Python比编译Haskell快？

Question

我有一个用Python和Haskell编写的简单脚本。它读取一个包含1000000个换行分隔整数的文件，将该文件解析为一个整数列表，对其进行快速排序，然后将其写入另一个排序的文件。此文件的格式与未排序文件的格式相同。很简单。

这里是哈斯克尔：

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser  = filter (< p) xs
        greater = filter (>= p) xs

main = do
    file <- readFile "data"
    let un = lines file
    let f = map (\x -> read x::Int ) un
    let done = quicksort f
    writeFile "sorted" (unlines (map show done))

下面是Python：

def qs(ar):
    if len(ar) == 0:
        return ar

    p = ar[0]
    return qs([i for i in ar if i < p]) + [p] + qs([i for i in ar if i > p])


def read_file(fn):
    f = open(fn)
    data = f.read()
    f.close()
    return data

def write_file(fn, data):
    f = open('sorted', 'w')
    f.write(data)
    f.close()


def main():
    data = read_file('data')

    lines = data.split('\n')
    lines = [int(l) for l in lines]

    done = qs(lines)
    done = [str(l) for l in done]

    write_file('sorted', "\n".join(done))

if __name__ == '__main__':
    main()

很简单。现在我用

$ ghc -O2 --make quick.hs

我给这两个人计时：

$ time ./quick
$ time python qs.py

结果：

哈斯克尔：

real    0m10.820s
user    0m10.656s
sys 0m0.154s

Python：

real    0m9.888s
user    0m9.669s
sys 0m0.203s

Python怎么可能比本地代码Haskell更快呢？

谢谢

编辑：

• Python版本：2.7.1
• GHC版本：7.0.4
• Mac OSX，10.7.3版
• 2.4GHz英特尔酷睿i5

列表生成者

from random import shuffle
a = [str(a) for a in xrange(0, 1000*1000)]
shuffle(a)
s = "\n".join(a)
f = open('data', 'w')
f.write(s)
f.close()

所以所有的数字都是唯一的。

Answer 1

与其说是哈斯凯利特人，不如说是Python人，但我要试试看：

1. 仅仅读取和写入文件，在您测量的运行时中会有相当多的开销，这两个程序之间可能非常相似。另外，请注意已经为两个程序预热了缓存。

2. 你的大部分时间都花在制作列表和列表片段的副本上。Python列表操作是经过大量优化的，是该语言最常用的部分之一，列表理解通常也有相当高的性能，在Python解释器的C-land中花费了大量时间。在Python中没有太多慢的东西，但是在静态语言中速度很快，比如对象实例上的属性查找。

3. 您的Python实现丢弃了与pivot相等的数字，因此到最后它可能会排序更少的项，这给了它一个明显的优势。（如果正在排序的数据集中没有重复项，则这不是问题。）修复此错误可能需要对每次调用qs()时的大多数列表进行另一个副本，这将使Python的速度慢一点。

4. 你没有提到你使用的是什么版本的Python。如果您使用的是2.x，那么只需切换到Python 3.x就可以让Haskell击败Python。：-）

我并不太惊讶这两种语言基本上是并驾齐驱的（10%的差异是不值得注意的）。使用C作为性能基准，Haskell由于其懒惰的功能特性而损失了一些性能，而Python由于是一种解释性语言而损失了一些性能。一场像样的比赛。

由于Daniel Wagner发布了一个使用内置sort的优化Haskell版本，下面是一个使用list.sort()的类似优化Python版本：

mylist = [int(x.strip()) for x in open("data")]
mylist.sort()
open("sorted", "w").write("\n".join(str(x) for x in mylist))

在我的机器上是3.5秒，而原始代码是9秒。几乎仍然与优化的Haskell并驾齐驱。原因：它的大部分时间都花在了C程序库中。另外，TimSort（Python中使用的排序）是一个野兽。

Answer 2

简而言之，不要使用read。用如下函数替换read：

import Numeric

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

我的速度相当快：

