Projekt Euler 14: wydajność w porównaniu do C i zapamiętywanie

Question

Obecnie pracuję nad project euler problem 14.

Rozwiązałem go przy użyciu słabo zakodowanego programu, bez konieczności zapamiętywania, które trwało przez 5 sekund (patrz edycja), które trwało .

Oto ona:

step :: (Integer, Int) -> Integer -> (Integer, Int) 
step (i, m) n | nextValue > m   = (n, nextValue) 
       | otherwise    = (i, m) 
       where nextValue = syr n 1 

syr :: Integer -> Int -> Int 
syr 1 acc = acc 
syr x acc | even x = syr (x `div` 2) (acc + 1) 
      | otherwise = syr (3 * x + 1) (acc + 1) 

p14 = foldl step (0, 0) [500000..999999] 

Moje pytanie jest o kilka komentarzy w wątku związanego z tym problemem, gdzie wymieniono czasy wykonania < 1 s dla programów jak następuje (kod C, kredytów do projektu Euler forum użytkownik ix kodu - uwaga: nie sprawdzałem, że czas realizacji jest w rzeczywistości, jak wymieniono):

#include <stdio.h> 


int main(int argc, char **argv) { 
    int longest = 0; 
    int terms = 0; 
    int i; 
    unsigned long j; 
    for (i = 1; i <= 1000000; i++) { 
     j = i; 
     int this_terms = 1; 
     while (j != 1) { 
      this_terms++; 
      if (this_terms > terms) { 
       terms = this_terms; 
       longest = i; 
      } 
      if (j % 2 == 0) { 
       j = j/2; 
      } else { 
       j = 3 * j + 1; 
      } 
     } 
    } 
    printf("longest: %d (%d)\n", longest, terms); 
    return 0; 
} 

dla mnie thos Programy e są trochę takie same, mówiąc o algorytmie.

Więc zastanawiam się, dlaczego istnieje tak duża różnica? Czy istnieje jakaś różnica między naszymi dwoma algorytmami, które mogą usprawiedliwiać czynnik x6 w wydajności?

BTW, obecnie próbuję zaimplementować ten algorytm za pomocą memoizacji, ale jestem trochę zagubiony co do mnie, jest to łatwiejsze do zrealizowania w imperatywnym języku (i nie manipuluję jeszcze monadami, więc nie mogę użyj tego paradygmatu). Więc jeśli masz dobry tutorial, który pasuje początkującym do nauki zapamiętania, będę zadowolony (ci, których spotkałem, nie byli wystarczająco szczegółowi lub poza moją ligą).

Uwaga: Doszedłem do paradygmatu deklaratywnego przez Prolog i wciąż znajduję się w bardzo wczesnym procesie odkrywania Haskella, więc mógłbym pominąć ważne rzeczy.

Uwaga 2: wszelkie ogólne porady dotyczące mojego kodu są mile widziane.

EDIT: dzięki pomocy delnan, w skompilowany program, a teraz pracuje w 5 sekund, więc patrzę głównie na wskazówki, memoization NOW (nawet jeśli wyobrażenia o istniejącej luki x6 są nadal mile widziane).

Answer 1

Po skompilowany z optymalizacji, nadal istnieje kilka różnic w programie C

• użyć div, podczas gdy program C wykorzystuje podział maszynowego (który obcina) [ale każdy szanujący przekształca kompilator C na zmianę, dzięki czemu będzie jeszcze szybszy], będzie to quot w Haskell; to zmniejszyło czas pracy o około 15% tutaj.
• program C używa 64-bitowej stałej szerokości (lub nawet 32-bitowej, ale przy odrobinie szczęścia otrzymuje poprawną odpowiedź, ponieważ niektóre wartości pośrednie przekraczają zakres 32-bitowy), program Haskell wykorzystuje dowolną precyzję Integer s. Jeśli masz 64-bitowe Int s w swoim GHC (64-bitowy system operacyjny inny niż Windows), zamień Integer na Int. To zmniejszyło czas pracy o współczynnik około 3 tutaj. Jeśli korzystasz z systemu 32-bitowego, masz pecha, GHC nie używa natywnych instrukcji 64-bitowych, operacje te są realizowane jako wywołania C, które wciąż są dość powolne.

W celu zapamiętania można zlecić go do jednego z pakietów do wymieniania podczas włamań, jedynym, który pamiętam jest data-memocombinators, ale są też inne.Czy można to zrobić samemu, na przykład utrzymując mapę poprzednio obliczonych wartości - które działa najlepiej w State monady,

import Control.Monad.State.Strict 
import qualified Data.Map as Map 
import Data.Map (Map, singleton) 

type Memo = Map Integer Int 

