使用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

蟒蛇:

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

您可以尝试使用hashtables包中的命令式哈希映射:http: //hackage.haskell.org/package/hashtables我记得我曾经比Data.Map获得了适度的加速.我不希望有什么壮观的.

UPDATE

我简化了你的python代码,所以我可以在一个大文件(1亿行)上测试它:

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秒

使用哈希表的Haskell翻译:

{-# 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秒,使用2.4%GC.仍然比Python慢​​很多但不是太糟糕.

根据GHC用户指南,您可以在编译时更改RTS选项:

GHC允许您在编译时使用-with-rtsopts标志更改程序的默认RTS选项(第4.12.6节"影响链接的选项").这种情况的一个常见用途是为程序提供一个大于默认值的默认堆和/或堆栈大小.例如,要设置-H128m -K64m,请链接-with-rtsopts =" - H128m -K64m".

Answer 2

您的Haskell和Python实现正在使用具有不同复杂性的映射.Python字典是哈希映射,因此每个操作(成员资格测试,查找和插入)的预期时间为O(1).Haskell版本使用Data.Map,它是一个平衡的二进制搜索树,因此相同的操作需要O(lg n)时间.如果你改变你的Haskell版本以使用不同的地图实现,比如哈希表或某种特里,它应该会更快.但是,我对实现这些数据结构的不同模块不太熟悉,以说哪个是最好的.我从Hackage的数据类开始,寻找你喜欢的类别.您也可以查找允许像STArray那样的破坏性更新的地图.

Answer 3

我们需要更多信息:

• 两个程序从输入中处理单词需要多长时间,没有用于维护计数的数据结构？

• 有多少不同的单词,所以我们可以判断log N平衡树的额外成本是否需要考虑？

• GHC的分析师说什么？特别是,分配花了多少时间？Haskell版本可能花费大部分时间来分配快速过时的树节点.

• 更新:我错过了小写的"文字"可能意味着Data.Text.您可能正在比较apply和oranges.Python的Latin1编码每个字符使用一个字节.虽然它试图有效,但Data.Text必须允许超过256个字符的可能性.如果切换到String或更好,会发生什么Data.ByteString？

根据这些指标所说的,这里有几件事要尝试:

• 如果分析输入是瓶颈,请尝试驱动所有I/O和分析,Data.ByteString而不是Text.

• 如果数据结构是瓶颈,Bentley和Sedgewick的三元搜索树纯粹是功能性的,但与哈希表竞争性地执行.TernaryTreesHackage上有一个包.