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

结果:

哈斯克尔:

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 Intel Core 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秒.(GHC 7.4使用-O2)

丹尼尔的ByteString版本

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

他的版本耗时8.1秒(并没有处理负数,但这对于这次探索来说更不是一个问题).

注意

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

文本版本

我撕掉了Daniel的版本,将其翻译为Text(因此它处理了各种编码)并使用VectorST monad中的mutable添加了更好的排序:

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 -only版本呢？没问题!

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上以一些更简单的形式打包......我也是.

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世纪"测试),以获得ULTIMATE BARE-METAL SPEED.它还有一些其他的差异; 例如,它发送到标准库的排序函数.完整代码如下.

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

更像是Pythonista而不是Haskellite,但我会采取刺:

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使用内置版本发布了优化的Haskell版本sort,因此这是一个类似优化的Python版本,使用list.sort():

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 4

这是事后,但我认为大部分麻烦都在Haskell写作中.以下模块非常原始 - 可能应该使用构建器并且肯定会避免通过String进行显示的荒谬往返 - 但它很简单,并且比使用kindall改进的python的pypy明显更好,并且比其他地方的2和4秒Haskell模块更好在这个页面上(它让我感到惊讶的是他们使用了多少列表,所以我又多了几圈.)

$ time aa.hs        real    0m0.709s
$ time pypy aa.py   real    0m1.818s
$ time python aa.py real    0m3.103s

我正在使用推荐用于矢量算法的未装箱矢量.以某种形式使用Data.Vector.Unboxed显然现在是做这种事情的标准,天真的方式 - 它是新的Data.List(用于Int,Double等)除了sort令人恼火的IO管理之外的所有东西,特别是在写端,我认为仍然可以大幅改进.读取和排序一起大约需要0.2秒,因为你可以看到它要求它打印一堆索引而不是写入文件,因此写入的时间是其他任何时间的两倍.如果pypy花费大部分时间使用timsort或其他任何东西,那么看起来排序本身在Haskell中肯定会更好,而且就如此简单 - 如果你可以抓住这个darned vector ...

我不确定为什么没有方便的函数来读取和写入自然格式的无盒装东西的向量 - 如果有的话,这将是三行长并且会避免String并且要快得多,但也许我只是避风港没见过他们.

import qualified Data.ByteString.Lazy.Char8 as BL
import qualified Data.ByteString.Char8 as B
import qualified Data.Vector.Unboxed.Mutable as M
import qualified Data.Vector.Unboxed as V
import Data.Vector.Algorithms.Radix 
import System.IO

main  = do  unsorted <- fmap toInts (BL.readFile "data")
            vec <- V.thaw unsorted
            sorted <- sort vec >> V.freeze vec
            withFile "sorted" WriteMode $ \handle ->
               V.mapM_ (writeLine handle) sorted

writeLine :: Handle -> Int -> IO ()
writeLine h int = B.hPut h $ B.pack (show int ++ "\n")

toInts :: BL.ByteString -> V.Vector Int
toInts bs = V.unfoldr oneInt (BL.cons ' ' bs) 

oneInt :: BL.ByteString -> Maybe (Int, BL.ByteString)
oneInt bs = if BL.null bs then Nothing else 
               let bstail = BL.tail bs
               in if BL.null bstail then Nothing else BL.readInt bstail