Решето времени исполнения Эратосфена в haskell

Я новичок в Haskell и писал код для решения проблемы решета Эратосфена с использованием списков. Вот код

primes m = 2 : primes' m [3,5 ..m] [] where
primes' m integers@(p : xs) acc   | p*p>m =  reverse acc ++ integers
                                  | True  = primes' m (xs `remove` [p*p, p*p+2*p..m]) (p:acc)

remove integers@(x:xs) multiples@(y:ys) | x < y = x : remove xs multiples
                                        | x == y =    remove xs ys
                                        | x > y =     remove integers ys

remove integers multiples = integers

Если я ввожу m = 2000000, коду требуется около 14 секунд, чтобы распечатать все результаты. Я думаю, что 90 процентов времени уходит на печать, а не на выполнение кода. Есть ли способ найти правильное время выполнения для этой конкретной программы?


performance functional-programming execution-time haskell sieve-of-eratosthenes
person Awsaf Rahman Protic    schedule 20.06.2018    source источник
comment
Я не эксперт по Haskell, но ваш remove выглядит так, будто ему нужно пройти через все неудаленные числа. Настоящее сито Эратосфена может прыгать прямо к флагам для чисел, которые оно помечает составными, что намного быстрее. Эмпирическое правило: если нет массива логических флагов, это, вероятно, не решето Эратосфена.   -  person user2357112 supports Monica    schedule 20.06.2018
comment
@ user2357112 это спорно. Я думаю, что суть SoE заключается в генерации композитов из каждого простого числа путем повторного приращения. то, как эти кратные затем пропускаются, зависит от конкретной реализации. remove ОП - это Data.List.Ordered.minus. конечно, у массивов есть преимущество произвольного доступа, но реализация с упорядоченными списками может иметь только дополнительный логарифмический фактор в сложности. подробнее здесь.   -  person Will Ness    schedule 21.06.2018
comment
remove действительно проходит все числа, но итерация останавливается раньше, на кв. м. верхнего предела. так что в целом это примерно primesTo m = foldl minus [3,5..] [[p*p, p*p+2*p..m] | p <- takeWhile ((<= m) . (^2)) primes]. Который, как показывает Мелисса О'Нил в своей статье JFP, имеет сложность чуть выше n ^ 1,5.   -  person Will Ness    schedule 21.06.2018
comment
@WillNess: Несмотря на то, что он выполняет те же повторяющиеся приращения, что и SoE, я бы посчитал этот алгоритм гораздо более близким к пробному делению, поскольку ему нужно рассматривать каждое число один раз для каждого простого числа до его первого делителя, а не один раз для каждого простого делителя. Мелисса О'Нил также твердо убеждена в том, что выполнение приращений вместо деления не превращает пробное деление в SoE в документ Я думаю, вы имеете в виду. (Кроме того, вау, вы редактировали эту вики-страницу 550 раз за десятилетие.)   -  person user2357112 supports Monica    schedule 21.06.2018
comment
Тем не менее, я не считаю массив флагов строго необходимым для решета Эратосфена, но для кода, который люди пишут при первой попытке решета, эмпирическое правило работает довольно хорошо.   -  person user2357112 supports Monica    schedule 21.06.2018
comment
эта бумага была для меня очень запутанной, за исключением математики в ней. тут конечно нет пробных делений. если этот foldl-код (...(((xs -a)-b)-c)-...) превратить в foldr-based (xs -(a+(b+(c+...)))), и если, далее, сумма будет найдена в виде дерева, а не списка, то сложность будет всего в log N раз хуже, чем решето случайного доступа (то же самое как на основе PQ в статье, кстати). Насколько нам известно, сам Эратосфен считал единицами. :) здесь по крайней мере каждое перечисление напрямую находит каждое следующее кратное, добавляя 2*p, а не добавляя 1 2p раз. Так что я считаю это настоящим решетом.   -  person Will Ness    schedule 21.06.2018
comment
Давайте продолжим это обсуждение в чате.   -  person Will Ness    schedule 21.06.2018

Ответы (1)


arrow_upward
3
arrow_downward

Попробуйте с

main = print $ last $ primes 2000000

поэтому он покажет вам только последнее найденное простое число.

Скомпилируйте его с помощью -O2 и запустите с помощью +RTS -s, чтобы увидеть общие тайминги и статистику памяти.

Обязательно измерьте его в нескольких точках размера, чтобы узнать эмпирические порядки роста. ! Настоящие сита работают примерно при ~ n^1.1, производя n простых чисел. Все до ~ n^1.5 приемлемо. ~ n^2 плохо, медленнее еще хуже. :)

С твоим должно быть все в порядке, судя по всему.

person Will Ness    schedule 20.06.2018