在Haskell中有效地解析ASCII文件

Question

我想在Haskell中重新实现我的一些ASCII解析器,因为我认为我可以获得一些速度.然而,即使是一个简单的"grep和count"也比一个草率的Python实现要慢得多.

有人可以解释我为什么以及如何正确地做到这一点？

所以任务是,计算以字符串"foo"开头的行.

我非常基本的Python实现:

with open("foo.txt", 'r') as f:
    print len([line for line in f.readlines() if line.startswith('foo')])

和Haskell版本:

import System.IO 
import Data.List

countFoos :: String -> Int
countFoos str = length $ filter (isPrefixOf "foo") (lines str)

main = do
    contents <- readFile "foo.txt"
    putStr (show $ countFoos contents)

time在带有17001895行的~600MB文件上运行两者都表明Python的实现速度几乎是Haskell的4倍(在我的带有PCIe SSD的MacBook Pro Retina 2015上运行):

> $ time ./FooCounter                                                           
1770./FooCounter  20.92s user 0.62s system 98% cpu 21.858 total

> $ time python foo_counter.py                                                   
1770
python foo_counter.py  5.19s user 1.01s system 97% cpu 6.332 total

与unix命令行工具相比:

> $ time grep -c foo foo.txt                                                     
1770
grep -c foo foo.txt   4.87s user 0.10s system 99% cpu 4.972 total

> $ time fgrep -c foo foo.txt                                                     
1770
fgrep -c foo foo.txt  6.21s user 0.10s system 99% cpu 6.319 total

> $ time egrep -c foo foo.txt                                                     
1770
egrep -c foo foo.txt  6.21s user 0.11s system 99% cpu 6.317 total

有任何想法吗？

更新:

使用AndrásKovács的实现(ByteString),我得到它不到半秒!

> $ time ./FooCounter                                                                                                               
1770
./EvtReader  0.47s user 0.48s system 97% cpu 0.964 total

Answer 1

我基准测试了以下解决方案:

{-# LANGUAGE OverloadedStrings #-}

import qualified Data.ByteString.Char8 as B

main =
  print . length . filter (B.isPrefixOf "foo") . B.lines =<< B.readFile "test.txt"

text.txt是一个170 MB的文件,有800万行,一半的行以"foo"开头.我用GHC 7.10和-O2 -fllvm.编译.

该ByteString版本在0.27秒内运行,而原始版本在5.16秒内运行.

但是,严格ByteString版本使用170 MB内存加载完整文件.将导入更改为Data.ByteString.Lazy.Char8I,运行时间为0.39秒,内存使用量为1 MB.

Answer 2

您的Haskell版本使用该类型String来表示文件的文本.String是一个别名,[Char]其中包含一个链接的字符列表.这不是大字符串的好表示.

请尝试使用文本包.它将字符串表示为数组(在Data.Text.*模块中)或表示链接的数组列表(在Data.Text.Lazy.*模块中).要移植现有代码,您可能需要后者,因为我猜你不想一次将完整的600MB文件加载到内存中.看在Data.Text.Lazy和Data.Text.Lazy.IO模块的变型readFile,filter,isPrefixOf您正在使用等功能.

如果您确定只想支持ASCII,那么您也可以考虑使用bytestring包而不是text包.