(Источник рисунка )Общеизвестно, что Решето Эратосфена (РЭ) один из древнейших алгоритмов, появившийся задолго до изобретения компьютеров. Поэтому можно подумать, что за века этот алгоритм изучен вдоль и поперек и добавить к нему ничего невозможно. Если посмотреть Википедию – там море ссылок на авторитетные источники, в которых запросто утонуть. Поэтому удивился, когда на днях случайно обнаружил, что вариант, который в Википедии преподносится как оптимальный, можно заметно оптимизировать.
Дело было так. В обсуждении статьи по функциональному программированию (ФП) задал вопрос: как в этой парадигме написать РЭ. Обладая более чем скудными знаниями по ФП, не берусь судить об ответах, но другие участники обсуждения забраковали некоторые из предложенных сходу решений, указав, что вместо теоретической сложности
(1)
предложенная реализация будет обладать вычислительной сложностью
(2)
и что с такой сложностью не дождаться, когда, например, просеются 10 миллионов чисел. Мне стало интересно и я попробовал реализовать оптимальную согласно Википедии версию, используя привычное мне процедурное программирование. В Delphi-7 у меня получился следующий код:
program EratosthenesSieve;
// Sieve of Eratosthenes
{$APPTYPE CONSOLE}
uses
SysUtils, DateUtils,Math;
const
version ='1.0.1d1';
N = 1000000000; // number of primes
var
sieve : array [2..N] of boolean; // false if prime
t0, t1,dt : TDateTime;
O,C : Extended;
procedure init;
var
i : integer;
begin
for i:=2 to n do
sieve [i] := false;
end; //init
procedure calc (start : integer);
var
prime, i : integer;
breakLoop, exitProc : Boolean;
begin
prime := start;
exitProc := false;
repeat
// find next prime
prime := prime+1;
while (prime<N) and sieve[prime] do
inc (prime);
i:= sqr(prime);
// delete
if i<= N then
begin
breakLoop := false;
repeat
if i<= N then
begin
sieve [i] := true;
inc (i,prime);
end
else // if i<= N
breakLoop := true;
until breakLoop;
end
else // if prime+prime<= N
exitProc := true;
until exitProc;
end; //calc
procedure print;
var
i :integer;
found : integer;
begin
found := 0;
for i:=2 to N do
if not sieve [i] then
begin
// write (i,', ');
inc(found);
end;
writeln;
writeln ('Found ',found,' primes.');
end; //
begin // program body
writeln ('Sieve of Eratosthenes version ', version);
writeln('N= ',N);
init;
t0 := now;
writeln('Program started ',DateTimeToStr(t0));
t0 := now;
calc (1);
t1 := now;
writeln('Program finished ',DateTimeToStr(t1));
dt := SecondSpan(t1,t0);
writeln ('Time is ',FloatToStr(dt),' sec.');
O := N* ln(ln(N));
C := dt/O;
writeln ('O(N ln ln N)= ',O,' C=',C);
O := sqr(N)/ln(N);
C := dt/O;
writeln ('O(N*N/ln N)= ',O,' C=',C);
print;
writeln ('Press Enter to stop...');
readln;
end.РЭ представлено булевым массивом sieve с инверсными значениями — если число простое, оно обозначается как false, что позволяет сократить количество операций отрицания (not) при просеивании. В программе 3 процедуры: инициализации РЭ — init, вычислений (просеивание и зачеркивание чисел в РЭ) — calc и вывода найденных в результате простых чисел — print, при этом подсчитывается количество найденных чисел. Особо обращу внимание на закомментированный вывод простых чисел в процедуре print: для тестирования при N=1000 комментарий снимается.
Здесь в процедуре calc использую рекомендацию Википедии: для очередного простого числа i вычеркивать из РЭ числа
Эта программа просеяла миллиард чисел за 17.6 сек. на моем ПК (CPU Intel Core i7 3.4 ГГц).
Сделав эту программу, я вдруг вспомнил о широко известных свойствах четных и нечетных чисел.
Лемма 1. 1) нечетное+нечетное=четное; 2) нечетное+четное=нечетное; 3) четное+четное= четное.
Доказательство
1) делится на 2. ЧТД.
2) не делится на 2 без остатка. ЧТД.
3) делится на 2. ЧТД.
Лемма 2. Квадрат нечетного числа есть нечетное число.
Доказательство. не делится на 2 без остатка. ЧТД.
Замечание. Простое число, большее 2, нечетное.
Поэтому можно вычеркивать только нечетные числа:
(3)
Но прежде надо вычеркнуть все четные числа. Это делает измененная процедура инициализации init.
program EratosthenesSieve;
// Sieve of Eratosthenes
{$APPTYPE CONSOLE}
uses
SysUtils, DateUtils,Math;
const
version ='1.0.1d1';
N = 1000000000; // number of primes
var
sieve : array [2..N] of boolean; // false if prime
t0, t1,dt : TDateTime;
O,C : Extended;
procedure init;
var
i : integer;
begin
for i:=2 to n do
sieve [i] := not odd(i);
end; //init
procedure calc (start : integer);
var
prime,prime2, i : integer;
breakLoop, exitProc : Boolean;
begin
prime := start;
exitProc := false;
repeat
// find next prime
prime := prime+1;
while (prime<N) and sieve[prime] do
inc (prime);
// i:= prime*prime;
i:= sqr(prime);
prime2 := prime+prime;
// delete
if i<= N then
begin
breakLoop := false;
repeat
if i<= N then
begin
sieve [i] := true;
inc (i,prime2);
end
else // if i<= N
breakLoop := true;
until breakLoop;
end
else // if prime+prime<= N
exitProc := true;
until exitProc;
sieve [2] := false;
end; //calc
procedure print;
var
i :integer;
found : integer;
begin
found := 0;
for i:=2 to N do
if not sieve [i] then
begin
// write (i,', ');
inc(found);
end;
writeln;
writeln ('Found ',found,' primes.');
end; //
begin // program body
writeln ('Sieve of Eratosthenes version ', version);
writeln('N= ',N);
init;
t0 := now;
writeln('Program started ',DateTimeToStr(t0));
t0 := now;
calc (2);
t1 := now;
writeln('Program finished ',DateTimeToStr(t1));
dt := SecondSpan(t1,t0);
writeln ('Time is ',FloatToStr(dt),' sec.');
O := N* ln(ln(N));
C := dt/O;
writeln ('O(N ln ln N)= ',O,' C=',C);
O := sqr(N)/ln(N);
C := dt/O;
writeln ('O(N*N/ln N)= ',O,' C=',C);
print;
writeln ('Press Enter to stop...');
readln;
end.Эта программа сработала за 9.9 сек. – почти вдвое быстрее.
Для оценки соответствия реального времени работы программы теоретическому я предположил, что
где – измеренное время работы;
– константа с размерностью времени;
– теоретическая оценка.
Вычислил отсюда для оценки (1) и (2). Для и меньше близко нулю. Поэтому привожу данные по первой программе для больших
| (1) | (2) | |
|---|---|---|
Как видим, оценка (1) гораздо ближе к реальным результатам. Для второй программы наблюдается похожая картина. Сильно сомневаюсь, что открыл Америку с применением последовательности (3) и буду очень благодарен за ссылку на работу, где применялся этот подход. Скорее всего, авторы Википедии сами утонули в море информации по РЭ и пропустили эту работу.
Комментарии (102)
mikhaelkh
05.05.2019 18:51www.spoj.com/problems/PRIMES2 — как раз задачка на поиск простых до миллиарда. Самое быстрое решение просеивает за 0.21 секунды на Intel Xeon E3-1220 v5. Алгоритм — segmented sieve of Eratosthenes with wheel factorization modulo 210
itblogger
06.05.2019 01:51Любые простые числа за исключением 2 и 3 подчиняются простой формуле 6*N ± 1. То есть, любое простое число это какое-то натуральное N умноженное на 6 плюс или минус один. ВСЕ простые числа кроме 2 и 3 обладают этим свойством. Обратное, естественно, неверно. Доказывается элементарно.
Так вот, эта формула как минимум в 6 раз снижает сложность решета.Cerberuser
06.05.2019 04:19По идее, в три — проверяется только каждое третье число, или я что-то не так понял?
mikhaelkh
06.05.2019 04:30В 3 раза, (2/1)(3/2) = 3.
Если брать простые числа, которые взаимно просты с 2, 3, 5, 7 — Wheel factorization, то скорость возрастёт примерно в (2/1)(3/2)(5/4)(7/6) = 210/48 = 4.375 раза. Для миллиарда колесо делать больше невыгодно.
MarazmDed
06.05.2019 09:34Любые простые числа за исключением 2 и 3 подчиняются простой формуле 6*N ± 1.
Сомнительное утверждение. Можете это доказать? Особенно про «ВСЕ».Cerberuser
06.05.2019 09:42+16N, 6N+2, 6N+4 — чётные, 6N+3 делится на 3, остаётся 6N+1 и 6N+5, разве нет? Никто ж не говорит, по идее, что все такие числа — простые. Только что все простые числа (кроме двух) — обязательно такие.
orion76
06.05.2019 10:15Да, любопытная формула-)
Но это формула не вычисления простого числа.
В любом случае, ее результат еще надо проверять на «простоту» 2 раза-)
Так что прироста в производительности не будет, как минимум ощутимого.
например N=6
X1 = 6 * 6 + 1 = 37
X2 = 6 * 6 — 1 = 35
и теперь, чтобы «доказать», что какое-то из этих чисел простое, необходимо попытаться разложить их на множители.-)Cerberuser
06.05.2019 10:17Так речь-то не о замене перебора по возрастанию на формулу, а о том, чтобы заранее отсечь заведомо неподходящие случаи.
Am0ralist
06.05.2019 10:28Решето это сказать, что все кратные, например, 7 элементы массива от 1 до N — вычеркиваем. При этом порядковый номер элемента массива по сути и есть его значение. То есть вы в цикле от 2 до k говорите что элементы 14, 21… 7*k — точно не простые.
У вас в массиве же 1/3 элементов и под каким номером то же 49 число — не понятно, придется не обращаться по номеру элемента, а искать по элементам есть ли в массиве число 49?
Am0ralist
06.05.2019 10:23Так вот, эта формула как минимум в 6 раз снижает сложность решета.
Во-первых, таки в 3 (слагаемые 0,2,3,4 убираем, 1 и 5 оставляем, 2 из 6, то есть треть).
Во-вторых, для именно решета это не особо снижает сложность, ибо там просто вначале вычеркивают всё, кратное 2, потом 3, потом 5, потом 7 и т.д. Таким образом массив сократить можно, но количество проверок по сути не изменится, просто для части проверок кратного, допустим, 7 элементов в массиве просто не будет. Вот только если до этого ты просто говорил, что элемент массива 49 — вычеркиваем, то сейчас тебе нужно найти элемент массива с значением 49 и уже его вычеркнуть.
Не вижу упрощения…
koldyr
06.05.2019 13:04Если число делится на что-то большее, чем корень из него, то, очевидно, оно делится на что-то меньшее. Таким образом, при фиксированном n можно обрабатывать поток окном длины корень из n, что существенно снижает требования по памяти.
MarazmDed
06.05.2019 14:03Если число делится на что-то большее, чем корень из него,
Как может число делиться нацело на что-то большее корня этого числа? sqrt(N) * sqrt(N)= N
то, очевидно, оно делится на что-то меньшее.
С чего вдруг?DuMMeR
06.05.2019 15:45+1Как может число делиться нацело на что-то большее корня этого числа? sqrt(N) * sqrt(N)= N
Если оно составное и не является квадратом простого числа.
Как, например, число 26 среди делителей имеет число 13, которое больше чем sqrt(26)=~ 5.1.
С чего вдруг?
Ситуации, когда N имеет два делителя p_1, p_2, таких что p_1 > sqrt(N), p_2 > sqrt(N), быть не может, поскольку произведение p_1 * p_2 будет заведомо больше N.
Значит, если существует делитель p_1 > sqrt(N), то будет существовать делитель p_2 < sqrt(N).
malkovsky
06.05.2019 19:19Скорее всего, авторы Википедии сами утонули в море информации по РЭ и пропустили эту работу.
Ничего авторы не утонули, просто вы поленились прочитать статью полностью, ну или хотя бы пролистать оглавление. Пролистали бы — обратили бы внимание на решето только по нечетным числам, а заодно более интересное решето за линейное время
third112 Автор
06.05.2019 19:28И где там последовательность (3)? И почему оптимизированной реализацией назван другой вариант? Приведенная там последовательность (Листинг 1 у меня) избыточна.
malkovsky
07.05.2019 14:07который в Википедии преподносится как оптимальный
И почему оптимизированной реализацией назван другой вариант?
Видите, Вы сами себя поправили: в википедии приведен «оптимизированный» вариант, а не оптимальный. Думаю, что здесь есть «стилистическая» ошибка от авторов статьи в вики, наверно подразумевалась оптимизация базового алгоритма решета Эратосфена, которая просто убирает ненужные действия.
И где там последовательность (3)?
Я кидал ссылку на параграф, там описание модификации, но кода нет. В общем то, вы и сами согласились, что модификация не очень хитрая, возможно авторы статьи в вики просто не стали заморачиваться с лишним кодом. Я бы даже предположил, что вот эта страница — оригинал статьи в вики. Если нужен код для проверки решета с линейным временем работы, то его можно взять здесь, советую в нем разобраться.
Обладая более чем скудными знаниями по ФП, не берусь судить об ответах, но другие участники обсуждения забраковали некоторые из предложенных сходу решений, указав, что вместо теоретической сложности
Я не участвовал в этом обсуждении, но кажется, что асимптотика n^2/log(n) относится не к решету Эратосфена, а к алгоритму, предложенному в этом комментарии, дело в том, что если вы просто напишете цикл типа: for i:=1 to n do «перебрать все простые делители от 2 до i-1 и проверить делится ли i хотя бы на один из них», то получите ровно такую ассимптотику, так как количество простых чисел от 2 до i — это примерно i / log(i). А проблема заключалась ровно в том, что ФП не очень хорошо подходит для реализации РЭ, как и для многих других нетривиальных алгоритмов.third112 Автор
07.05.2019 18:28А проблема заключалась ровно в том, что ФП не очень хорошо подходит для реализации РЭ, как и для многих других нетривиальных алгоритмов.
В том обсуждении был сделан аналогичный вывод. Т.о. РЭ помогло выявить важную проблему технологии программирования (ФП):
Для многих задач в этой парадигме можно сделать очень простой и понятный код. Для других задач чистое ФП все-таки не так хорошо подходит.
Я кидал ссылку на параграф, там описание модификации, но кода нет.
Про какой параграф речь? Если про РЭ с «линейным» временем — там псевдокод:
Вход: натуральное число n
Пусть pr - целочисленный массив, поначалу пустой; lp - целочисленный массив, индексируемый от 2 до n, заполненный нулями для i := 2, 3, 4, ..., до n: если lp[i] = 0: lp[i] := i pr[] += {i} для p из pr пока p ? lp[i] и p*i ? n: lp[p*i] := p Выход: все числа в массиве pr.
советую в нем разобраться.
Код (см. Реализация) почти аналогичен псевдокоду в вики. И как, скажите, пожалуйста, два вложенных друг в друга цикла (первый от 2 до n) могут дать линейное время?
Думаю, что здесь есть «стилистическая» ошибка от авторов статьи в вики,
И я так думаю. О чем и сказал в статье.third112 Автор
07.05.2019 18:38PS BTW Пожалуйста, подскажите, кто знает: как на Хабре оформлять псевдокод? Установил «source lang=code» пропали отступы, установил «delphi» фигурные скобки стали комментами.
wataru
07.05.2019 23:04+1И как, скажите, пожалуйста, два вложенных друг в друга цикла (первый от 2 до n) могут дать линейное время?
Внутренний цикл суммарно выполнится O(n) раз. Там так хитро подогнанно, что каждый элемент массива lp[] будет записан ровно один раз. А это единственная операция во вложенном цикле.
Почему так происходит понрять чуть сложнее. lp[] — минимальный простой делитель для каждого числа. Все позиции будут подсчитанны: Вот есть число k и его минимальный делитель lp[k]. В момент, когда i в коде будет k / lp[k] внутренний цикл точно дойдет до k, ведь в k/lp[k] не может быть делителей меньше lp[к], иначе бы это был меньший делитель в k. Теперь, почему оно будет подсчитанно только один раз: Когда мы пишем в ичейку lp[k] значение p — i однозначно равно k/p, других вариантов нет. Вот и получается, что внутренняя операция выполниться ровно n раз.
third112 Автор
08.05.2019 03:45Спасибо. Я примерно представил, что Вы хотите сказать, но, к сожалению, то что Вам удалось сказать звучит как-то слишком расплывчато (с учетом того, что сказано в упомянутых источниках). М.б., если поднять первоисточник, то там всё это показано достаточно строго. Можно предположить, что авторы вторичных источников разобрались в первичном, но при пересказе опустили важные моменты, сделав вид, что эти моменты очевидные. Такое, к сожалению, случается с нетривиальными алгоритмами. В результате четкое наглядное доказательство превращается в запутанный ребус. Однако читатель не должен разгадывать ребусы. В мат.журналах существует строгое правило: чтение производится до первой ошибки или неясности. При этом, конечно, встречаются и очень покладистые читатели, которые готовы верить каждому «печатному слову» — им только кажется, что они всё поняли.
Прежде всего возникает вопрос: а зачем тогда внутренний цикл?
внутренний цикл точно дойдет до k
Сколько шагов он будет доходить? Не будет ли он работать вхолостую подбирая нужное значение? Не зависит ли это от реализации?wataru
08.05.2019 11:05Прежде всего возникает вопрос: а зачем тогда внутренний цикл?
Что бы посчитать для всех k=p*i.
Представьте вычисление этих lp[] в виде графа. Есть n точек в ряд. Проведите ребра из каждой точки k в k/lp[k]. Всего ребер n. Этот алгоритм линейного решета обходит ребра задом-на-перед. Внешний цикл перебирает все вершины. Внутренний перебирает все ребра, втыкающиеся в эту вершину и записывает значение для другого конца ребра. Для каких-то вершин будет много ребер, для каких-то мало, для каких-то не одного. Суммарно — n.
Сколько шагов он будет доходить?
А какая разница? Каждый шаг — одно подсчитанное значение. Каждое значение считается ровно один раз. Всего значений n.
third112 Автор
08.05.2019 17:32Внешний цикл перебирает все вершины. Внутренний перебирает все ребра
Пусть в графе m вершин и n ребер. Граф задан матрицей смежности
g : array [1..m,1..m] of boolean;
где g[i,j] = true, если существует ребро (i,j), false — в противном случае. Поставим простейшую задачу: перебором пар вершин удалить все ребра.
Решение:
for i:=1 to m do for j:=1 to m do g[i,j] := false;
Сложность O(m^2), от n не зависит.
Если мы хотим реагировать только на существующие ребра, то можем написать:
for i:=1 to m do for j:=1 to m do if g[i,j] then g[i,j] := false;
Сложность не изменится, хотя оператор g[i,j] := false; будет выполняться ровно m раз в случае несимметрической матрицы и 2m раз в случае симметрической.
В псевдокоде действителбную сложность можно попытаться замаскировать:
для i от 1 до m для j: (i,j) существует, j<=m g[i,j] := false;
Можно работать только с половиной матрицы выше (или ниже) главной диагонали, но это для наших рассуждений не принципиально.wataru
08.05.2019 17:34Но тут граф задан списком смежности!
third112 Автор
08.05.2019 17:47Дла списка необходим только один цикл:
для i от 1 до n { взять_из _списка_ребро (i); удалить (i); }
Сложность O(n).wataru
08.05.2019 20:23Эм… Список смежности
Для каждой вершины хранится отдельный список всех, смежных с ней. Обход ребер для одной вершины — внутренний список. Обход для всех ребер — перебор вершины — внешний цикл.
third112 Автор
09.05.2019 00:21Пока Гвидо ван Россум делал Питон списком смежности называли и такое, нпр., представление полного графа из 3 вершин: 1-2, 2-3, 3-1.
Нпр., и после Питона я написал:
Такой подход соответствует одному из наиболее экономных представлений графа в виде списка смежности. В частности, он очень удобен для ручного ввода графов. Можно использовать следующий формат для записи ребра:
Возражений не последовало )
v-u
где v,u – инцидентные ребру вершины.
Обход ребер для одной вершины — внутренний список. Обход для всех ребер — перебор вершины — внешний цикл.
Число всех вершин — m, число ребер — n. Допустим наиболее экономную по времени ситуацию, когда в списках нет повтора ребер, как в приведенном примере: 1-2, 2-3, 3-1 — первое число вершина, для которой список, вторая список (в примере они из одного элемента). Обработка всех списков по внутреннему циклу даст kn операций, но внешний цикл перебора вершин — это еще pm операций, где k,p константы, зависящие от реализациии. Т.о. получим O(kn+pm). Однако пока не очевидно, что обсуждаемый алгоритм эквивалентен алгоритму со списком смежности графа.wataru
09.05.2019 10:51Однако пока не очевидно, что обсуждаемый алгоритм эквивалентен алгоритму со списком смежности графа.
Внешний цикл по i -это фактически перебор вершины.
Внутренний цикл по p — это беребор всех ребер в списке смежности для этой вершины. Там n вершин. Осталось понять, что ребер ровно n. В итоге, как вы указали, весь алгоритм займет O(c1*n+c2*n) = O(n)
Ребра тут — это i->p*i: p <= lp[i].
Главное убедится, что все правые части не равны между собой.
Допустим для двух разных i,j правые концы ребер совпали: i < j, p1*i = p2*j, p1 <= lp[i], p2 <= lp[j].
Поскольку p1 и p2 — простые, то i=p2*k, j=p1*k. Еще, очевидно, что p1 > p2 (ведь при умножении на i<j p1 дает такой же результат). Теперь посмотрим повнимательнее на условия p1 <= lp[i]. Можно подставить i внутрь и раскрыть определение lp (lp — минимальный простой делитель, значит lp[pk] = min(p, lp[k])):
p1 <= lp[p1*k], значит p1 <= lp[k] и p1 <= p2. Но p1 > p2! Вот и противоречие.
malkovsky
08.05.2019 14:48И как, скажите, пожалуйста, два вложенных друг в друга цикла (первый от 2 до n) могут дать линейное время?
Прежде всего возникает вопрос: а зачем тогда внутренний цикл?
Это довольно распространенная практика в некоторых алгоритмах, кроме РЭ приходят в голову метод двух указателей и алгоритм Кнута-Морриса-Пратта
Ghost_nsk
07.05.2019 07:20Вы можете ускорить альгоритм РЭ но это будет уже другой алгоритм. Да и вообще для чего? Он хорош для демострации школьникам, а на практике на столько дорог что скорее бесполезен. На практике встречаестся задача проверки некоего числа на простоту. Для этого есть другие алгоритмы, например Конягина-Померанса, Миллера и куча более дешевых вероятностных оценок. Задача изобрести большое простое число решается примено так, генерируем случайное число большой размерности, проверяем его простоту, повторяем.
third112 Автор
07.05.2019 10:47Вы можете ускорить альгоритм РЭ
Я не вижу, как это можно сделать. Попробуйте.
Он хорош для демострации школьникам, а на практике на столько дорог что скорее бесполезен.
Решето Эратосфена является популярным способом оценки производительности компьютера.
MarazmDed
Волшебно! :) Выкинуть гигабайт памяти непонятно на что :)
Что-то мне подсказывает, что бинарное дерево простых чисел будет занимать радикально меньше памяти.
Как обычно, нужно принимать во внимание не только вычислительную сложность алгоритма, но еще и сложность по памяти. И если миллиард итераций для современных камней — это нормально, то гигабайт памяти на вспомогательную структуру данных — явный перебор.
third112 Автор
Как обычно: что нужно — на то и кидаем: нужно ускорить — не постоим за памятью, нужно
комнату обогретькамень догрузить — подождем с обеда до обеда :) В вики, нпр., ссылки, где простоту каждого числа 1 битом кодируют…MarazmDed
А тут еще вопрос, насколько поиск по бинарному дереву тормознее. Да, это лишний log n. Но для миллиарда — это плюс-минус 30 сравнений. А по памяти экономия колоссальная.
Хотя бы. Вы тут от 8 до 32 раз потребление памяти уменьшите. Но скорость несколько уменьшится.
third112 Автор
infund
Может быть, будет интересно — написал реализацию решета на Swift. Собственно «решето» — три строчки в цикле while, включая условие выхода.
NickViz
ну а как вы обходить то это дерево будете? и изначально в нём должны быть все числа. весь миллиард.
вы алгоритм эратосфена-то видели? бинарное дерево может быть хорошо для записи результата работы алгоритма. но при работе он потребует памяти.
MarazmDed
Бинарным поиском.
Зачем? Вы в дерево можете добавлять элементы динамически. Да, балансировка дерева — это затраты времени. Вопрос в том, что чем больше числа, тем реже будут попадаться простые, соответственно перестройка дерева — относительно редкая операция.
Видел. И что? Ну а если вы захотите триллион простых чисел найти, сразу же терабайт памяти выделять будете? И гарантированно уроните домашнюю систему, и среднестатистический сервер? Или все же будете думать о тех проблемах, которые у вас возникнут? массив и дерево — эквивалентные представления одной и той же структуры данных. А вот свойства их сильно разные. Дерево — занимает ровно столько памяти, сколько необходимо. При этом сложность поиска — логарифмическая. Что не страшно даже для размерностей в триллион.
Напротив, дерево занимает минимум памяти. И результат работы алгоритма — это еще вопрос, какой должен быть. В консоль весь перечень чисел вы будете выплескивать только на лабораторках в ВУЗе/школе. В реальной работе будут какие-либо вменяемые структуры данных. Список? Дерево? Хэш-таблица? Зависит от потребностей.
NickViz
Вы не могли бы накидать алгоритм, как можно решето эратосфена на двоичном дереве сделать?
если задача будет стоять найти их с помощью алгоритма эратосфена — то да, буду выделять. Ну либо бить на части и искать там. потом объединять. но двоичное дерево сюда не лезет. покажите как.
MarazmDed
Точно также, как и на массиве, но вместо будете писать . Функция getSieve(idx) будет вам возвращать true, если число — простое, и false — В противном случае.
Сильно. Т.е. вас не будет смущать, что, программа у вас тупо вылетит по out of memory exception? И при этом, я вам привел простой путь, как можно разменять память на скорость.
Студент? :) На практике у вас не будет стоять задача найти ИМЕННО с помощью такого-то алгоритма. На практике у вас будет задача — РЕШИТЬ задачу корректно и с учетом разумных ограничений по памяти/скорости + доп. ограничения предметной области.
third112 Автор
На практике часто стоит задача оценки производительности (benchmark), и для нее часто используют РЭ в различных вариантах часто сознательно загружая ОЗУ.
MarazmDed
Вам тут очень легко перестараться: размер ОЗУ вы можете узнать у операционки, а вот фрагментацию ОЗУ вы уже не узнаете просто так. Да и еще непонятно, что операционка будет делать с вашими страницами памяти. Возьмет и отправит в своп. И весь ваш бенчмарк слился. Кстати, не могу сказать, что задача оценки производительности стоит «часто».
third112 Автор
Бенчмарк нужен и для выявления возможности таких накладок. Когда подобное недопустимо меняют конфигурацию или систему.
MarazmDed
Вряд ли бенчмарк будет одним здоровым куском выделять память. Скорее, это будут порции памяти разумного размера.
third112 Автор
И это м.б. целью тестирования: как выделяет, насколько быстро и т.д.
MarazmDed
В таком случае, это будет тест ядра операционной системы, а не железа/приложения. возможно и реальная задача, но явно не распространенная. Насколько я разбираюсь в колбасных обрезках, обычно нужно протестировать производительность своего разработанного софта. И тут уже не решето Эратосфена применяют, а имитируют нагрузку пользователей. При чем, стараются угадать реальные кейсы.
third112 Автор
NickViz
Ну и? первый проход вычеркивает все четные числа. соответственно в ваше дерево должны будут быть они занесены изначально, весь миллиард (если вычеркиваем), или пол-миллиарда добавлено, если мы в дереве храним вычеркнутое.
будет ли дерево с таким количеством узлов меньше жрать памяти чем массив — для меня ясно. нет, не будет.
далее — последовательный доступ к памяти по сравнению со случайным в дереве — в разы быстрее.
если памяти мало — общий диапазон разбивается на под-диапазоны и решето применяется последовательно.
а вас именно об этом просили? нет, правда? если мне нужно менять память на скорость — в пределе вообще одним числом можно обойтись и делить до корня из лимита. да, не быстро будет, но зато драгоценную память не потребим.
ай спасибо за комплимент. как я оказывается хорошо сохранился. а вы я так понимаю — преподаватель?
вот и стоит задача — решить как можно быстрее. и вас не удивляет, что лучший результат www.spoj.com/problems/PRIMES2 достигнут на решете на массиве. а не на супер-пупер дереве.
MarazmDed
Тьфу-ты, бес попутал :) Прошу пардону. :) Действительно, вся соль решета Эратосфена в потреблении кучи памяти. И хоть какой-то разумный выход — действительно бить большой диапазон на более мелкие.
Но это как раз и говорит о том, что нужно думать, что пишешь: выделить массив на гигабайт просто в качестве примера — это сильно. Если речь идет о таких числах, значит изначально нужно продумывать либо менее требовательный к памяти алгоритм, либо бить задачу на куски.
Тоже самое и про терабайт памяти. Хрен вы его выделите одним куском.
NickViz
не проблем :-) а то я уж думал, что сам в маразм впал и чего-то простейшего, что все легко видят не ухватил.
В win x64 VA для процесса 8TB. И максимальный лимит на swap файл 16TB. т.е. выделить можно. правда всё будет в swap на обычных машинах и при работе решета последовательно будет с диска в память и обратно трешиться, но, в принципе, на домашнем компе на сегодняшний день — можно. непрактично, очень не быстро, но можно. не нужно, это да, но можно.
third112 Автор
MarazmDed
У вас на суперкомпах память быстрее кончится, чем вычислительные возможности. Ну, например, 256Гб памяти — это уже где-то ближе к верхней планке. При этом, этим алгоритмом ее сожрать можно очень быстро.
third112 Автор
Супер-компы быстро развиваются…
MarazmDed
Но то, что оно именно ВЫДЕЛИТСЯ — далеко не факт :) Т.е. вероятность заработать out of memory exception — очень и очень повышается.
Именно с этого я и начал, пока в маразм не ушел :) Часто вижу, как свежедипломированные специалисты подобными вещами в реальных проектах начинают чудить. А все почему? Потому что 4-6 лет в ВУЗе, если не пьянку пьянствовали, то решали только учебные задачи.
Меня, например, порадовало, как один краснодипломник на тестовом задании в цикле коннекшн к базе устанавливал. Ну там, цикл по количеству элементов в коллекции. На каждой итерации: а) создаем ADO DB com-объект, устанавливаем коннекшн, выполняем запрос.
Вопрос был только один: почему диплом — красный. :)
NickViz
ну наверное как в анекдоте don-ald.livejournal.com/541672.html
что бы опасались…
почему? я завтра если время будет добавлю свопа и попробую тер выделить и пройтись по нему. консольная прога, с.с++ win10. результат отпишу.
MarazmDed
Так не честно :)
А винт, случаем, не SSD?
NickViz
ну вот, получилось следующее: свопа добил до 905GB — на 2х SSD и одном HDD (больше места просто нет) плюс 32GB рамы.
Попробовал аллоцировать вектор на 900GB — не вышло.
Попробовал на 100GB — вышло и committed памяти было 105GB. В общем понятно, что запас нужен. проверил два прохода:
Allocated in 153479ms << время на std::vector test(size);
First pass in 228883ms << проход по вектору с занулением 0x00FF00FF00FF00FF — имитируем вычеркивание четных
Second pass in 314308ms << проход с шагом 3 побайтовый
Попробовал с 800GB — выделило, committed memory 840GB. Ждать окончания выполнения на 800GB уже не стал.
Резюме — на современных машинах можно работать с терабайтными массивами, но медленно. лучше разбить их на части, которые лезут в память. а идеально в кеш первого уровня :-)
MarazmDed
Интересный тест. Кстати, а вектор гарантирует наличие непрерывного куска памяти? Или все же выделяет ее кусочками? Вообще, в теории, у операционки блок какого максимального размера можно запросить?
NickViz
да, стандарт гарантирует. у Win операционки x64 процессу можно запросить 8TB минус накладные расходы (код, стек, BSS, рантайму памяти надо). Но если на асме примитивное консольное приложение накорябать — то почти все 8TB получатся. Линукс вроде 128TB может процессу выделить.
lorc
Да, С++ вектор гарантирует непрерывный кусок памяти.
Операционке в общем без разницы какой блок выделять. Благодаря MMU, то что для процесса выглядит как один большой регион, на самом деле может быть размазано тонким слоем по памяти и свопу. Так что вопрос чисто к имплементации, которая, естественно может отличаться на разных версиях ядра, не говоря уж о разных ядрах.
third112 Автор
Слышал об обратном случае преувеличенной заботы о ресурсах. Во времена IBM PC AT в редакцию одного солидного н-т. журнала серьезные вроде бы авторы прислали описание своей прикладной программы, где особой заслугой отмечалась реализация обработки событий мыши на ассемблере. На недоуменный вопрос редактора, а почему на ассемблере, было уверенно отвечено, что на высоком ЯП быстродействия может не хватить. В редакции, когда обсуждали, кто-то предположил, что может они не рукой мышь двигают, а из пневмопушки ей стреляют, чтобы катилась быстрей.
yarick123
MarazmDed «Решето Эратосфена» — это, если я правильно помню, алгоритм, который выщитывает простые числа в диапазоне от 2 до N путём вычёркивания в этом диапазоне всех чисел, больше текущего простого числа, которые делятся на это число. Мы начинаем с 2. Следующим простым числом будет первое невычеркнутое число. Так что, сам алгоритм предписывает сохранять информацию о том, «вычеркнуто» данное число или нет, для чисел в диапазоне 2,…, N.
Бесспорно, информацию можно хранить по-разному. Например, сделав утверждение, что поскольку все чётные числа непростые, мы всегда расматриваем только нечётные. Таким образом массив уменьшается в два раза…
Вы, судя по всему, предлагаете хранить только простые числа в двоичном дереве. А как же непростые? Как алгоритм будет «вычёркивать» соответствующие числа больше текущего? Или Вы, всё-же, предлагаете хранить информацию о том, вычеркнуто число или нет, для чисел от 2 до N в двоичном дереве? Тогда это скорее не оптимизация, а совсем даже наоборот…
MarazmDed
Да, прошу прощения — меня заглючило.
Но как бы там ни было, выделение гигабайта памяти — это сильно. А если терабайт потребуется? Тоже так написать? Просто нужно смотреть на применимость алгоритмов. Для больших N — не использовать решето Эратосфена, или бить диапазоны на куски.
third112 Автор
Первая пришедшая в голову идея. Записываем, нпр., в дерево числа до 1 млн. начинаем удалять четные, удаляя каждую вершину дерева. Дерево уменьшилось вдвое, добавляем к дереву второй лимон чисел, продолжаем удалять четные. И т.д., пока дерво не достигнет лимита памяти. Запоминаем, то число, на котором встали с удалением кратных 2двум, обозначим его х2, Переходим к удалению троек (т.е. что делится на 3) в дереве нечетных чисел. Доходим до х2. Останавливаем удаление троек и запоминаем х3 = х2. Добавляем в дерево следующую порцию чисел, удаляем двойки, потом с х3 удаляем тройки. Аналогично с другими числами.
MarazmDed
Да у вас вообще не должно быть в дереве лишних элементов!
Изначально — дерево пустое. И функция проверки на простоту для любого числа будет возвращать false.
Затем запускаете алгоритм Эратосфена. Нашли число — добавили его в дерево. Четные числа вообще не надо проверять. Просто в цикле шаг меняете и все.
NickViz
вот это вот — ну бред же.
что конкретно значит у вас «нашли число»? как нашли?
Am0ralist
2n+1, где n — шаг цикла?
Хотя да, как хранить инфу, что вычеркиваем…
NickViz
т.е. все не простые числа будут в итоге в дереве — так?
ну и почему вы думаете, что это займёт меньше памяти? число, пара ссылок — на 64-бит системе — это в (1+8+8) 17 раз больше, чем один байт в массиве.
Далее, для дерева надо по нему пробежаться (случайный доступ к памяти в среднем на пол-глубины), в каких то случаях перебалансировать, в других — аллоцировать память для нового узла.
Сравниваем с массивом — индексация (одно умножение) и один доступ в память на запись. Ну или если указатель — одно сложение + доступ.
в чем преимущество дерева?
Am0ralist
А вообще, если говорить про вычеркивание — вычеркивают же только кратные простым, кстати. То есть дерево простых чисел уже содержит инфу для дальнейшего вычисления, то есть кратность нужно проверять лишь с уже найденными простыми.
а вот как сегментировать весь массив, если для вычеркивания мы должны каждый раз перебрать его весь с заданным шагом n?
ну, чтоб не работать с терабайтом чисел.
Am0ralist
и да, чем лучше — без понятия. просто вопрос был как найти)
Am0ralist
хотя есть мысль, если создать массив на n элементов и его итеративно изменять k раз, после чего по каждому уже найденному простому вычеркнуть, каждый раз сохраняя невычеркнутое в итоге в список простых.
память будет жрать удвоенный массив простых чисел и наперёд известный по размеру массив для вычислений…
ушел спать, ибо брежу уже…
ps. я не программист, я так, учился очень давно и так, балуюсь иногда
orion76
Согласно «следствию» из «алгоритма Эратосфена» получается, что любое НЕпростое число можно представить в виде произведения ПРОСТЫХ чисел.
т.е. чтобы определить, является ли число НЕпростым, достаточно проверить его делимость на несколько первых ПРОСТЫХ чисел в последовательности.
Причем произведение максимального простого числа на минимальное(число 2) должно быть не больше чем проверяемое число. (Как обосновать данное утверждение еще не придумал, но вроде так получается-)
Следовательно, расход памяти:
1.Размер текущего проверяемого числа
2.Структура для хранения найденных ПРОСТЫХ чисел.
3.«память» для проверки делимости очередного числа.
Что-то мне подсказывает, данный алгоритм можно оптимизировать по производительности. Исключение четных чисел — частный случай такой оптимизации.
Так же можно исключить числа кратные 3,5,7 и т.п. т.е. кратные найденным простым числам.
third112 Автор
wataru
Этот алгоритм жрет меньше памяти, да (в log n раз меньше). Но работает за n^2/log^2 n. Для 10^9 вы его уже не дождетесь.
Это именно то самое "неправильное" решето реализованное на ФП в оригинальном топике.
Откуда такая оценка? Вам каждое простое число в любом случае придется проверить на делимость всеми предыдущими простыми. Всего простых n/log n. Значит проверок будет ассимптотически квадрат этого числа.
При оптимизации и проверке только на делимость простых меньше корня текущего, у вас будет оценка n sqrt(n) / log^n. Уже лучше, но все-равно сильно медленее.
А проблемы с потреблением памяти решета решаются очень просто — нужно хранить только кусок большого массива в памяти. При этом придется хранить в памяти все простые до корня из n и вычеркивать их из каждого куска массива отдельно. Так и n=10^12 можно просеять с несколькими мегабайтами памяти.
Am0ralist
wataru
Можно еще удвоить потребление памяти но ускорить работу, если хранить для каждого простого следующее число на вычеркивание.
Лучше всего хранить эти маленькие простые в массиве для локальности. Его можно сразу выделить на sqrt(n) / log(n) * 3. Этого должно хватить для больших n.
Am0ralist
под конец для границы в миллиард — не такие уж и маленькие… unsigned long int минимум, то есть по 4 байта, и второе не меньше. Если выше миллиардов считать, то уже unsigned long long int каждое…
orion76
нет, проверять «квадратом» максимальное простое число для текущего проверяемого — перебор.
достаточно чтобы произведение текущего простого числа на минимальное простое число было больше текущего проверяемого числа.
но тут можно еще оптимизировать.
интуиция подсказывает, что как только сумма двух последних простых чисел больше проверяемого, проверку можно заканчивать(поиск делителя проверяемого числа в массиве найденных простых чисел, отсортированному по возрастанию)
вот в общем-то алгоритм (typescript):
third112 Автор
Смотрю делимость на 3 нечетных чисел. В дерево попадает 25. Но это не простое число делится на 5. И часто нужна балансировка, т.к. числа будут добавляться в возрастающем порядке, и дерево будет вырождаться в линейный список с максимальным временем поиска. М.б. сохранять несколько чисел в буфере, а потом добавлять в дерево случайнным образом?
MarazmDed
Про дерево я сморозил глупость. Это тоже напоминание о том, что сперва нужно подумать, а потом — писать :)
Проблема в том, что у любого алгоритма есть свои ограничения.
И если в исходных текстах массив на миллиард элементов — выглядит вполне безобидно, то в скомпилированной программе — это будет сильно. Если вы приводите примеры с такими размерностями, то не мешает задуматься о структурах данных. Например, делить целиковый диапазон на поддиапазоны. Или поискать более экономный по памяти алгоритм.
third112 Автор
Не понял: 1 гиг — это много для среднего современного ПК? В достаточно крупной задаче есть чего мерять, а при N=200 измерять будет проблематично ;)
MarazmDed
А у вас в программе одна единственная структура данных? :) Программа работает в изолированной среде? Ну и потом, а что если ваши аппетиты вырастут и будет не миллиард, а триллион. Аккуратнее надо с числами. Понятно, что пример — учебный. Но в этом и есть проблема. Студенты учатся на учебных примерах и о таких вопросах начинают задумываться не в ВУЗе, а на реальной работе, после десятка-другого неудачных экспериментов. В вашем случае, какие-никакие проверки на память просятся.
1гиг — это еще сильно зависит от реализации. Если бы вы тоже самое писали на c++, то это было бы 4гига. А это уже фатально :)
Битовые маски — это как раз то решение, которое вам имеет смысл использовать. Для дельфи в 8 раз память с экономите. Для плюсов — в 32 раза.
Это вы уже применение к задаче находите. Но задача формулируется не как «нагрузочное тестирование, на примере решета эратосфена», а именно как поиск простых чисел.
NickViz
Нет. sizeof bool = 1 в сях и плюсах. 1 байт. можно ужать в бит, но пострадает скорость доступа к этому счастью.
опять же — нет. типичный комп сейчас имеет 8GB рамы. у программеров 16-32 и более.
мой пример — дома — ноуты 3шт. все по 8ГБ, стационарник — 16. на работе 32гига. не потому, что прям вот всё задействовано, а потому, что меньше не ставят уже.
MarazmDed
Не байт, а char. :) sizeof возвращает размер не в байтах, а в char'ах. А размер char'а не обязан быть 1 байт. Т.е. bool в плюсах у вас может спокойно занимать 4 байта.
Если постараться, то скорость пострадает у вас не сильно.
Если у вас на компе 8Gb, и вы отдаете тут же половину непонятно куда, то отзывчивость вашей системы пострадает ой как сильно. Если у вас x32 (что, слава богу, уже редкость), то вы получите прямой выкидыш по памяти. И это еще вопрос, в x64 вы компилируетесь или в x32. Т.е. даже на 64битной системе можете получить выкидыш.
NickViz
честно говоря, кроме редких DSP не встречал процов с char более байта. но вы правы, может такое быть.
На интел 32-бит — мертво. 64-бит помимо памяти дают ещё дофига регистров, и это видно в тяжелых задачах даже на глаз. так что сейчас компилять в 32-бит — смысла никакого. только для легаси и/или 100 лет поддержки. За последние 5 лет у меня только один проект был 32-бит — и то для XP — пром.оборудование, другую ос не поставить.
не, вы мыслите в категориях разумной достаточности. т.е. если есть 8 гиг то это было сделано для дела, память на 80% используется и 4 отожрать — тормоза. Сейчас не так. У меня из 8 гигов 5 свободны (2 кеш пользует, 3 совсем свободны). выделить 4 — я не замечу. И именно поэтому ставят много памяти — что бы не встало колом, когда кто то жирный в память залезет. ну и дешевая она. была бы дорогая — сидели бы на гиге и хромом не пользовались. мои первые 16мегов я за $600 купил… эх времена были… зато Windows 95 летала :-)
third112 Автор
Буду, нпр., искать грант на покупку/аренду нужного железа ;)
Много лет назад участвовал в международном конкурсе Интел (не для студеньов, а дл профи). Все задачи были на грани возможностей тогдашнего железа.
Но цель поиска в формулировке отсутствует.
MarazmDed
Первое, с чего вы начнете, это попытаться оптимизировать алгоритм и выжать максимум из железа, как я понимаю :)
third112 Автор
Не факт. Все зависит от конкретной задачи.
Am0ralist
а тут и хватит линейного списка в две переменных, массив промежуточный ограниченный на число и флаг вычеркнут или нет и всё это в несколько итераций…
masai
Кстати, плотность простых чисел падает относительно медленно. Количество простых чисел до n приблизительно равно n / ln n для больших n.
MarazmDed
Перестройка тоже разная бывает. Если задействовано 3 элемента — то ерунда. Ну вставка записей даже в огромную БД не скажу, что прям лагает. Т.е. решаемо.
gaidukav
Если мы начнём искать простые с начала числового ряда — дерево потребуется перебалансировать довольно часто, т.к. каждое следующее число будет больше предыдущего.
Но если искать простые с двух сторон поочерёдно:
1, N, 2, N-1, 3, N-2 и т.д.
дерево будет собираться более-менее равномерно, и возможно, количество перебалансировок дерева будет минимальным.
Мне так кажется…
MarazmDed
Да, это все хорошо. Проблема в другом :) Меня — заглючило. Решето Эратосфена — про массивы, а не про деревья. Сам алгоритм предполагает, что есть массив. И процесс поиска — это вычеркивание пометок. Эратосфен, думаю, не предполагал, что людям придется вычислять триллион первых простых чисел :), поэтому алгоритм занимает O(n) памяти.
Другое дело, что конструкция array [2..1000000000] of boolean — далеко не самый удачный вариант. А решить можно по разному:
1) разбить лярд на диапазоны сильно скромнее
2) Использовать более сложные структуры данных, например std::vector (TArray)
3) использовать битовые маски.
4) не использовать решето Эратосфена для больших размерностей.
gaidukav
Думаю, что для алгоритма «Решета» не требуется исходный массив с числовым рядом от 1 до N, достаточно крутить цикл от 1 до N, проверяя каждое i на «Эратосфенность», и складывая истинные результаты в массив, дерево или список.
Нам ведь не требуется после проверки очередного числа возвращаться к ранее проверенным элементам ряда для их «перепроверки». По этому исходный массив — пустая трата памяти.
MarazmDed
Меня тоже поначалу на этом заглючило. Нет, число не проверяется на эратосфенность. Просто для каждого простого числа вычеркиваются все числа, кратные ему. Сходу не могу придумать подходящую структуру данных, чтобы алгоритм не кушал память. Единственный вменяемый вариант — битовые маски, которые сокращают потребление памяти в 8 раз.
wataru
Еще можно сегментировать массив. Если хранить дополнительно все простые числа до sqrt(n) — то можно вычеркивать числа из массива отдельно в каждом куске размера sqrt(n) и хранить в памяти только текущее "окно".
third112 Автор