jak dowiedzieć się, dlaczego to rozwiązanie jest tak powolne. Czy są jakieś polecenia, które mówią mi, gdzie spędza się większość czasu obliczeń, aby wiedzieć, która część mojego programu haskell działa wolno?
Dokładnie! GHC zapewnia wiele doskonałych narzędzi, w tym:
Samouczek na temat korzystania z profilowania w czasie i przestrzeni jest częścią Real World Haskell .
Statystyki GC
Po pierwsze, upewnij się, że kompilujesz z ghc -O2. I możesz się upewnić, że jest to nowoczesny GHC (np. GHC 6.12.x)
Pierwszą rzeczą, jaką możemy zrobić, jest sprawdzenie, czy czyszczenie pamięci nie stanowi problemu. Uruchom swój program z + RTS -s
$ time ./A +RTS -s
./A +RTS -s
749700
9,961,432,992 bytes allocated in the heap
2,463,072 bytes copied during GC
29,200 bytes maximum residency (1 sample(s))
187,336 bytes maximum slop
**2 MB** total memory in use (0 MB lost due to fragmentation)
Generation 0: 19002 collections, 0 parallel, 0.11s, 0.15s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 13.15s ( 13.32s elapsed)
GC time 0.11s ( 0.15s elapsed)
RP time 0.00s ( 0.00s elapsed)
PROF time 0.00s ( 0.00s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 13.26s ( 13.47s elapsed)
%GC time **0.8%** (1.1% elapsed)
Alloc rate 757,764,753 bytes per MUT second
Productivity 99.2% of total user, 97.6% of total elapsed
./A +RTS -s 13.26s user 0.05s system 98% cpu 13.479 total
Co już daje nam wiele informacji: masz tylko stertę 2M, a GC zajmuje 0,8% czasu. Nie musisz się więc martwić, że problemem jest alokacja.
Profile czasowe
Uzyskanie profilu czasowego dla twojego programu jest proste: skompiluj z -prof -auto-all
$ ghc -O2 --make A.hs -prof -auto-all
[1 of 1] Compiling Main ( A.hs, A.o )
Linking A ...
A dla N = 200:
$ time ./A +RTS -p
749700
./A +RTS -p 13.23s user 0.06s system 98% cpu 13.547 total
który tworzy plik A.prof zawierający:
Sun Jul 18 10:08 2010 Time and Allocation Profiling Report (Final)
A +RTS -p -RTS
total time = 13.18 secs (659 ticks @ 20 ms)
total alloc = 4,904,116,696 bytes (excludes profiling overheads)
COST CENTRE MODULE %time %alloc
numDivs Main 100.0 100.0
Wskazuje, że cały czas spędzasz w numDivs i jest to również źródło wszystkich twoich przydziałów.
Profile sterty
Możesz również uzyskać zestawienie tych przydziałów, uruchamiając + RTS -p -hy, co tworzy A.hp, który można wyświetlić, konwertując go do pliku postscriptowego (hp2ps -c A.hp), generując:
co mówi nam, że nie ma nic złego w używaniu pamięci: alokuje ona w stałej przestrzeni.
Więc twoim problemem jest złożoność algorytmiczna numDivs:
toInteger $ length [ x | x<-[2.. ((n `quot` 2)+1)], n `rem` x == 0] + 2
Napraw to, co stanowi 100% twojego czasu pracy, a wszystko inne jest łatwe.
Optymalizacje
To wyrażenie jest dobrym kandydatem do optymalizacji fuzji strumienia , więc przepiszę je, aby używał Data.Vector , na przykład:
numDivs n = fromIntegral $
2 + (U.length $
U.filter (\x -> fromIntegral n `rem` x == 0) $
(U.enumFromN 2 ((fromIntegral n `div` 2) + 1) :: U.Vector Int))
Które powinny zostać połączone w jedną pętlę bez zbędnych alokacji sterty. Oznacza to, że będzie miał większą złożoność (według stałych czynników) niż wersja listy. Możesz użyć narzędzia ghc-core (dla zaawansowanych użytkowników), aby sprawdzić kod pośredni po optymalizacji.
Testując to, ghc -O2 --make Z.hs
$ time ./Z
749700
./Z 3.73s user 0.01s system 99% cpu 3.753 total
Więc skrócił czas działania dla N = 150 o 3,5x, bez zmiany samego algorytmu.
Wniosek
Twój problem to numDivs. Zajmuje 100% czasu pracy i ma straszną złożoność. Pomyśl o numDivs i jak, na przykład, dla każdego N generujesz [2 .. n div
2 + 1] N razy. Spróbuj to zapamiętać, ponieważ wartości się nie zmieniają.
Aby zmierzyć, która z funkcji jest szybsza, rozważ zastosowanie kryterium , które zapewni statystycznie wiarygodne informacje o poprawie czasu działania poniżej mikrosekundy.
Uzupełnienia
Ponieważ numDivs to 100% twojego czasu pracy, dotykanie innych części programu nie zrobi dużej różnicy, jednak ze względów pedagogicznych możemy również przepisać te za pomocą fuzji strumieniowej.
Możemy również przepisać trialList i polegać na fusion, aby przekształcić ją w pętlę, którą piszesz ręcznie w trialList2, która jest funkcją „skanowania prefiksów” (aka scanl):
triaList = U.scanl (+) 0 (U.enumFrom 1 top)
where
top = 10^6
Podobnie dla sol:
sol :: Int -> Int
sol n = U.head $ U.filter (\x -> numDivs x > n) triaList
Z takim samym ogólnym czasem działania, ale nieco czystszym kodem.
time
narzędzie, o którym Don wspomniał w Time Profiles, to tylkotime
program dla Linuksa . Nie jest dostępny w systemie Windows. Więc jeśli chodzi o profilowanie czasu w systemie Windows (gdziekolwiek), zobacz to pytanie.