Python比编译好的Haskell更快？
如果您认为这不属于这里，请随意标记为无关紧要。
我有一个用Python和Haskell编写的简单脚本。 它读取一个具有1,000,000换行分隔整数的文件，将该文件parsing成整数列表，快速sorting，然后将其写入到sorting的不同文件中。 这个文件与未sorting的文件格式相同。 简单。
这里是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
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()
所以所有的数字都是唯一的
总之，不要使用read 。 用这样的函数replaceread ：
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世纪”的testing）的极限稀有金属速度。 它也有一些其他的区别; 例如，它发布到标准库的sortingfunction。 完整的代码如下。
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 tr | BS.null t -> writeFile "sorted" . unlines . map show . sort $ r
原始的Haskell代码
Haskell版本有两个问题：
- 你正在使用stringIO，它build立链接的字符列表
- 你正在使用一个看起来像quicksort的非quicksort。
此程序需要18.7秒才能运行在我的英特尔酷睿2 2.5 GHz笔记本电脑上。 （使用-O2的GHC 7.4）
Daniel的ByteString版本
这是大大改善，但注意到它仍然使用低效的内置合并sorting。
他的版本需要8.1秒（并且不处理负数，但对于这个探索来说这更不是问题）。
注意
从这里开始，这个答案使用下面的包： Vector ， attoparsec ， text和vector-algorithms 。 还要注意kindall的使用timsort的版本在我的机器上需要2.8秒（编辑：和2秒使用pypy）。
文本版本
我撕掉了Daniel的版本，把它翻译成了Text（所以它处理各种编码），并且在ST monad中使用了一个可变的Vector来添加更好的sorting：
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 tr | 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-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 tr | 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秒内运行。
生成testing文件
以防万一谁好奇，我的testing文件是由：
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上…我也是。
比一个Haskellite更python，但我会采取一个刺：
-
在测量的运行时间中，只是读取和写入文件有一定的开销，这两个程序之间可能非常相似。 另外，请注意，您已经预热了这两个程序的caching。
-
你的大部分时间都花费在制作清单和清单片段的副本上。 Python列表操作经过了大量优化，是语言中使用频率最高的部分之一，列表parsing通常也非常高效，大部分时间都花在Python解释器中的C-land上。 Python中没有太多东西是慢的，但是在静态语言中很快速，比如对象实例的属性查找。
-
你的Python实现抛出的数字相当于数据透视表，所以最终它可能会sorting更less的项目，给它一个明显的优势。 （如果你正在sorting的数据集中没有重复的话，这不是问题。）解决这个bug可能需要在每次调用
qs()做出大部分列表的另一个副本，这会减慢Python的速度再多一点。 -
你没有提到你使用的是什么版本的Python。 如果您使用的是2.x，那么您可能只需切换到Python 3.x即可让Haskell击败Python。 🙂
我并不觉得这两种语言在这里基本上是唾手可得的（10％的差异并不值得注意）。 使用C作为性能基准，Haskell因其懒惰的function性质而失去了一些性能，而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中使用的sorting）是一个野兽。
这是事实，但我认为大部分麻烦在于Haskell的写作。 下面的模块非常原始 – 应该使用构build器，当然可以通过String来避免可笑的往返显示 – 但是它简单，明显比pypy更好，改进了python，比其他地方的Haskell模块要好2到4秒在这个页面上（这让我感到吃惊，因为他们使用了多less列表，所以我做了几圈曲柄。）
$ time aa.hs real 0m0.709s $ time pypy aa.py real 0m1.818s $ time python aa.py real 0m3.103s
我正在使用推荐用于vectoralgorithm的无盒vector的types。 以某种forms使用Data.Vector.Unboxed现在显然是做这种事的标准，天真的方式 – 它是新的Data.List（对于Int，Double等）除了sort一切都是令人讨厌的IOpipe理我认为在写作结果上还是会有很大的提高。 阅读和sorting在一起大约需要0.2秒，因为你可以从打印一堆索引而不是写入文件中看到什么，所以花费的时间是其他任何东西的两倍。 如果pypy花费大部分时间使用timsort或其他任何东西，那么看起来sorting本身肯定会在Haskell中大幅提高，就像一个简单的方法一样 – 如果你可以把你的手放在这个恶意的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
要跟踪@kindall有趣的答案，那些时间是从你使用的python / Haskell实现，运行testing的硬件configuration以及两种语言中的algorithm实现。
尽pipe如此，我们仍然可以尝试获得一种语言实现相对于另一种语言的相对性能的一些好的提示，或者从一种语言到另一种语言。 像qsort这样的众所周知的alogrithms，这是一个好的开始。
为了演示python / python比较，我只是在同一台机器上testing了CPython 2.7.3和PyPy 1.8上的脚本：
- CPython：〜8s
- PyPy：〜2.5s
这说明在语言实现方面还有空间可以改进，也许编译好的Haskell最多不能解释和编译相应的代码。 如果你在Python中search速度，如果需要，也可以考虑切换到pypy，如果你的覆盖代码允许你这样做的话。
我注意到一些其他人没有注意到的问题， 你的haskell和python代码都有这个。 （请告诉我，如果它在自动优化固定，我对优化一无所知）。 为此我将在Haskell中演示。 在你的代码中，你可以像这样定义更小和更大的列表：
where lesser = filter (<p) xs greater = filter (>=p) xs
这是不好的，因为你在xs的两个元素中每次比较两次，一次是进入较小的列表，一次是进入较大的列表。 这（理论上，我没有检查时间）使你的sorting使用两倍的比较; 这是一场灾难。 相反，你应该使用一个谓词来将一个列表分成两个列表
split f xs
相当于
(filter f xs, filter (not.f) xs)
使用这种types的函数，只需要比较列表中的每个元素就可以知道元组的哪一侧。
好吧，让我们做到这一点：
where split :: (a -> Bool) -> [a] -> ([a], [a]) split _ [] = ([],[]) split f (x:xs) |fx = let (a,b) = split f xs in (x:a,b) |otherwise = let (a,b) = split f xs in (a,x:b)
现在让我们用更小的/更大的发生器
let (lesser, greater) = split (p>) xs in (insert function here)
完整代码：
quicksort :: Ord a => [a] -> [a] quicksort [] = [] quicksort (p:xs) = let (lesser, greater) = splitf (p>) xs in (quicksort lesser) ++ [p] ++ (quicksort greater) where splitf :: (a -> Bool) -> [a] -> ([a], [a]) splitf _ [] = ([],[]) splitf f (x:xs) |fx = let (a,b) = splitf f xs in (x:a,b) |otherwise = let (a,b) = splitf f xs in (a,x:b)
由于某种原因，我不能纠正where子句中的getter / less的部分，所以我必须在let子句中对其进行修改。 另外，如果它不是尾recursion，让我知道，并为我修复（我不知道如何tail-recorsive完全工作）
现在你应该为python代码做同样的事情。 我不知道Python，所以我不能为你做。
编辑：实际上已经在Data.List中已经是这样的函数称为分区。 注意这certificate了这种function的需要，因为否则就不会被定义。 这缩小了代码：
quicksort :: Ord a => [a] -> [a] quicksort [] = [] quicksort (p:xs) = let (lesser, greater) = partition (p>) xs in (quicksort lesser) ++ [p] ++ (quicksort greater)
Python对于这种事情是非常优化的。 我怀疑Haskell不是。 这是一个类似的问题 ，提供了一些非常好的答案。
