Сито Эратосфена в Хаскеле

Question

Я решаю некоторые классические проблемы в Haskell, чтобы развить свои функциональные навыки, и у меня есть проблема для реализации оптимизации, предложенной на этом "Programming Praxis" сайте:

У меня триРешения этой проблемы, а третий слишком медленный по сравнению со вторым решением.Может кто-нибудь предложить некоторые улучшения в моем коде?

Мои реализации:

-- primeira implementação
primes n
    | n < 2 = []
    | n == 2 = [2]
    | n `mod` 2 == 0 = primes'
    | otherwise = if (find (\x -> n `mod` x == 0) primes') == Nothing then
                      n:primes'
                  else
                      primes'
    where primes' = primes (n - 1)

-- segunda implementação
primes' :: Integer -> [Integer]
primes' n = sieve $ 2 : [3,5..n]
    where sieve :: [Integer] -> [Integer]
          sieve [] = []
          sieve l@(x:xs)
              | x*x >= n = l
              | otherwise = x : sieve list'
              where list' = filter (\y -> y `mod` x /= 0) xs

-- terceira implementação
primes'' :: Integer -> [Integer]
primes'' n = 2 : sieve 3 [3,5..n]
    where sieve :: Integer -> [Integer] -> [Integer]
          sieve _ [] = []
          sieve m l@(x:xs)
              | m*m >= n = l
              | x < m*m = x : sieve m xs
              | otherwise = sieve (m + 2) list'
              where list'= filter (\y -> y `mod` m /= 0) l

Answer 1

Похоже, проблема с вашей третьей ревизией заключается в том, как вы выбираете следующий элемент для просеивания. Вы без разбора увеличиваете на 2. Проблема в том, что вы затем просеиваете ненужные числа. например, в этой версии вы в конечном итоге будете передавать 9 как m, и вы будете делать дополнительную рекурсию для фильтрации на 9, даже если ее нет даже в списке, и, следовательно, вы никогда не должны были выбирать ее в первое место (поскольку оно было бы удалено в самом первом фильтре на 3)

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

Другими словами, я думаю, что вы в конечном итоге просеиваете каждое нечетное число от 3 до n. Вместо этого вы должны просеивать каждое нечетное число, которое еще не было удалено предыдущим проходом.

Я думаю, что для правильной реализации оптимизации запуска сита в квадрате текущего значения просеивания, вы должны сохранить переднюю часть списка при просеивании сзади, где задняя часть содержит элементы> = квадрат значения просеивания , Я думаю, что это заставит вас использовать конкатенации, и я не уверен, что оптимизация достаточно хороша, чтобы отменить накладные расходы, вызванные использованием ++.

Answer 2

Прежде всего, mod медленный, поэтому используйте rem в ситуациях, когда это не имеет значения (когда вы не имеете дело с негативами, в основном).Во-вторых, используйте Критерий , чтобы показать (себе), что быстрее и какие изменения на самом деле являются оптимизацией.Я знаю, что я не даю вам полного ответа на этот вопрос, но это хорошее место для вас (и других потенциальных ответчиков), чтобы начать, так что вот некоторый код:

import List
import Criterion.Main

main = do
  str <- getLine
  let run f = length . f
      input = read str :: Integer
  defaultMain   [ bench "primes" (nf (run primes) input)
                , bench "primes'" (nf (run primes') input)
                , bench "primes''" (nf (run primes'') input)
                , bench "primesTMD" (nf (run primesTMD) input)
                , bench "primes'TMD" (nf (run primes'TMD) input)
                , bench "primes''TMD" (nf (run primes''TMD) input)
                ]
  putStrLn . show . length . primes'' $ (read str :: Integer)

-- primeira implementação
primes n
    | n < 2 = []
    | n == 2 = [2]
    | n `mod` 2 == 0 = primes'
    | otherwise = if (find (\x -> n `mod` x == 0) primes') == Nothing then
                      n:primes'
                  else
                      primes'
    where primes' = primes (n - 1)

primesTMD n
    | n < 2 = []
    | n == 2 = [2]
    | n `mod` 2 == 0 = primes'
    | otherwise = if (find (\x -> n `rem` x == 0) primes') == Nothing then
                      n:primes'
                  else
                      primes'
    where primes' = primesTMD (n - 1)

-- segunda implementação
primes' :: Integer -> [Integer]
primes' n = sieve $ 2 : [3,5..n]
    where sieve :: [Integer] -> [Integer]
          sieve [] = []
          sieve l@(x:xs)
              | x*x >= n = l
              | otherwise = x : sieve list'
              where list' = filter (\y -> y `mod` x /= 0) xs

primes'TMD :: Integer -> [Integer]
primes'TMD n = sieve $ 2 : [3,5..n]
    where sieve :: [Integer] -> [Integer]
          sieve [] = []
          sieve l@(x:xs)
              | x*x >= n = l
              | otherwise = x : sieve list'
              where list' = filter (\y -> y `rem` x /= 0) xs

-- terceira implementação
primes'' :: Integer -> [Integer]
primes'' n = 2 : sieve 3 [3,5..n]
    where sieve :: Integer -> [Integer] -> [Integer]
          sieve _ [] = []
          sieve m l@(x:xs)
              | m*m >= n = l
              | x < m*m = x : sieve m xs
              | otherwise = sieve (m + 2) list'
              where list'= filter (\y -> y `mod` m /= 0) l

primes''TMD :: Integer -> [Integer]
primes''TMD n = 2 : sieve 3 [3,5..n]
    where sieve :: Integer -> [Integer] -> [Integer]
          sieve _ [] = []
          sieve m l@(x:xs)
              | m*m >= n = l
              | x < m*m = x : sieve m xs
              | otherwise = sieve (m + 2) list'
              where list'= filter (\y -> y `rem` m /= 0) l

Обратите внимание на улучшенное время выполнениявариантов, использующих rem:

 $ ghc --make -O2 sieve.hs
 $./sieve
 5000
 ...
 benchmarking primes 
 mean: 23.88546 ms, lb 23.84035 ms, ub 23.95000 ms

 benchmarking primes'
 mean: 775.9981 us, lb 775.4639 us, ub 776.7081 us

 benchmarking primes''
 mean: 837.7901 us, lb 836.7824 us, ub 839.0260 us

 benchmarking primesTMD
 mean: 16.15421 ms, lb 16.11955 ms, ub 16.19202 ms

 benchmarking primes'TMD
 mean: 568.9857 us, lb 568.5819 us, ub 569.4641 us

 benchmarking primes''TMD
 mean: 642.5665 us, lb 642.0495 us, ub 643.4105 us

Хотя я вижу, что вы делаете это для своего собственного образования, стоит отметить соответствующие ссылки простых чисел на Haskell.org и быстрый Пакет простых чисел при взломе.