Haskell 中涉及 'read' 的程序比等效的 Python 程序要慢得多。

Question

作为编程挑战的一部分，我需要从stdin读取一系列由空格分隔的整数（在单行上），并将这些整数的总和打印到stdout。所涉及的序列可以包含多达10,000,000个整数。

我有两个解决方案：一个用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

- jub0bs

---

你的测试文件几乎全部都是零。这真的是一个好的测试吗？ - dfeuer

@dfeuer 我并没有生成那个文件。它只是比赛期间提供的测试案例之一。它可能很糟糕或者无趣，但这并不是我的选择。 - jub0bs

我知道 read :: String -> Integer 至少在最近的一个补丁之前是二次方的。不确定是否对于 Int 使用了相同类型的算法... - Bakuriu

请注意，当您的格式仅为整数时，read不是正确的工具。 read 旨在解析有效的 Haskell 表达式，因此类似 "((( 0x8485) ))" 的内容会以相当高的额外成本成功解析。请使用适当的工具来解析整数。 - Thomas M. DuBuisson

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"

- András Kovács

---

你应该使用 B.dropWhile (not . isDigit) 来做得更好。isDigit 比 isSpace 更便宜，虽然不如假的版本 (==' ') 便宜。 - dfeuer

Answer 2

阅读速度较慢

根据这个回答，快速读取将使您的速度降至5.5秒。

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

字符串是链表

在 Haskell 中，String 类型是一个链表。如果你只需要 ASCII 码，可以使用紧凑的表示方法（bytestring），但 Text 也非常快速且支持 Unicode。根据这个答案所示，性能应该相当。

- Thomas M. DuBuisson

Answer 3

我敢猜测，你的问题很大一部分实际上与“单词”有关。当你执行“map read . words”时，实际上是在做以下这些事情：

1. 扫描输入，寻找空格并构建一个非空格列表。有许多不同种类的空格，检查任何不是常见类型的空格的字符还涉及到对C函数的外部调用（速度较慢）。我计划在未来修复此问题，但目前尚未解决，即使修复后，你仍然会为没有充分理由而构建和丢弃列表，并在实际上只想检查数字时检查空格。
2. 读取累积字符列表以尝试将其组成数字。生成该数字。现在累积的列表变成了垃圾。
3. 回到步骤1。

这是一种相当荒谬的方法。我认为你甚至可以使用类似于reads这样可怕的东西来做得更好，但使用ReadP之类的东西会更有意义。您还可以尝试更高级的流解析方式；我不知道这是否有助于提高效率。

- dfeuer

---

“word” 似乎不是大问题，根据经验。使用 map (const 0) . words <$> readFile "test.txt"，代码运行时间为1.3秒，而如果我使用 read 而不是 const 0，则需要约23秒。 - András Kovács

@AndrásKovács，有趣。如果您使用快速版本的read和words会发生什么？如果read可以变得更快，为什么不这样做呢？ - dfeuer

如果我使用一个相当丑陋的代码 map (fst . fromJust . B.readInt . B.pack) . words <$> readFile "test.txt"，依然需要2秒才能运行。看一下read函数可能是个好主意... - András Kovács