1

我正在寻找一个优先级队列的实现,它使用常double量值作为键的优先级。我相信,如果实施得当,这可以比PriorityQueue使用灵活比较器的默认实施更快。不需要减少键操作(=降低队列中已有元素的优先级)。

从斯坦福的 NLP 小组找到了一个实现,但他们声称它的速度是原始实现的两倍。是否有一个 PQ 实现可以胜过PriorityQueue我们用例的默认实现?

4

3 回答 3

0

我们最终实现了我们自己的堆结构。具有优化remove()操作的 d-ary 堆结果证明性能相当好,尤其是在加载的共享内存机器上。

于 2012-07-15T02:47:05.627 回答
0

尝试使用 Sedgewick-Wayne 代码

http://algs4.cs.princeton.edu/24pq/MaxPQ.java.html

但用 double 替换通用 Key 类型并删除 Comparable/Comparator 代码。

于 2012-06-26T10:44:37.843 回答
0

您引用的斯坦福 NLP 版本的速度较慢是因为它确实支持 reduceKey()。正如其 Javadoc 中所提到的,您可以尝试这个不支持 reduceKey() 的类:

http://www.jarvana.com/jarvana/view/edu/stanford/nlp/stanford-corenlp/1.3.0/stanford-corenlp-1.3.0-javadoc.jar!/javadoc/edu/stanford/nlp/util /FixedPrioritiesPriorityQueue.html

于 2012-06-27T05:55:55.913 回答