doubleキーの優先度として定数値を使用する優先度キューの実装を探しています。これを適切に実装すればPriorityQueue、柔軟なコンパレータを使用したデフォルトの実装よりも高速になると思います。decreaseKey操作（=すでにキューにある要素の優先度を下げる）は必要ありません。
スタンフォードのNLPグループから実装を見つけましたが、元の実装の2倍遅いと彼らは主張しています。PriorityQueueユースケースのデフォルトを上回るPQ実装はありますか？
質問する
733 次
3 に答える
0
Sedgewick-Wayneコードを使用してみてください
http://algs4.cs.princeton.edu/24pq/MaxPQ.java.html
ただし、汎用キータイプをdoubleに置き換え、Comparable/Comparatorコードを削除してください。
于 2012-06-26T10:44:37.843 に答える
0
引用するStanfordNLPバージョンの速度が遅いのは、decreaseKey（）をサポートしているためです。Javadocで述べられているように、decreaseKey（）をサポートしていないこのクラスを試すことができます。
于 2012-06-27T05:55:55.913 に答える
0
最終的に、独自のヒープ構造を実装しました。最適化された操作を備えたd-aryヒープはremove()、特にロードされた共有メモリマシンで、適度に良好に機能することが判明しました。
于 2012-07-15T02:47:05.627 に答える