Python比编译的Haskell快吗？

Question

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

这是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

蟒蛇：

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

简而言之，不要使用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

只是为了好玩，上述结果包括一个使用ByteStringULTIMATE BARE-METAL
SPEED的版本（因此完全忽略了文件编码问题，因此未能通过“ 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