为什么这个Haskell程序比同等的Python程序慢得多？

Question

作为编程挑战的一部分,我需要从stdin读取一系列空格分隔的整数(在一行上),并将这些整数的总和打印到stdout.有问题的序列可以包含多达10,000,000个整数.

我有两个解决方案:一个用Haskell(foo.hs)编写,另一个用等价的,用Python 2(foo.py)编写.不幸的是,(编译的)Haskell程序一直比Python程序慢,而且我不知道解释两个程序之间的性能差异; 请参阅下面的基准部分.如果有的话,我会期望Haskell占上风......

我究竟做错了什么？我如何解释这种差异？有没有一种简单的方法来加速我的Haskell代码？

(有关信息,我使用的是2010年中期的Macbook Pro,配备8Gb RAM,GHC 7.8.4和Python 2.7.9.)

foo.hs

main = print . sum =<< getIntList

getIntList :: IO [Int]
getIntList = fmap (map read . words) getLine

(编译ghc -O2 foo.hs)

foo.py

ns = map(int, raw_input().split())
print sum(ns)

基准

在下文中,test.txt由一行1000万个以空格分隔的整数组成.

# Haskell
$ time ./foo < test.txt 
1679257

real    0m36.704s
user    0m35.932s
sys     0m0.632s

# Python
$ time python foo.py < test.txt
1679257 

real    0m7.916s
user    0m7.756s
sys     0m0.151s

Answer 1

read是慢的.对于批量解析,使用bytestring或text原语,或attoparsec.

我做了一些基准测试.您的原始版本在我的计算机上运行了23.9秒.以下版本的运行时间为0.35秒:

import qualified Data.ByteString.Char8 as B
import Control.Applicative
import Data.Maybe
import Data.List
import Data.Char

main = print . sum =<< getIntList

getIntList :: IO [Int]
getIntList =
    map (fst . fromJust . B.readInt) . B.words <$> B.readFile "test.txt"

通过将解析器专门化到您的test.txt文件,我可以将运行时间缩短到0.26秒:

getIntList :: IO [Int]          
getIntList =
    unfoldr (B.readInt . B.dropWhile (==' ')) <$> B.readFile "test.txt"

Answer 2

读取很慢

从这个答案中快速阅读将使您降低到5.5秒.

import Numeric
fastRead :: String -> Int
fastRead s = case readDec s of [(n, "")] -> n

字符串是链接列表

在Haskell中,String类型是链表.使用打包表示(bytestring如果你真的只想要ascii,但Text也非常快并且支持unicode).如这个答案所示,表现应该是颈部和颈部.

Answer 3

我敢猜测，您的问题的很大一部分实际上是words. 当你map read . words，你实际上在做什么是这样的：

1. 扫描输入以查找空格，并在进行时构建非空格列表。有很多不同类型的空格，检查任何不是常见空格类型的字符还涉及对 C 函数的外部调用（慢）。我打算在某个时候解决这个问题，但我还没有解决这个问题，即便如此，您仍然会无缘无故地构建和丢弃列表，并在您真的只想检查空格时检查空格数字。
2. 通读累积的字符列表，尝试从中找出一个数字。产生号码。累积的列表现在变成了垃圾。
3. 返回步骤 1。

这是一种相当荒谬的前进方式。我相信你甚至可以使用类似的可怕的东西做得更好reads，但使用类似ReadP 的东西会更有意义。你也可以尝试更高级的东西，比如基于流的解析；我不知道这是否会有很大帮助。