在显示进度的同时对大型集合进行排序

Question

更新进度条时对集合排序的最佳方法是什么？目前，我有这样的代码：

for (int i = 0; i < items.size(); i++)
{
    progressBar.setValue(i);

    // Uses Collections.binarySearch:
    CollectionUtils.insertInOrder(sortedItems, item.get(i));
}

这显示进度，但是进度条随着项目数量的sortedItems增加而减慢。有谁有更好的方法？理想情况下，我想使用类似于的接口，Collections.sort()以便尝试不同的排序算法。

任何帮助将是巨大的！

作为背景，这段代码正在从Lucene撤回许多文档（1到1000万个），并在它们之上运行自定义比较器。通过将数据写回到磁盘上对它们进行排序将太慢而无法实用。大部分成本是从磁盘上读取项目，然后在项目上运行比较器。我的电脑有大量的内存，因此没有与交换到磁盘等有关的问题。

最后，我选择了Stephen的解决方案，因为它非常干净，使我可以轻松添加多线程排序算法。

Answer 1

您在这里要小心。您已选择使用一种算法来增量构建排序的数据结构，以便（我接受）您可以显示进度条。但是，这样做时，您选择的排序方法 可能
比最佳排序慢得多。（两种类型都可以，O(NlogN)但是性能要比big-O行为更多…）

如果您担心这可能是个问题，请比较使用TreeMap和对典型集合进行排序的时间Collections.sort。后者的工作方式是将输入集合复制到数组中，对数组进行排序，然后再将其复制回。（它的工作原理最好的，如果在输入集合是一个ArrayList，如果你不需要结果作为可变集合就可以避免使用最终拷贝过来的Collection.toArray，Arrays.sort并Arrays.asList代替。）

一种替代方法是使用Comparator对象，该对象跟踪被调用的次数，并使用该对象跟踪排序的进度。您可以利用以下事实：比较器通常会被粗略调用N*log(N)，尽管您可能需要根据实际使用的算法1对其进行校准。

顺便说一下，与对插入次数进行计数相比，对比较器的调用进行计数可以更好地指示进度。当您接近完成排序时，您将不会看到进度出现放缓的趋势。

（您将拥有不同的线程来读取和写入计数器，因此您需要考虑同步。声明计数器volatile可以正常工作，但会增加内存流量。如果您对进度条感到满意，也可以忽略该问题有时会显示过时的值…具体取决于您的平台等）

1-这有问题。在某些算法中，比较次数可能会根据要排序的数据的初始顺序而急剧变化。对于这种算法，没有办法校准将在“非平均”情况下工作的计数器。