16

哪个实现不那么“重”：PriorityQueue 或排序的 LinkedList（使用比较器）？

我想对所有项目进行排序。插入将非常频繁，有时我将不得不运行所有列表来进行一些操作。

4

11 回答 11

32

ALinkedList是最坏的选择。要么使用ArrayList（或更一般地，RandomAccess实现者），要么使用PriorityQueue. 如果您确实使用列表，请仅在迭代其内容之前对其进行排序，而不是在每次插入之后进行排序。

需要注意的一点是，PriorityQueue迭代器没有按顺序提供元素；您实际上必须删除元素（清空队列）才能按顺序迭代其元素。

于 2010-05-20T22:01:29.727 回答
5

您应该同时实现这两种方法，然后对实际数据进行性能测试，看看哪种方法在您的特定情况下效果最好。

于 2010-05-20T21:52:26.863 回答
3

我在这个问题上做了一个小基准。如果您希望在所有PriorityQueue插入结束后对列表进行排序，那么和之间几乎没有区别LinkedList（LinkedList 好一点，在我的机器上快 5% 到 10%），但是如果您使用 ArrayList，您将得到几乎 2比 PriorityQueue 中的排序快几倍。

在我的列表基准测试中，我测量了从开始填充值到排序结束的时间。对于 PriorityQueue - 从填充开始到轮询所有元素结束（因为元素在 PriorityQueue 中排序，同时删除它们，如埃里克森回答中所述）

于 2012-10-18T21:53:37.963 回答
2

如果您使用 a LinkedList，则每次添加项目时都需要重新使用这些项目，并且由于插入频繁，我不会使用 a LinkedList。所以在这种情况下，我会使用 a PriorityQueue's 如果您只向列表中添加唯一元素，我建议使用 a SortedSet（一种实现是TreeSet）。

于 2010-05-20T21:57:06.727 回答
2

将对象添加到优先级队列将是 O log(n) 并且对于每个 pol 都相同。如果您经常在非常大的队列上进行插入，那么这可能会影响性能。插入到 ArrayList 的顶部是恒定的，因此总的来说，所有这些插入在 ArrayList 上的速度都会比在优先级队列上的速度快。

如果您需要按排序顺序获取所有元素，Collections.sort 将在大约 On log (n) 时间内工作。由于优先级队列中的每个 pol 将是 O log(n) 时间，所以如果你从队列中抓取所有 n 个东西，它将再次是 On log(n)。

优先队列获胜的用例是，如果您试图在任何给定时间查找队列中的最大值是什么。要使用 ArrayList 做到这一点，每次您想知道最大的时候，您必须对整个列表进行排序。但是对于优先级队列，它总是知道最大的价值是什么。

于 2013-09-21T22:34:31.290 回答
1

这两种数据结构之间存在根本区别，它们并不像您想象的那么容易互换。

根据 PriorityQueue 文档：

方法 iterator() 中提供的 Iterator 不能保证以任何特定顺序遍历优先级队列的元素。

仅在迭代列表之前使用 ArrayList 并在其上调用 Collections.sort()。

于 2010-05-20T22:11:10.407 回答
1

问题PriorityQueue是您必须清空队列才能按顺序获取元素。如果这是您想要的，那么这是一个不错的选择。否则，您可以ArrayList仅在需要排序结果时使用排序的，或者，如果项目不同（相对于比较器），则使用TreeSet. TreeSet就空间而言，两者ArrayList都不是很“重”；哪个更快取决于用例。

于 2010-05-20T22:18:10.323 回答
0

您是否需要随时对其进行分类？如果是这种情况，您可能想要使用类似树集（或其他具有快速查找的 SortedSet）的东西。

如果您只需要偶尔对其进行排序，请使用链表并在需要访问时对其进行排序。当您不需要访问时，让它未排序。

于 2010-05-20T21:58:02.090 回答
0

java.util.PriorityQueue是

“基于优先级堆的无界优先级队列”

. 堆数据结构比链表更有意义

于 2010-05-20T22:00:01.773 回答
0

我可以看到两个选项，哪个更好取决于您是否需要能够拥有重复的项目。

如果您不需要维护列表中的重复项，我会使用 SortedSet（可能是 TreeSet）。

如果您需要维护重复的项目，我会使用 LinkedList 并以正确的顺序将新项目插入列表中。

除非您想在执行操作时删除项目，否则 PriorityQueue 并不真正适合。

与其他人一起，确保您使用分析来确保为您的特定问题选择正确的解决方案。

于 2010-06-05T19:24:06.270 回答
-1

恕我直言：如果有 LinkedList，我们不需要 PriorityQueue。我可以使用 LinkedList 比使用 PriorityQueue 更快地对队列进行排序。例如

Queue list = new PriorityQueue();
list.add("1");
list.add("3");
list.add("2");
while(list.size() > 0) {
    String s = list.poll().toString();
    System.out.println(s);
}

我相信这段代码工作时间太长，因为每次我添加元素时它都会对元素进行排序。但如果我将使用下一个代码：

Queue list = new LinkedList();
list.add("1");
list.add("3");
list.add("2");
List lst = (List)list;
Collections.sort(lst);
while(list.size() > 0) {
    String s = list.poll().toString();
    System.out.println(s);
}

I think this code will sort only once and it will be faster that using PriorityQueue. So, I can once sort my LinkedList once, before using it, in any case and it will work faster. And even if it sort the same time I don't really need PriorityQueue, we really don't need this class.

于 2016-07-18T15:39:54.597 回答