Haskell、Python速度比较（堆//优先级队列）

Question

我有一个问题要解决。它的细节基本上无关紧要，我有两个有效的解决方案：Python 和 Haskell。

Python代码：

import heapq

_, volume, *ppl = map(int, open("input.txt").read().split())
ppl = [-x for x in ppl]
heapq.heapify(ppl)
for i in range(volume):
    current = (- heapq.heappop(ppl)) // 10
    heapq.heappush(ppl, -current)

print(sum(-x for x in ppl), file=open("output.txt", 'w'))

哈斯克尔代码：

import Data.List hiding (insert, singleton)

type Rank = Int

data Heap a = Tip | Node Rank Int (Heap Int) (Heap Int)

rank Tip = 0
rank (Node r _ _ _) = r

fromList :: [Int] -> Heap Int
fromList [] = Tip
fromList (x:xs) = foldl' (flip insert) (singleton x) xs

makeHeap :: Int -> Heap Int -> Heap Int -> Heap Int
makeHeap x a b = if rank a >= rank b then Node (rank b + 1) x a b
                                     else Node (rank a + 1) x b a

empty :: Heap a
empty = Tip

singleton :: Int -> Heap Int
singleton x = Node 1 x Tip Tip

insert :: Int -> Heap Int -> Heap Int
insert x = merge (singleton x)

merge :: Heap Int -> Heap Int -> Heap Int
merge l Tip = l
merge Tip r = r
merge h1@(Node _ x l1 r1) h2@(Node _ y l2 r2) =
  if x > y then makeHeap x l1 (merge r1 h2)
            else makeHeap y l2 (merge h1 r2)

-- | O(1).
peek :: Heap Int -> Int
peek Tip = 0
peek (Node _ x _ _) = x

-- | O(1), but evaluating the second element of the tuple has same complexity
-- of `merge`.
extract :: Heap Int -> (Int, Heap Int)
extract (Node _ x a b) = (x, merge a b)

toSum :: Heap Int -> Int
toSum Tip            = 0
toSum (Node _ x a b) = x + toSum a + toSum b 

solve :: Int -> Heap Int -> Int
solve 0 heap = toSum heap
solve _ (Node _ 0 _ _) = 0
solve sips ppl = solve (sips - 1) (insert (val `div` 10) h)
    where (val, h) = extract ppl
    


main :: IO()
main = do
    line <- readFile "input.txt"
    let _:volume:ppl = map(read :: String -> Int) $ words line
    let heap = fromList ppl
    writeFile "output.txt" $ show $ solve volume heap

借用的问题位于结果表的以下部分：

N 次测试	判决	时间（秒）python	时间（秒）Haskell
19	好的	0.0312	0.0156
20	好的	0.0624	0.172
21	好的	0.078	0.733
22	好的	0.234	1.34
23	好的	0.218	1.34

测试本身对我来说不可用。

所以...似乎我的 Haskell 代码由于某种原因在大量值（~10^5）的情况下明显变慢。 有人可以解释一下原因以及如何解决吗？

Answer 1

最有可能的问题是读取输入文件而不是你的算法。

当我对读取一百万个整数并用 Python 对它们求和进行基准测试时：

ppl = map(int, open("random.dat").read().split())
print(sum(ppl))

我得到的基线时间约为 100 毫秒。

如果我将其与根据您的 Haskell 代码构建的版本进行比较：

main :: IO()
main = do
    line <- readFile "random.dat"
    let ppl = map (read :: String -> Int) $ words line
    print $ sum ppl

大约需要 950 毫秒。 噢！

从这个

String

实现切换到惰性

ByteString

:

import qualified Data.ByteString.Lazy as BL
import qualified Data.ByteString.Lazy.Char8 as BL

main :: IO()
main = do
    line <- BL.readFile "random.dat"
    let ppl = [n | w <- BL.words line, let Just (n, _) = BL.readInt w]
    print $ sum ppl

将其降至 43 毫秒。

那么，尝试一下吧。