4

より専門的なコードに対してテストしたいルビーでの最小ヒープの実装がありましたが、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"

私が持っているバージョンは、100,000 個の値に対して同じポップ操作を ~2.2 秒で実行します。これは非常に遅いと思いましたが、これは実行を終了することさえできません。それは期待されていますか、それとも私は何か間違っていますか？

4

1 に答える 1

3

あなたが何か間違ったことをしているとは思いません。

ソース ( https://github.com/kanwei/algorithms/blob/master/lib/containers/heap.rb ) を見て、ヒープの設定が終わったら puts ステートメントを入れます。要素を配置するのは非常にメモリを集中的に使用する操作のように見えます (毎回再利用する可能性があります)。

また、彼が実際のノードごとにノード クラスを作成しているのかどうかもわかりません。それらはクリーンアップされないため、完了するまでにメモリ内に約 100,000 個のオブジェクトが存在することになります。

それがどれだけの助けになるかわからない場合は、ソースがあなたの試みとどのように異なるかを確認してください。

于 2012-12-20T19:36:48.110 に答える