Компромисс времени и памяти

разработчики из нас сам мне сообщили что на новом марсоходе установлена та же платформа управления памятью что и на кьюриосити кьюриосити был оборудован двумя компьютерами которые работали по очереди технические спецификации у них были следующие два гигабайта flash памяти 256 мегабайт оперативной памяти и нам нужно чтобы вся программа загрузилась в оперативную память и при этом она должна занимать не более пяти процентов оперативной памяти то есть это получается примерно 12,8 мегабайт а и эти данные понадобятся чтобы рассказать вам о компромиссе времени и памяти или памяти и времени это часто используемый термин в информатике я посмотрел на программу которую написал ay вид 42 в этой программе был массив из простых чисел до миллиона с его помощью программа при проверке числа на простоту могла шагать только по простым числам автор программа поставил вопрос почему бы заранее не сохранить в массиве все необходимые нам простые числа чтобы не высчитывать их каждый раз в прошлом видеоролике мы говорили что это оптимальный алгоритм для проверки на делимость хотя количество шагов в этой программе было небольшим работала она очень медленно и вылетала с ошибкой задолго до достижения предела интераций эта программа не смогла быстрый решить задачу для указанных мной ранее пределов в данном случае было решено уменьшить время работы а также количество проверок на делимость за счет увеличения пространства то есть памяти для хранения массива но почему возникли проблемы давайте подумаем вместе и посмотрим как сделать так чтобы эта программа смогла уложиться в установленный лимит памяти напомню нам нужно работать с числами чуть больше 9 квадриллионов алгоритм проверки на делимость у должен остановиться дойдя до квадратного корня искомого числа если к этому моменту или теле и не нашлись то число на 100 процентов простое сколько простых чисел мы должны хранить до квадратного корня из 9 квадриллионов и это будет около 95 миллионов сколько простых чисел меньше 95 миллионов в этом нам поможет теорема распределения простых чисел сколько простых чисел меньших никого значения x x деленный на натуральный логарифм x если x 94,9 миллиона то простых чисел в этом промежутке примерно 5 целых одна десятая миллиона чтобы сохранить столько чисел в памяти нужно посмотреть на наибольшее простое число в нашем случае мы знаем что это число будет чуть меньше чем 94,9 миллиона и если посчитать точное значение этого числа то наибольшее простое число до корня квадратного из верхнего предела которые мы должны будем сохранить в памяти будет равно 89 миллионов 70 8611 и сколько тогда памяти понадобится для хранения одного такого числа чтобы это узнать переведем это число в двоичную систему счисления ведь компьютер хранить числа виде менее переключателей мы уже говорили об этом в других видео в битах самое большое простое число выглядит вот так она занимает 24 бита или три байта столько нужно для хранения одного числа а теперь подумаем сколько нужно памяти для хранения всех чисел поскольку для самого большого числа нужно 24 бита нам понадобится набор из блоков по 24 бита в каждом из которых хранится одно простое число сколько бит нужно для хранения всего списка общая занимаемая память будет равняться произведению количества ячеек то есть простых чисел на размер каждой ячейки то есть примерно 5 миллионов 166 тысяч 822 числа умножить на 24 бита это чуть больше ста двадцати четырех миллионов бит если перевести в байты получится примерно 14,7 мегабайт грубо говоря примерно 15 мегабайт то есть в данных условиях в памяти не поместятся даже обычный список простых чисел причем это очень упрощенный пример например в массиве нужно хранить указатель на каждый элемент в 32 бита вам компьютере указателя занимает четыре байта то есть в реальности потребуется гораздо больше чем 15 мегабайт таким образом сохранить все простые числа до корня квадратного из максимального числа просто-напросто не представляется возможным мы не укладываемся выделенную память а что если цена на носителе упадет в тысячу а то и в 10 тысяч раз в современных криптографических алгоритмах используется гораздо большие числа и поиск делителей становится просто невозможным поэтому всегда нужно иметь ввиду что доступная нам память ограниченна сколько бы времени не работала программа при решении задач всегда приходится искать баланс между используемым пространством или временем и чтобы решить задачу проверки числа на простоту за небольшое время с использованием небольшого количества памяти нужно придумать какой-то совсем другой подход спасибо что подписывайтесь на наш канал мы будем рады услышать ваше мнение по поводу этого видео если у вас возникли вопросы касательно данного видеоролика то напишите их в комментариях и мы с удовольствием постараемся ответить на них