Haskell стиль / эффективность
Поэтому я работал над способом ленивого генерирования простых чисел и придумал эти три определения, которые все работают эквивалентным образом - просто проверяя, есть ли у каждого нового целого числа фактор среди всех предыдущих простых чисел:
primes1 :: [Integer]
primes1 = mkPrimes id [2..]
where mkPrimes f (x:xs) =
if f (const True) x
then
let g h y = y `mod` x > 0 && h y in
x : mkPrimes (f . g) xs
else
mkPrimes f xs
primes2 :: [Integer]
primes2 = mkPrimes id (const True) [2..]
where mkPrimes f f_ (x:xs) =
if f_ x
then
let g h y = y `mod` x > 0 && h y in
x : mkPrimes (f . g) ( f $ g $ const True) xs
else
mkPrimes f f_ xs
primes3 :: [Integer]
primes3 = mkPrimes [] [2..]
where mkPrimes ps (x:xs) =
if all (\p -> x `mod` p > 0) ps
then
x : mkPrimes (ps ++ [x]) xs
else
mkPrimes ps xs
Так мне кажетсяprimes2
должно быть немного быстрее, чемprimes1
, поскольку это позволяет избежать пересчетаf_ = f (const True)
за каждое целое число (которое ядумать требует работы порядка порядка простых чисел, которые мы уже нашли), и обновляет его только тогда, когда мы сталкиваемся с новым простым числом.
Просто из ненаучных тестовtake 1000
в ghci) похожеprimes3
работает быстрее чемprimes2
.
Должен ли я извлечь из этого урок и предположить, что, если я могу представить функцию как операцию над массивом, я должен реализовать ее последним способом для повышения эффективности, или здесь что-то еще происходит?