~/programming% time ./test.slow
./test.slow  9.82s user 0.06s system 99% cpu 9.901 total
~/programming% time ./test.fast
./test.fast  6.99s user 0.05s system 99% cpu 7.064 total
~/programming% time ./test.bytestring
./test.bytestring  4.94s user 0.06s system 99% cpu 5.026 total

有趣的是，上面的结果包含了一个版本，它使用ByteString（因此完全忽略了文件编码的问题而没有通过“为21世纪做好准备”的测试）来获得最终的裸机速度。它还有一些其他的区别；例如，它发布到标准库的排序函数。完整代码如下。

import qualified Data.ByteString as BS
import Data.Attoparsec.ByteString.Char8
import Control.Applicative
import Data.List

parser = many (decimal <* char '\n')

reallyParse p bs = case parse p bs of
    Partial f -> f BS.empty
    v -> v

main = do
    numbers <- BS.readFile "data"
    case reallyParse parser numbers of
        Done t r | BS.null t -> writeFile "sorted" . unlines . map show . sort $ r

Answer 3

原始Haskell代码

Haskell版本有两个问题：

• 您使用的是string IO，它构建了字符的链接列表
• 您正在使用类似于快速排序的非快速排序。

此程序在我的英特尔Core2 2.5 GHz笔记本电脑上运行需要18.7秒。（GHC 7.4使用-O2）

丹尼尔的ByteString版本

这已经有了很大的改进，但请注意，它仍然使用低效的内置合并排序。

他的版本需要8.1秒（并且不处理负数，但这对于本次探索来说更是一个没有问题的问题）。

注意

从这里开始，这个答案使用以下包：Vector，attoparsec，text和vector-algorithms。还要注意，kindall使用timsort的版本在我的机器上需要2.8秒（edit：使用pypy需要2秒）。

文本版本

我删掉了丹尼尔的版本，将其翻译成文本（以便处理各种编码），并在ST monad中使用可变的Vector添加了更好的排序：

import Data.Attoparsec.Text.Lazy
import qualified Data.Text.Lazy as T
import qualified Data.Text.Lazy.IO as TIO
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Algorithms.Intro as I
import Control.Applicative
import Control.Monad.ST
import System.Environment (getArgs)

parser = many (decimal <* char '\n')

main = do
    numbers <- TIO.readFile =<< fmap head getArgs
    case parse parser numbers of
        Done t r | T.null t -> writeFile "sorted" . unlines
                                                  . map show . vsort $ r
        x -> error $ Prelude.take 40 (show x)

vsort :: [Int] -> [Int]
vsort l = runST $ do
        let v = V.fromList l
        m <- V.unsafeThaw v
        I.sort m
        v' <- V.unsafeFreeze m
        return (V.toList v')

4秒钟内完成（也不处理负片）

返回Bytestring

所以现在我们知道我们可以做一个更通用的更快的程序了，那就让只使用ASCii的版本更快吧？没问题！

import qualified Data.ByteString.Lazy.Char8 as BS
import Data.Attoparsec.ByteString.Lazy (parse,  Result(..))
import Data.Attoparsec.ByteString.Char8 (decimal, char)
import Control.Applicative ((<*), many)
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Algorithms.Intro as I
import Control.Monad.ST


parser = many (decimal <* char '\n')

main = do
    numbers <- BS.readFile "rands"
    case parse parser numbers of
        Done t r | BS.null t -> writeFile "sorted" . unlines
                                                   . map show . vsort $ r

vsort :: [Int] -> [Int]
vsort l = runST $ do
        let v = V.fromList l
        m <- V.unsafeThaw v
        I.sort m
        v' <- V.unsafeFreeze m
        return (V.toList v')

这需要2.3秒。

生成测试文件

万一有人好奇，我的测试文件是由：

import Control.Monad.CryptoRandom
import Crypto.Random
main = do
  g <- newGenIO :: IO SystemRandom
  let rs = Prelude.take (2^20) (map abs (crandoms g) :: [Int])
  writeFile "rands" (unlines $ map show rs)

如果你想知道为什么vsort没有以更简单的形式打包在Hackage上。。。我也是