不満なトリックを使わずに自分の単語カウントプログラムを速くする方法はありますか？

Question

少し練習として、私はハズケで次の単語カウントプログラムを作った。それは、テキストファイル内の別個の単語を数え、それらの頻度と共に50の最も頻繁なものを出力する。

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 " " 

問題は、それが可変のdictと私のPythonの実装よりも16倍も遅いということであるということです。私は問題はGHCがconstanstly新しいマップをrealocatingているという事実によるものであると考え

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] 

同じものを何度も繰り返し使用することができます。ランタイムstatitisticsが割り当ての多くを示しています

$ 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 

私の質問は次のとおりです。このプログラムを作るための方法が存在するよう、IOモナドで働く可変データ構造を使用するなど、汚い手口に頼ることなく、パフォーマンスが向上し、等？

PS：データファイルには、次のURLから入手できます。ここではhttp://www.gutenberg.org/cache/epub/13951/pg13951.txt

Answer 1

は、私が試したいくつかの迅速かつ簡単な最適化されています。私のマシンで

オリジナル版：

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

1. 代わりのinsertとfoldl'を使用して、あなたは 単語をカウントするfromListWithを使用することができます。

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

   これは2倍以上です。

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

2. Stringタイプではなく、エレガントですが非効率 文字列を操作可能な文字のリンクリストです。 Textタイプを使用すると、効率的な文字列処理の をさらに取得できます。また、pp関数を書き換えて、foldl'の代わりにunlines を使用し、wordsの代わりにsplitOnを元の分割に使用しました。

   {-# 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 
   

   また、前のステップの2倍の速さ。

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

3. Map

   import qualified Data.Map.Strict as Map 
   

   約20％の高速化

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