краткий ответ: счетное сито работает медленнее, чем сито Тернера (также известное как «наивное»), потому что оно имитирует прямой доступ к ОЗУ с последовательным счетом, что заставляет его проходить по потокам не просмотрено между этапами разметки. Это иронично, потому что счет делает его "подлинным" ситом Эратосфена, в отличие от сита пробного деления Тернера. На самом деле удаление кратных, как это делает сито Тернера, может испортить счет.
Оба алгоритма работают очень медленно, потому что они запускают работу по удалению кратных чисел слишком рано с каждого найденного простого числа вместо его квадрата, создавая, таким образом, слишком много ненужных этапов обработки потока (будь то фильтрация или маркировка) - вместо этого O(n) из них всего ~ 2*sqrt n/log n при получении простых чисел до n. Проверка на кратность 7 не требуется, пока во входных данных не появится 49.
Этот ответ объясняет, как sieve можно рассматривать как построение конвейера потоковых "преобразователей" позади себя, поскольку он работает :
[2..] ==> sieve --> 2
[3..] ==> mark 1 2 ==> sieve --> 3
[4..] ==> mark 2 2 ==> mark 1 3 ==> sieve
[5..] ==> mark 1 2 ==> mark 2 3 ==> sieve --> 5
[6..] ==> mark 2 2 ==> mark 3 3 ==> mark 1 5 ==> sieve
[7..] ==> mark 1 2 ==> mark 1 3 ==> mark 2 5 ==> sieve --> 7
[8..] ==> mark 2 2 ==> mark 2 3 ==> mark 3 5 ==> mark 1 7 ==> sieve
[9..] ==> mark 1 2 ==> mark 3 3 ==> mark 4 5 ==> mark 2 7 ==> sieve
[10..]==> mark 2 2 ==> mark 1 3 ==> mark 5 5 ==> mark 3 7 ==> sieve
[11..]==> mark 1 2 ==> mark 2 3 ==> mark 1 5 ==> mark 4 7 ==> sieve --> 11
Решето Тернера использует nomult p = filter ((/=0).(`rem`p)) вместо mark _ p записей, но в остальном выглядит так же:
[2..] ==> sieveT --> 2
[3..] ==> nomult 2 ==> sieveT --> 3
[4..] ==> nomult 2 ==> nomult 3 ==> sieveT
[5..] ==> nomult 2 ==> nomult 3 ==> sieveT --> 5
[6..] ==> nomult 2 ==> nomult 3 ==> nomult 5 ==> sieveT
[7..] ==> nomult 2 ==> nomult 3 ==> nomult 5 ==> sieveT --> 7
[8..] ==> nomult 2 ==> nomult 3 ==> nomult 5 ==> nomult 7 ==> sieveT
Каждый такой преобразователь может быть реализован как закрывающий фрейм (он же «преобразователь») или как генератор с изменяемым состоянием, что не имеет значения. Продукция каждого такого производителя поступает непосредственно в качестве входных данных для его преемника в цепочке. Здесь нет неоцененных преобразователей, каждый вынужден своим потребителем производить следующий результат.
Итак, чтобы ответить на ваш вопрос,
Я подозреваю, что это как-то связано с повторением каждого элемента в списке в функции отметки.
да, точно. В противном случае они оба используют схемы без отсрочки.
Таким образом, код можно улучшить, отложив начало маркировки потока:
primes = 2:3:filter (>0) (sieve [5,7..] (tail primes) 9)
sieve (x:xs) ps@ ~(p:t) q
| x < q = x:sieve xs ps q
| x==q = sieve (mark xs 1 p) t (head t^2)
where
mark (y:ys) k p
| k == p = 0 : (mark ys 1 p) -- mark each p-th number in supply
| otherwise = y : (mark ys (k+1) p)
Теперь он работает на уровне чуть выше O(k^1.5), эмпирически, в k произведенных простых числах. Но зачем считать по единицам, если мы можем считать по инкрементам. (Каждое третье нечетное число из 9 можно найти, снова и снова добавляя 6.) И затем вместо того, чтобы отмечать, мы можем сразу отсеять числа, получив добросовестное сито Эратосфена (пусть и не самое эффективное):
primes = 2:3:sieve [5,7..] (tail primes) 9
sieve (x:xs) ps@ ~(p:t) q
| x < q = x:sieve xs ps q
| x==q = sieve (weedOut xs (q+2*p) (2*p)) t (head t^2)
where
weedOut i@(y:ys) m s
| y < m = y:weedOut ys m s
| y==m = weedOut ys (m+s) s
| y > m = weedOut i (m+s) s
Это выполняется при более чем O(k^1.2) в k простых числах, быстрое и грязное тестирование, скомпилированное и загруженное в GHCi, дает до 100-150 тысяч простых чисел, ухудшается до O(k^1.3) при примерно 0,5 миллиона простых чисел.
Так какого же ускорения это достигается? Сравнивая код OP с ситом Тернера из "Википедии",
primes = sieve [2..] :: [Int]
where
sieve (x:xs) = x : sieve [y | y <- xs, rem y x /= 0]
было 8x ускорение W / OP до 2k (т. е. производилось 2000 простых чисел). Но при 4k это было 15x ускорение. Сито Тернера, кажется, работает с примерно O(k^1.9 .. 2.3) эмпирической сложностью при получении k = 1000 .. 6000 простых чисел, а счетное сито - с O(k^2.3 .. 2.6) для того же диапазона.
Для двух версий, представленных здесь в этом ответе, v1 / W был дополнительно 20x быстрее на 4k, а 43x на 8k . v2 / v1 был 5.2x на 20k, 5.8x при 40k и 6.5x быстрее при производя 80 000 простых чисел.
(для сравнения, код очереди приоритетов Мелиссы О'Нил работает с эмпирической сложностью примерно O(k^1.2), получено k простых чисел. Конечно, он масштабируется намного лучше, чем приведенный здесь код).
Вот решето из определения Эратосфена:
P = {3, 5, ...} \ {{p * p , p * p + 2 * p, ...} | p в P}
Ключ к эффективности Решета Эратосфена - это прямое генерирование кратных простых чисел путем подсчета с приращением (двойного) значения простого числа от каждого простого числа; и их прямое исключение, что стало возможным благодаря объединению значения и адреса, как и в алгоритмах целочисленной сортировки (возможно только с изменяемыми массивами). Неважно, должен ли он производить заданное количество простых чисел или работать бесконечно, потому что он всегда может работать по сегментам.
person
Will Ness
schedule
31.07.2012
