为什么Haskell程序比等效的Python程序慢得多?

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

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

我究竟做错了什么? 我怎样才能解释这种差异? 有没有简单的方法来加快我的Haskell代码?

(有关信息,我正在使用8Gb RAM,GHC 7.8.4和Python 2.7.9的2010年中期Macbook Pro。)

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 

read很慢。 对于批量parsing,请使用bytestringtext基元或attoparsec

我做了一些基准testing。 您的原始版本在我的电脑上运行了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" 

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

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

阅读很慢

快速阅读, 从这个答案 ,将带你下降到5.5秒。

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

string是链接列表

在Haskell中, Stringtypes是一个链表。 使用打包表示( bytestring如果你真的只想ascii但Text也非常快,并支持Unicode)。 正如在这个答案中所显示的那样,表演应该是无可奈何的。

我敢冒险猜测你的问题的一大部分其实就是words 。 当你map read . words map read . words ,你实际上做的是这样的:

  1. 扫描input寻找一个空间,build立一个非空格列表,你去。 有很多不同types的空间,检查任何不是一般空间types的字符还需要一个外部调用C函数(慢)。 我打算在某个时候解决这个问题,但是我还没有做到这一点,即使这样,你仍然会在没有正当理由的情况下build立并丢弃列表,并且在你真正想检查的时候检查空格数字。
  2. 通读累积字符的列表,尝试从中得出一个数字。 产生数字。 累积的列performance在变成垃圾。
  3. 回到步骤1。

这是一个相当荒谬的方式来进行。 我相信你甚至可以使用像reads这样的可怕东西做得更好,但是使用类似于ReadP的东西会更有意义。 你也可以尝试一些比较stream行的parsing方法; 我不知道这是否会有所帮助。