Gibt es eine Möglichkeit, mein Wortzählprogramm schneller zu machen, ohne unreine Tricks zu verwenden?

Question

Als kleine Übung habe ich das folgende Wortzählprogramm in Haskell gemacht. Es zählt einzelne Wörter in einer Textdatei und gibt die 50 häufigsten zusammen mit ihren Häufigkeiten aus.

import qualified Data.Map as Map 
import Data.List.Split 
import Data.List 
import Data.Ord 

-- Count words 
count = Map.toList . foldl' increment Map.empty 
    where 
     increment dict k = Map.insert k (1 + Map.findWithDefault 0 k dict) dict 

-- Sort the counts 
countAndSort = sortBy (flip $ comparing snd) . count 

-- Pretty printing 
pp :: Show a => [(String,a)] -> IO() 
pp = putStrLn . foldl' format "" where 
    format text (x,y) = text ++ "\n" ++ x ++ "\t" ++ show y 

main = readFile "pg13951.txt" >>= pp . take 50 .countAndSort . splitOn " " 

Das Problem ist, dass es, dass es 16-mal ist langsamer als mein Python-Implementierung mit einem wandelbaren dict:

def increment(dic,word): 
    dic[word] = dic.get(word,0) + 1 
    return dic 

print sorted(reduce(increment,open("pg13951.txt").read().split(),{}).items(),key=lambda e:-e[1])[:50] 

Ich denke, das Problem auf die Tatsache zurückzuführen ist, dass ghc constanstly ist realocating neue Karten, wenn es könnte dasselbe immer und immer wieder verwenden. Laufzeit statitistics zeigt viele Zuteilungen:

$ ghc -rtsopts count.hs 
$ ./count +RTS -sstderr 

de  7682 
et  4423 
la  4238 
<snip> 
d'Artagnan  511 
M.  502 
c'est 443 
d'Artagnan,  443 

    705,888,048 bytes allocated in the heap 
    655,511,720 bytes copied during GC 
    139,823,800 bytes maximum residency (10 sample(s)) 
     1,049,416 bytes maximum slop 
      287 MB total memory in use (0 MB lost due to fragmentation) 

            Tot time (elapsed) Avg pause Max pause 
    Gen 0  1366 colls,  0 par 2.16s 2.26s  0.0017s 0.0072s 
    Gen 1  10 colls,  0 par 2.86s 3.09s  0.3093s 1.5055s 

    INIT time 0.00s ( 0.00s elapsed) 
    MUT  time 3.18s ( 3.36s elapsed) 
    GC  time 5.02s ( 5.36s elapsed) 
    EXIT time 0.00s ( 0.00s elapsed) 
    Total time 8.20s ( 8.72s elapsed) 

    %GC  time  61.2% (61.4% elapsed) 

    Alloc rate 221,831,366 bytes per MUT second 

    Productivity 38.8% of total user, 36.5% of total elapsed 

Meine Frage ist: Gibt es eine Möglichkeit, dieses Programm zu machen einen bessere Leistung, ohne zu schmutzigen Tricks zurückgreifen, wie in dem IO-Monade, arbeitete mit änderbaren Datenstrukturen, etc. ?

PS: die Datendatei unter folgender URL verfügbar: http://www.gutenberg.org/cache/epub/13951/pg13951.txt

Answer 1

Hier sind einige schnelle und einfache Optimierungen, die ich versuchte.

Original-Version auf meinem Rechner:

real 0m1.539s 
user 0m1.452s 
sys 0m0.076s 

1. Statt mit insert und foldl' können Sie fromListWith verwenden die Worte zu zählen.

   count = Map.toList . Map.fromListWith (+) . flip zip (repeat 1) 
   

   Dies ist doppelt so schnell.

   real 0m0.687s 
   user 0m0.648s 
   sys 0m0.032s 
   

2. Der String Typ ist eine verknüpfte Liste von Zeichen, die Saiten eher elegant, aber ineffizient macht manipulieren. Wir können den Typ verwenden, um mehr effiziente String-Handhabung zu erhalten. Ich schrieb auch Ihre pp Funktion, um unlines anstelle von foldl' zu verwenden und words stattdessen splitOn für den ursprünglichen Split zu verwenden.

   {-# LANGUAGE OverloadedStrings #-} 
   
   import Data.Monoid 
   import Data.Text (Text) 
   import qualified Data.Text as T 
   import qualified Data.Text.IO as T 
   
   pp :: Show a => [(Text,a)] -> IO() 
   pp = T.putStrLn . T.unlines . map format where 
       format (x,y) = x <> "\t" <> (T.pack $ show y) 
   
   main = T.readFile "pg13951.txt" >>= pp . take 50 .countAndSort . T.words 
   

   Wieder doppelt so schnell wie im vorherigen Schritt.

   real 0m0.330s 
   user 0m0.316s 
   sys 0m0.008s 
   

3. die strenge Version von Map Verwenden

   import qualified Data.Map.Strict as Map 
   

   Etwa 20% Geschwindigkeitserhöhung

   real 0m0.265s 
   user 0m0.252s 
   sys 0m0.008s