Haskell стиль / эффективность - PullRequest
Новая
       37

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

6 голосов
/ 22 мая 2009

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

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.

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

Ответы [ 2 ]

9 голосов
/ 22 мая 2009

Зачем нужен второй аргумент для 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-ish), 

   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]}
...

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

1 голос
/ 22 мая 2009

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

...