Python 比已编译的 Haskell 更快？

Question

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

这是 Haskell:

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()

非常简单。现在我用

编译Haskell代码

$ ghc -O2 --make quick.hs

我将这两个时间用:

$ time ./quick
$ time python qs.py

结果:

haskell :

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

原始 Haskell 代码

Haskell 版本有两个问题:

• 您正在使用字符串 IO，它构建字符的链接列表
• 您正在使用看起来像快速排序的非快速排序。

在我的 Intel Core2 2.5 GHz 笔记本电脑上运行该程序需要 18.7 秒。 (使用 -O2 的 GHC 7.4)

Daniel 的 ByteString 版本

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

他的版本需要 8.1 秒(并且不处理负数，但这对于本次探索来说不是问题)。

注意

从这里开始，这个答案使用以下包:Vector、attoparsec、text 和 vector-algorithms .另请注意，使用 timsort 的 kindall 版本在我的机器上需要 2.8 秒(编辑:使用 pypy 需要 2 秒)。

文字版

我抄袭了 Daniel 的版本，将其翻译成 Text(因此它可以处理各种编码)，并在 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 秒内运行(并且也不处理负数)

返回字节串

所以现在我们知道我们可以制作一个更快的更通用的程序，那么让仅 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 上以更简单的形式打包......我也是。