java - 使用 ArrayList 的优先级队列的性能

Question

我目前正在开发一个最小优先级队列，该队列在添加项目时保持自身排序。建议的实现将新项目添加到已排序的 ArrayList 的末尾，然后返回列表以找到项目的正确位置。因此，它会与列表中的每个先前元素交换，直到添加的项目按顺序排列。

在建议使用此方法之前，我使用的实现涉及通过排序列表进行比较，标记要插入项目的索引，然后使用 Java 的 add(int index, Object O) 方法，而不是仅添加到末尾。

我试图了解两者之间的性能差异。我知道如果我插入，所有尾随索引都必须被纠正(这是由类方法处理的)。但这真的比通过列表交换回来效率低吗？

预先感谢您的任何解释

Answer 1

如上所述，这两个选择都将在 O(n) 时间内运行(我认为)。然而，第二个选项(即您的初始实现)可能会有更好的常数因子，因为一次移动一组元素可能(并且可能会)比一次移动一个元素更有效，特别是如果您必须移动一大组元素。因此，我想说，您的初始实现效率更高，除非您的最终插入点几乎总是靠近数组末尾，此时 System.arraycopy() 的开销可能会主导完成实际工作所需的时间 - 但不会太多。

我想您可以将这两种情况视为近似比较冒泡排序(建议实现)和插入排序(初始实现)的单次迭代。两者具有相同的时间复杂度，但由于操作较少，插入排序的单次迭代几乎总是(或者也许总是？)运行得更快。

以此为例(为简单起见，假设可调整大小的数组):

int[] a = new int[] {1, 2, 4, 5};

并说您要插入3。

您的初始实现将如下所示:

1. 查找要插入的索引。 3 次比较以找到 index == 2。
2. 在索引 > 2 处移动元素。2 次操作:将 5 移动一位，将 4 移动一位。 (这可能是一项操作，具体取决于 System.arraycopy() 的实现方式)。结果是 {1, 2, 0, 4, 5}
3. 插入元素。 1 操作。最终结果为{1, 2, 3, 4, 5}。

总计:3 次比较，3 次操作。

您的新实现将如下所示:

1. 在末尾插入元素。 1 操作。结果为 {1, 2, 4, 5, 3}。
2. 比较一下是否需要交换。 1比较。需要交换。
3. 交换。 3 个操作:将 5 分配给临时变量，将 3 分配给索引 3，将临时变量分配给索引 4。结果为 {1, 2, 4, 3, 5}
4. 比较一下是否需要交换。 1比较。需要交换。
5. 交换。 3 个操作:将 4 分配给临时变量，将 3 分配给索引 2，将临时变量分配给索引 3。结果为 {1, 2, 3, 4, 5}。
6. 比较一下是否需要交换。 1比较。无需交换。完成。

总计:3 次比较，7 次操作。

顺便说一句，您可能最好使用二分搜索来查找插入点，而不是直接线性搜索。