syr :: Integer -> State Memo Int 
syr n = do 
    mb <- gets (Map.lookup n) 
    case mb of 
     Just l -> return l 
     Nothing -> do 
      let m = if even n then n `quot` 2 else 3*n+1 
      l <- syr m 
      let l' = l+1 
      modify (Map.insert n l') 
      return l' 

solve :: Integer -> Int -> Integer -> State Memo (Integer,Int) 
solve maxi len start 
    | len > 1000000 = return (maxi,len) 
    | otherwise = do 
     l <- syr start 
     if len < l 
      then solve start l (start+1) 
      else solve maxi len (start+1) 

p14 :: (Integer,Int) 
p14 = evalState (solve 0 0 500000) (singleton 1 1) 

jednak, że nie będzie prawdopodobnie uzyskać zbyt wiele (nawet jeśli zostały dodane niezbędna surowość). Kłopot w tym, że wyszukiwanie w trybie Map nie jest zbyt tanie, a wstawianie jest stosunkowo kosztowne.

Inną metodą jest zachowanie tablicy zmiennych dla wyszukiwania. Kod staje się bardziej skomplikowany, ponieważ musisz wybrać rozsądne górne ograniczenie wartości do pamięci podręcznej (nie powinno być ono dużo większe niż granica dla wartości początkowych) i radzić sobie z częściami sekwencji leżącymi poza zapamiętanym zakresem. Ale wyszukiwanie tablicy i pisanie są szybkie. Jeśli masz 64-bitowe Int s, poniższy kod działa dość szybko, tutaj zajmuje 0,03s dla limitu 1 miliona, a 0,33 dla limitu 10 milionów, odpowiadający (tak, jak mógłbym rozsądnie) kod C działa w 0,018 lub 0,2 s.

module Main (main) where 

import System.Environment (getArgs) 
import Data.Array.ST 
import Data.Array.Base 
import Control.Monad.ST 
import Data.Bits 
import Data.Int 

main :: IO() 
main = do 
    args <- getArgs 
    let bd = case args of 
       a:_ -> read a 
       _ -> 100000 
    print $ collMax bd 

next :: Int -> Int 
next n 
    | n .&. 1 == 0 = n `unsafeShiftR` 1 
    | otherwise  = 3*n + 1 

collMax :: Int -> (Int,Int16) 
collMax upper = runST $ do 
    arr <- newArray (0,upper) 0 :: ST s (STUArray s Int Int16) 
    let go l m 
      | upper < m = go (l+1) $ next m 
      | otherwise = do 
       l' <- unsafeRead arr m 
       case l' of 
        0 -> do 
         l'' <- go 1 $ next m 
         unsafeWrite arr m (l'' + 1) 
         return (l+l'') 
        _ -> return (l+l'-1) 
     collect mi ml i 
      | upper < i = return (mi, ml) 
      | otherwise = do 
       l <- go 1 i 
       if l > ml 
        then collect i l (i+1) 
        else collect mi ml (i+1) 
    unsafeWrite arr 1 1 
    collect 1 1 2 

Answer 2

Cóż, program C wykorzystuje unsigned long, ale Integer można przechowywać dowolnie dużych liczb całkowitych (jest to bignum). Jeśli importujesz Data.Word, możesz użyć Word, która jest liczbą całkowitą bez znaku maszynowego.

Po wymianie Integer z Word i używając ghc -O2 i gcc -O3 program C działa w 0,72 sekundy, a programy Haskell działa w 1,92 sekundy. 2,6x nie jest zły. Jednak ghc -O2 nie zawsze pomaga, a jest to jeden z programów, na które nie działa! Używanie tylko -O, tak jak Ty, powoduje zmniejszenie czasu wykonywania do 1.90 sekund.

Próbowałem zastąpić div z quot (który używa tego samego rodzaju podziału co C, różnią się one tylko na wejściach ujemnych), ale co dziwne, faktycznie sprawił, że program Haskell działał dla mnie nieco wolniej.

Powinieneś być w stanie przyśpieszyć działanie funkcji syr przy pomocy this previous Stack Overflow question Odpowiadałem na temat tego samego problemu z Projektem Euler.

Answer 3

W moim bieżącym systemie (32-bitowy Core2Duo) twój kod Haskella, zawierający wszystkie optymalizacje podane w odpowiedziach, zabiera 0.8s do kompilacji i 1.2s do uruchomienia.

Można przenieść czas pracy do czasu kompilacji i zmniejszyć czas działania do niemal zera.

module Euler14 where 

import Data.Word 
import Language.Haskell.TH 

terms :: Word -> Word 
terms n = countTerms n 0 
    where 
    countTerms 1 acc    = acc + 1 
    countTerms n acc | even n = countTerms (n `div` 2) (acc + 1) 
        | otherwise = countTerms (3 * n + 1) (acc + 1) 

longestT :: Word -> Word -> (Word, Word) 
longestT mi mx = find mi mx (0, 0) 
    where 
     find mi mx (ct,cn) | mi == mx = if ct > terms mi then (ct,cn) else (terms mi, mi) 
         | otherwise = find (mi + 1) mx 
             (if ct > terms mi then (ct,cn) else (terms mi, mi)) 

longest :: Word -> Word -> ExpQ 
longest mi mx = return $ TupE [LitE (IntegerL (fromIntegral a)), 
           LitE (IntegerL (fromIntegral b))] 
    where 
    (a,b) = longestT mi mx 

i

{-# LANGUAGE TemplateHaskell #-} 
import Euler14 

main = print $(longest 500000 999999) 

W moim systemie zajmuje 2.3s skompilować to jednak run-time spada do 0.003s. Wykonywanie funkcji czasu kompilacji (CTFE) to coś, czego nie można zrobić w C/C++. Jedyny inny język programowania, jaki znam, który obsługuje CTFE to D programming language. I aby być kompletnym, kod C pobiera 0.1s do kompilacji i 0.7s do uruchomienia.