为什么这个简单的文本分析程序如此之慢？

Question

这是我计算行数和单词的代码:

import System.IO
import Data.List
main = do
        hSetBinaryMode stdin True
        interact $ (\(w,l)->"line:"++(show l)++"\nwords:"++(show w)++"\n")
                   . foldl' (\(w,l) r-> w `seq` l `seq` (w+length r ,succ l) ) (0,0)
                   . lines

这大约需要10秒才能在大约100兆字节的文件上运行.我将它与Lua(9s),awk(20s)和wc -l -c(0.6s)中的类似程序进行了比较.

为什么这段代码这么慢？可能是什么问题呢？

Answer 1

String已知I/O 在Haskell中不够快.通常必须将从句柄读取的字节转换为Unicode代码点,然后根据这些代码点构建链接列表.这是导致大量分配的大量工作.在这种情况下,转换为代码点有点简单,因为您将stdin设置为二进制模式,但是链接字符列表的构造仍然需要很长时间.

另一个小因素是您的行计数正在使用Integer,但这很小,只有在I/O达到最高速度时才起到重要作用.

如果您需要快速I/O,则必须使用更适合的类型.ByteString例如,一种可能性是使用

import Data.List
import qualified Data.ByteString.Lazy.Char8 as C
main = do
        txt <- C.getContents
        putStrLn $ (\(w,l)->"line:"++(show l)++"\nwords:"++(show w)++"\n"). foldl' (\(w,l) r-> w `seq` l `seq` (w+C.length r ,succ l) ) (0,0) . C.lines $ txt

在我的盒子上以0.12秒的94MB文件工作(wc -l -c需要0.06s),而原始使用String需要4.4s.它可以进一步优化,

{-# LANGUAGE BangPatterns #-}
import Data.List
import qualified Data.ByteString.Lazy.Char8 as C
main = do
        txt <- C.getContents
        putStrLn $ (\(w,l)->"line:"++(show l)++"\nwords:"++(show w)++"\n"). loop 0 0 . C.lines $ txt

loop :: Int -> Int -> [C.ByteString] -> (Int,Int)
loop !w !l (ln:lns) = loop (w + fromIntegral (C.length ln)) (l+1) lns
loop w l _ = (w,l)

只需0.08s,这足以让我停止在那里优化(String版本的类似变化将时间降低到3.6s).