Сравнение скорости Haskell, Python (куча // очередь приоритетов) ⇐ Python

[Anonymous]

Мне нужно решить проблему. Детали этого в принципе не имеют значения, и у меня есть два подходящих решения: на 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'))

Код на Haskell:

Код: Выделить всё

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


< td>22
ОК
0,234
1,34


23
ОК
0,218
1.34



Сами тесты мне недоступны.
Итак... Похоже, мой код на Haskell по какой-то причине работает значительно медленнее с большим количеством значений (~ 10^5).
Может кто-нибудь объяснить мне, почему и как это исправить ?

Подробнее здесь: https://stackoverflow.com/questions/791 ... rity-queue