Haskell style/efficiency

Question

Итак, я работал над тем, чтобы лениво генерировать простые числа, и я придумал эти три определения, которые все работают эквивалентным образом - просто проверяя, имеет ли каждое новое целое число фактор среди всех предыдущих штрихи:

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) для любого целого (которое я думаю требует работы по порядку числа простых чисел мы 's найденный до сих пор), и только обновляет его, когда мы enc одурачить новый премьер.

Просто от ненаучных испытаний (бег take 1000 в GHCI), похоже primes3 работает быстрее, чем primes2.

Должен ли я взять из этого урок, и предположу, что, если я могу представить функцию в качестве операции на массиве, что я должен выполнять его последний способ для повышения эффективности, или есть что-то еще здесь происходит ?

Answer 1

Каков второй аргумент в пользу f? На мой взгляд, оба из этих альтернатив более удобным для чтения, и не оказывают существенного влияния на производительность ...

---

Во всяком случае, вернемся к этому вопросу. Иногда использование функций в качестве структур данных является лучшим представлением для определенной задачи, а иногда и нет. «Лучшее» с точки зрения простоты кодирования и «лучшего» с точки зрения производительности не всегда одно и то же. Методика «функции как структуры данных» имеет важное значение для runtime compilation, но эта страница предупреждает,

время выполнения компиляции может иногда выиграть вам существенно повысить эффективность, но часто не может выиграть вам почти ничего на стоимости вашего повышенного стресса и снижение производительности.

В вашем случае, вероятно, что накладные расходы на строительство каждого f :: Integer -> ... -> Bool значительно выше, чем накладные расходы на строительство каждого ps :: [Integer], с небольшим или без разницы при вызове f ... x против all ... ps.

---

Чтобы сжать циклы из бесконечного простого решета, чтобы избавиться от вызовов mod! Целочисленное умножение, деление и модуль намного медленнее, чем целочисленное сложение и вычитание. На моей машине эта реализация работает на 40% быстрее при расчете первых 1000 простых чисел (GHC 6.10.3 -O2).

import qualified Data.Map as M 
primes' :: [Integer] 
primes' = mkPrimes 2 M.empty 
    where 
    mkPrimes n m = case (M.null m, M.findMin m) of 
     (False, (n', skips)) | n == n' -> 
      mkPrimes (succ n) (addSkips n (M.deleteMin m) skips) 
     _ -> n : mkPrimes (succ n) (addSkip n m n) 
    addSkip n m s = M.alter (Just . maybe [s] (s:)) (n+s) m 
    addSkips = foldl' . addSkip 

В действии (с использованием немного JSON-иш синтаксис),

mkPrimes 2 {} 
=> 2 : mkPrimes 3 {4: [2]} 
=> 2 : 3 : mkPrimes 4 {4: [2], 6: [3]} 
=> 2 : 3 : mkPrimes 5 {6: [2, 3]} 
=> 2 : 3 : 5 : mkPrimes 6 {6: [2, 3], 10: [5]} 
=> 2 : 3 : 5 : mkPrimes 7 {8: [2], 9: [3], 10: [5]} 
=> 2 : 3 : 5 : 7 : mkPrimes 8 {8: [2], 9: [3], 10: [5], 14: [7]} 
=> 2 : 3 : 5 : 7 : mkPrimes 9 {9: [3], 10: [2, 5], 14: [7]} 
=> 2 : 3 : 5 : 7 : mkPrimes 10 {10: [2, 5], 12: [3], 14: [7]} 
=> 2 : 3 : 5 : 7 : mkPrimes 11 {12: [2, 3], 14: [7], 15: [5]} 
... 

карта отслеживает будущих мультипликаторов, не используя ничего, кроме того.

Answer 2

Отметьте, что primes3 можно сделать более эффективным, изменив ps++[x] на (x:ps).Пробег (++) является линейным по длине его левого аргумента, но постоянным по длине правого аргумента.