用haskell建立直方圖，比python慢​​了許多倍

Question

我正要測試樸素貝葉斯分類。其中一部分將構建訓練數據的直方圖。問題在於，我使用了大量的訓練數據，幾年前的haskell-cafe郵件列表，並且該文件夾中有超過20k個文件。

用python創建直方圖需要花費兩分多鐘的時間，而使用haskell需要8分多鐘。我正在使用Data.Map（insertWith'），枚舉器和文本。我還能做些什麼來加速該計劃？

哈斯克爾：

import qualified Data.Text as T 
import qualified Data.Text.IO as TI 
import System.Directory 
import Control.Applicative 
import Control.Monad (filterM, foldM) 
import System.FilePath.Posix ((</>)) 
import qualified Data.Map as M 
import Data.Map (Map) 
import Data.List (foldl') 
import Control.Exception.Base (bracket) 
import System.IO (Handle, openFile, hClose, hSetEncoding, IOMode(ReadMode), latin1) 
import qualified Data.Enumerator as E 
import Data.Enumerator (($$), (>==>), (<==<), (==<<), (>>==), ($=), (=$)) 
import qualified Data.Enumerator.List as EL 
import qualified Data.Enumerator.Text as ET 



withFile' :: (Handle -> IO c) -> FilePath -> IO c 
withFile' f fp = do 
    bracket 
    (do 
     h ← openFile fp ReadMode 
     hSetEncoding h latin1 
     return h) 
    hClose 
    (f) 

buildClassHistogram c = do 
    files ← filterM doesFileExist =<< map (c </>) <$> getDirectoryContents c 
    foldM fileHistogram M.empty files 

fileHistogram m file = withFile' (λh → E.run_ $ enumHist h) file 
    where 
    enumHist h = ET.enumHandle h $$ EL.fold (λm' l → foldl' (λm'' w → M.insertWith' (const (+1)) w 1 m'') m' $ T.words l) m 

的Python：

for filename in listdir(root): 
    filepath = root + "/" + filename 
    # print(filepath) 
    fp = open(filepath, "r", encoding="latin-1") 
    for word in fp.read().split(): 
     if word in histogram: 
      histogram[word] = histogram[word]+1 
     else: 
      histogram[word] = 1 

編輯：增加進口

Answer 1

您可以嘗試使用哈希表包中的命令式哈希映射：http://hackage.haskell.org/package/hashtables 我記得我曾經比Data.Map有過中等加速比。儘管如此，我不會期待任何壯觀的事情。

UPDATE

我簡化你的Python代碼，所以我可以測試它在一個單一的大文件（100萬條用戶線）：

import sys 
histogram={} 
for word in sys.stdin.readlines(): 
    if word in histogram: 
     histogram[word] = histogram[word]+1 
    else: 
     histogram[word] = 1 
print histogram.get("the") 

注意到6.06秒

使用

哈斯克爾翻譯哈希表：

{-# LANGUAGE OverloadedStrings #-} 
import qualified Data.ByteString.Char8 as T 
import qualified Data.HashTable.IO as HT 
main = do 
    ls <- T.lines `fmap` T.getContents 
    h <- HT.new :: IO (HT.BasicHashTable T.ByteString Int) 
    flip mapM_ ls $ \w -> do 
    r <- HT.lookup h w 
    case r of 
     Nothing -> HT.insert h w (1::Int) 
     Just c -> HT.insert h w (c+1) 
    HT.lookup h "the" >>= print 

運行時帶有大的分配區域：histogram +RTS -A500M 需要9.3秒，GC爲2.4％。還是比Python慢​​很多，但不是太糟糕。

按照GHC user guide，您可以更改RTS選項在編譯：

GHC lets you change the default RTS options for a program at compile time, using the -with-rtsopts flag (Section 4.12.6, 「Options affecting linking」). A common use for this is to give your program a default heap and/or stack size that is greater than the default. For example, to set -H128m -K64m, link with -with-rtsopts="-H128m -K64m".

Answer 2

你Haskell和Python實現使用的地圖，不同的複雜性。 Python字典是哈希映射，因此每個操作（成員資格測試，查找和插入）的預期時間爲O（1）。 Haskell版本使用Data.Map，它是一個平衡的二叉搜索樹，所以相同的操作需要O（lg n）時間。如果你改變你的Haskell版本來使用不同的地圖實現，比如說一個哈希表或某種類型的trie，它應該會更快。然而，對於實現這些數據結構的不同模塊來說，哪一個最好，我還不夠熟悉。我會從the Data category on Hackage開始，找一個你喜歡的。你也可能會尋找一個允許破壞性更新的地圖，如STArray。

Answer 3

我們需要更多的信息：

• 多久採取兩種方案，以處理來自字輸入，沒有數據結構來維護計數？

• 有多少個不同的單詞存在，所以我們可以判斷平衡樹木的額外費用是否需要考慮？

• GHC的分析器說什麼？特別是，分配花了多少時間？ Haskell版本可能花費大部分時間來分配快速過時的樹節點。

• UPDATE：我錯過了小寫「文本」可能意味着Data.Text。你可能會比較適用和橙子。 Python的Latin1編碼每個字符使用一個字節。雖然它試圖有效，但是Data.Text必須允許超過256個字符的可能性。如果切換到String或更好，Data.ByteString會發生什麼情況？

根據什麼這些指標說，這裏有幾件事情嘗試：

• 如果分析輸入的是一個瓶頸，嘗試駕駛所有的I/O，分析和Data.ByteString代替Text。

• 如果數據結構是一個瓶頸，Bentley和Sedgewick的ternary search trees是純粹的功能，但與哈希表競爭性地執行。 Hackage上有一個TernaryTrees包。