Стиль/эффективность Haskell

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

Просто из ненаучных тестов (запуск take 1000 в ghci) вроде как primes3 работает быстрее, чем primes2.

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

Answer 1

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

...
            let g y = f y && y `mod` x > 0 in
            x : mkPrimes g xs
...

import Control.Arrow  -- instance Monad (-> r)
import Control.Monad  -- liftM2
(.&&.) = liftM2 (&&)
...
            let g y = y `mod` x > 0 in
            x : mkPrimes (f .&&. g) xs
...

---

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

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

В вашем случае вполне вероятно, что накладные расходы на создание каждого 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).Бег (++) линейна по длине левого аргумента, но постоянна по длине правого аргумента.