2012-04-02 15 views
8

To jest mój kod do liczenia linii i słowa:Dlaczego ten prosty program do analizy tekstu jest tak wolny?

import System.IO 
import Data.List 
main = do 
     hSetBinaryMode stdin True 
     interact $ (\(w,l)->"line:"++(show l)++"\nwords:"++(show w)++"\n") 
        . foldl' (\(w,l) r-> w `seq` l `seq` (w+length r ,succ l)) (0,0) 
        . lines 

To trwa około 10 sekund, aby uruchomić na pliku około 100 megabajtów. Porównałem go z podobnymi programami w Lua (9s), awk (20s) i wc -l -c (0.6s).

Dlaczego ten kod jest taki wolny? Jaki może być problem?

+0

czy kompilowałeś z opcją -O2? –

+0

tak, -O2 faktycznie po prostu przyspieszyć około 0.xx sekund – vzex

+4

Spróbuj użyć ByteString: http://stackoverflow.com/questions/9746352/parsing-large-log-files-in-haskell –

Odpowiedz

15

We/wy z String jest mniej niż szybki w Haskell. Bajty odczytane z uchwytu generalnie muszą zostać przekonwertowane na punkty kodowe Unicode, a następnie na nich zbudowana jest lista połączona. To dużo pracy, która powoduje dużo alokacji. W takim przypadku konwersja do punktów kodowych jest nieco prostsza, ponieważ ustawiasz tryb stdin na binarny, ale budowa listy połączonych znaków wymaga jeszcze wiele czasu.

Innym małym czynnikiem jest to, że liczba linii używa Integer, ale jest to niewielka i odgrywa znaczącą rolę tylko wtedy, gdy we/wy działa.

Jeśli potrzebujesz szybkiego wejścia/wyjścia, musisz użyć typu lepiej do tego przystosowanego. Jedną z możliwości jest użycie ByteString np

import Data.List 
import qualified Data.ByteString.Lazy.Char8 as C 
main = do 
     txt <- C.getContents 
     putStrLn $ (\(w,l)->"line:"++(show l)++"\nwords:"++(show w)++"\n"). foldl' (\(w,l) r-> w `seq` l `seq` (w+C.length r ,succ l)) (0,0) . C.lines $ txt 

spełnia swoje zadanie na plik 94MB w 0.12s na moim oknie (wc -l -c zajmuje 0.06s), podczas gdy oryginalna użyciu String wziął 4.4s. To może być zoptymalizowane dalej,

{-# LANGUAGE BangPatterns #-} 
import Data.List 
import qualified Data.ByteString.Lazy.Char8 as C 
main = do 
     txt <- C.getContents 
     putStrLn $ (\(w,l)->"line:"++(show l)++"\nwords:"++(show w)++"\n"). loop 0 0 . C.lines $ txt 

loop :: Int -> Int -> [C.ByteString] -> (Int,Int) 
loop !w !l (ln:lns) = loop (w + fromIntegral (C.length ln)) (l+1) lns 
loop w l _ = (w,l) 

trwa tylko 0.08s, który jest na tyle przyzwoity, żebym przestał optymalizacji tam (podobną zmianę dla wersji String przynosi czas w dół do 3.6s do tego).

+0

Cóż, ten wynik jest zgodny z moimi oczekiwaniami, wielkie dzięki. – vzex

+4

Jeśli odpowiedź Daniela ci pomogła, powinieneś oznaczyć ją akceptowaną, klikając znak zaznaczenia obok niej, aby twoje pytanie zostało oznaczone jako rozwiązane, a inne osoby, które przeczytały to pytanie, odpowiedzią odpowiedzą: – ehird

+0

OK, jestem tu świeżo, teraz jest oznaczone ~ – vzex

Powiązane problemy