Sito Eratostenesa w Haskell

Question

jestem rozwiązywania kilka klasycznych problemów w Haskell, aby rozwijać swoje umiejętności i funkcjonalne Mam problem wdrożenia optymalizacji sugerowanego w http://programmingpraxis.com/2009/02/19/sieve-of-eratosthenes/

mam trzy „rozwiązania” tego problemu, a trzeci jest zbyt wolny w porównaniu do drugiego rozwiązania. Czy ktoś może zaproponować kilka ulepszeń do mojego kodu?

Moje implementacje są tutaj: http://hpaste.org/40261/sieve_of_eratosthenes

Answer 1

Wygląda na to, że problem z trzecią wersją wygląda tak, jak wybierasz następny element do przesiewania. Ty bezkrytycznie zwiększasz o 2. Problem polega na tym, że przesiewasz niepotrzebne liczby. na przykład, w tej wersji ostatecznie przejdzie 9 jako m, a ty wykonasz dodatkową rekursję, aby filtrować na 9, nawet jeśli nie ma jej nawet na liście, a zatem nie powinieneś jej nigdy wybierać po pierwsze (ponieważ byłby usunięty w pierwszym filtrze na 3)

Mimo że druga wersja nie rozpoczyna filtrowania poza kwadrat numeru, który przesuwa, nigdy nie wybiera niepotrzebnego przesiewania wartość.

Innymi słowy, myślę, że skończy się przesiewanie każdej liczby nieparzystej od 3 do n. Zamiast tego powinieneś przesiać każdą liczbę nieparzystą, która nie została wcześniej usunięta przez poprzednie podanie.

Uważam, że aby prawidłowo zaimplementować optymalizację uruchamiania sita na placu aktualnej wartości sita, należy zachować przód listy podczas przesiewania z tyłu, gdzie z powrotem zawiera elementy> = kwadrat przesiewacza wartość. Myślę, że to zmusiłoby Cię do użycia konkatenacji, i nie jestem pewien, czy optymalizacja jest wystarczająco dobra, aby zlikwidować koszty ogólne wywołane przez ++.

Answer 2

Przede wszystkim mod jest powolny więc używać rem w sytuacjach, w których nie ma znaczenia (gdy nie mamy do czynienia z negatywów, w zasadzie). Po drugie, użyj Criterion, aby pokazać (samemu), co jest szybsze, a jakie zmiany są faktycznie optymalizacjami. Wiem, że nie daję pełną odpowiedź, że pytanie o to, ale jest to dobre miejsce dla ciebie (i inni potencjalni Główni odpowiadający), aby rozpocząć, więc tutaj jest jakiś kod:

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 

Wskazówka ulepszona runtime warianty użyciu 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 

Chociaż widzę, robisz to na własną edukację, warto zauważyć związane z nimi więzi Primes on Haskell.org i szybki Primes package na hackage.