Kelime sayma programımı, pürüzlü hileler kullanmadan daha hızlı hale getirmenin bir yolu var mı?

Question

Biraz egzersiz olarak, haskell'de aşağıdaki kelime sayma programını yaptım. Bir metin dosyasında farklı kelimeleri sayar ve frekansları ile birlikte en sık 50 olanı çıkarır.

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

sorun bunun bir değişken dict ile benim piton uygulanması göre 16 kat daha yavaş olduğunu olmasıdır:

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] 

Sorun ghc constanstly yeni haritalar zaman realocating gerçeğine bağlı olduğunu düşünüyorum Aynı olanı tekrar tekrar kullanabilir. Çalışma zamanı statitistics tahsisleri bir sürü gösterir:

$ 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 

Sorum şu: Bu programı yapmak için bir yolu yoktur böyle, IO monad çalışan değişken veri yapılarını kullanarak kirli hileler başvurmadan, daha iyi performans, vb. ?

Not: veri dosyası aşağıdaki adresten bulabilirsiniz: Burada http://www.gutenberg.org/cache/epub/13951/pg13951.txt

Answer 1

denedim bazı hızlı ve basit optimizasyonlar vardır. Benim makinede

Orijinal versiyonu: Yerine insert kullanarak ve foldl' sen kelimeleri saymak için fromListWith kullanabilirsiniz ait

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

1. .

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

   Bu, iki kat daha hızlıdır.

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

2. String tipi oldukça şık ama verimsiz dizeleri manipüle yapar karakterlerin bir bağlantılı listesidir. Daha fazla verimli dizi işleme için Text türünü kullanabiliriz. Ayrıca, kullanmak yerine pp işlevini yeniden yazdım ve yerine splitOn özgün bölme için kullanın.

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

   Yine, önceki adıma göre iki kat daha hızlı.

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

3. import qualified Data.Map.Strict as Map 
   

   Map sıkı sürümünü kullanın% 20 kadarı hız artışı

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