Комментарии 33
А потом вы бы узнали про разряженные битовые поля, и все ужалось бы еще сильнее.
Не будет ли гораздо эффективнее разбить просеиваемые числа на блоки по, скажем, миллиарду бит в каждом? Тогда мы не будем пробегать по диску много раз, да и вообще весь текущий блок будет помещаться в ОЗУ, и сбросить его на диск надо будет лишь один раз простой одноразовой записью (а вообще, не зная вашей задачи, трудно сказать, нужно ли вообще будет хранилище на диске).
Чтобы выполнить просеивание в отдельно взятом блоке, достаточно знать простые до квадратного корня из верхней границы (т. е. в вашем случае нужны будут простые до миллиона).
P.S. На всякий случай - решето Эратосфена, особенно в такой "лобовой" реализации, как в статье - не самый лучший способ поиска всех простых.
Спасибо за внимание к материалу. Идея сделать по блокам, используя имеющиеся в наличии простые до миллиона, отличная. Конечно у меня они есть, т.к. предварительно прогнал эту программу на 16 ГБ (это примерно до 137 миллиардов). Но переписывать программу не хочу (да и времени нет, это всё на досуге). Пусть уже лошадка доработает.
Далее, на диске иметь их нужно, да, т.к. список простых это исходный материал для другого исследования. Я про него напишу отдельно, после того как триллион посчитается и покажет свои результаты.
А поподробнее про более эффективное решето что можете сказать?
Решето Эратосфена можно дальше улучшить, например, только рассматривая и храня нечётные числа - это ускоряет примерно вдвое. (Аналогично, можно было бы отсечь и кратные трём, пяти, и т. д., но это уже сделает код более муторным. Отсечение чётных же делается буквально парой изменений в границах цикла и обращениях к массивам.)
Также есть модификации этого решета, которые совершают лишь линейное число модификаций: http://e-maxx.ru/algo/prime_sieve_linear.
Но при ваших объёмах попробовать сделать блочное решето точно имеет смысл, потому что вместо прыжков по почти терабайтным файлам будет работа чисто в ОЗУ с периодическим сбросом результатов очередного блока на диск. Реализация там не сильно сложнее - по сути, вы сначала делаете обычное решето до 10^6, а затем идёте по блокам. Каждый блок обрабатывается почти стандартным алгоритмом, только внешний цикл идёт по предпосчитанным выше простым, а внутренний - по кратным им числам, лежащим внутри блока.
А вообще обычно ссылаются на решето Аткина как на самое быстрое. Я не знаю, как оно будет вести при вашем профиле нагрузки, так как я его самостоятельно никогда не "щупал".
Так ведь чётные числа отсекаются в строке где проверка на простоту числа, в if (Registry.Contains(i)) между внешним и внутренним циклами. Поэтому и нет никакого ускорения вдвое.
Вам, как минимум, приходится хранить их. Если не хранить признаки простоты чётных чисел — вам понадобится в два раза меньше памяти. А это уже приведёт к ускорению.
Помимо того, что отметил mayorovp, при игнорировании чётных внутренний цикл будет делать вдвое меньше итераций. Например, при вычеркивании кратных числу 3 мы будем только итерироваться по числам 9, 15, 21, и т. п., и не будем тратить нисколько времени на вычеркивание заведомо бесполезных 12, 18, 24.
А есть например вот такая статья.
Буду внимательнее читать комментарии. (del)
Мне кажется чем дальше, тем реже встречаются простые числа, и по памяти все это можно ужать. Правда за счёт скорости. А что вы такое делаете? Опровергаете Римана?)
Использование MMF накладывает слишком много накладных расходов по сравнению с массивом.
Поэтому, думаю намного быстрее было бы продвигаться блоками определенного разумного размера и просеивать рабочий блок на все простые числа сразу. После уже скидывать готовый блок в результирующий файл. Рабочий блок будет всего один и будет целиком помешаться в память при выборе разумного размера.
Это позволит выполнять только последовательные чтения и записи, что является самым быстрым доступом к файлам. А также позволяет продолжать работу с любого места где программа остановилась прошлый раз. Так как в файл будут записываться только полностью готовые блоки.
Таким образом можно обработать все простые пока не надоест по времени или не закончится место на диске или не закончится диапозон uint64 например.
Очень интересно, но что такое "Сопоставленные в памяти файлы" я так и не понял, а жаль. Впрочем спасибо за новое понятие - можно погуглить и разобраться, возможно окажется полезным.
Немного оффтоп - в последнем примере кода вместо goto quit, лучше сделать простой return
Почему нет оптимизации на четные числа? Это уже экономия по памяти в 2 раза.
Ну что ж вы так, простые числа можно было бы хранить поинтереснее, чем просто в битовом массиве. Например, как в MPEG, выбрать сколько-то "опорных" чисел и закодировать их как есть, а между - хранить только расстояния до следующего простого числа, они все относительно небольшие, максимально известное расстояние в 1550 уместилось бы в 11 бит (см. Prime gap)
Спасибо, мне статья понравилась.
База на диске — хороший компромисс между скоростью работы и простотой реализации, но для некоторых задач она не нужна:
— Если у вас в основном последовательный доступ, то есть, вам надо перебрать простые числа на интервале [X… Y], то имеет смысл их каждый раз заново просеивать: достаточно заранее в памяти просчитать и держать список простых чисел до sqrt(N), в вашем случае — до миллиона.
— Если у вас полностью рандомный доступ, то выгоднее воспользоваться критерием простоты чисел: en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Testing_against_small_sets_of_bases. Аккуратно написанный, он дает скорость 20 микросекунд на число (в отличие от 2 миллисекунд на seek на HDD): ceur-ws.org/Vol-1326/020-Forisek.pdf
Альтернативно, базу можно сократить в два раза, если хранить биты только на каждое нечетное число, или даже в три раза, если хранить только числа, дающие при делении на 6 остатки 1 или 5 (остальные не могут быть простыми, кроме чисел 2 и 3). А можно вообще упороться, и хранить только числа, дающие один из восьми остатков от деления на 30, что как раз занимает один байт. Я это все описывал в habr.com/ru/post/526924, там есть код на C#, который можно использовать для этого.
База данных с 1 трлн записей и опыт использования отображаемых на память файлов