Trudno zrozumieć zachowanie przydziału pamięci Haskell

Question

Natknąłem się na Haskella i FP i oszołomiłem się możliwościami. A stary frajer z matematyki nie miał problemu z napisaniem naiwnego kodu dla rzeczywistych użytecznych celów. Jednak pomimo całej lektury wciąż mam problem ze zrozumieniem, jak nie trafić w zaskakujące wąskie gardła wydajności.

Tak więc piszę bardzo krótkie fragmenty kodu z naiwnymi implementacjami, a następnie próbuję trochę zmienić, aby zobaczyć, jak reaguje wydajność. A oto jeden przykład, którego naprawdę nie mogę zrozumieć ... Napisałem tę funkcję, która znajduje rozwiązanie Josephus problem, celowo z implementacją listy naiwnej.

m = 3 
n = 3000 
main = putStr $ "Soldier #" ++ (show $ whosLeft [1..n]) ++ " survived...\n" 

whosLeft [lucky] = lucky 
whosLeft soldiers = whosLeft $ take (length soldiers -1) $ drop m $ cycle soldiers 

Ten ostatni działa w 190 ms, z wydajnością 63% zgodnie z RTS.

Pierwszą rzeczą, którą chciałem wypróbować, było usunięcie (długość żołnierza -1) i zastąpienie go zmniejszającą się liczbą całkowitą.

Czas pracy skoczył do 900 ms, a wydajność spadła do 16% i zużywa 47 razy więcej pamięci niż prostszy kod powyżej! Dodałem więc ścisłą ocenę, wymusiłem typ Int, próbowałem takich rzeczy jak usuwanie zmiennych globalnych i innych, ale nie na wiele się to zdało. I po prostu nie mogę zrozumieć tego spowolnienia.

m = 3::Int 
n = 3000::Int 
main = putStr $ "Soldier #" ++ (show $ whosLeft n [1..n]) ++ " survived...\n" 

whosLeft 1 [lucky] = lucky 
whosLeft n' soldiers = n' `seq` left `seq` whosLeft (n'-1) left 
       where left = take (n'-1) $ drop m $ cycle soldiers 

Przeszukałem artykuły i posty związane z wydajnością, ale po prostu nie wydaje mi się, aby to usłyszeć. Nadal będąc nokajem Haskella, muszę przegapić coś wielkiego ... W jaki sposób ten jeden dodany parametr (przedwczesne obliczenia ...) tak bardzo zmniejsza prędkość?

PS: wiem, czy naprawdę był Józef z 3000 żołnierzy, to nie potrzebowałby do samobójstwa ...

Answer 1

Pierwsze rozwiązanie zmusza cały kręgosłup listy żołnierzy poprzez swoją długość. Drugie rozwiązanie wymusza jedynie (używając) dane o żołnierzach. Wymień left pomiędzy seq s z length left, a otrzymasz swoją wydajność z powrotem.