ruby - Kanwei minheap 慢红宝石

Question

我在 ruby​​ 中实现了一个最小堆，我想针对更专业的代码进行测试，但我无法让 Kanwei 的 MinHeap 正常工作。这个：

mh = Containers::MinHeap.new # Min_Binary_Heap.new
for i in 0..99999
    mh.push(rand(9572943))
end

t = Time.now
for i in 0..99999
    mh.pop
end
t = Time.now - t
print "#{t}s"

我的版本在 2.2 秒内对 100,000 个值执行相同的弹出操作，我认为这非常慢，但这甚至不会完成运行。这是预期的还是我做错了什么？

Answer 1

我不认为你做错了什么。

查看源代码（https://github.com/kanwei/algorithms/blob/master/lib/containers/heap.rb），在完成堆设置时放置一个 puts 语句。将元素放入（可能每次都使用）看起来像是一个非常占用内存的操作，因此它可能会帮助您完成它。

我也不确定他是否为每个实际节点创建一个节点类。由于它们不会被清理，所以当你完成时，内存中将有大约 100,000 个对象。

不确定这有多少帮助，也许看看来源与您的尝试有何不同？