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

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-10百万个)并在它们上面运行自定义比较器.通过将数据写回磁盘来对它们进行排序将太慢而不实用.大部分成本是从磁盘上读取项目,然后在项目上运行比较器.我的电脑有大量内存,所以没有与交换到磁盘等有关的问题.

最后我选择了Stephen的解决方案,因为它非常干净,并允许我轻松添加多线程排序算法.

Answer 1

你想在这里小心.您已选择使用逐步构建已排序数据结构的算法,以便(我接受)您可以显示进度条.但是,在执行此操作时,您可能选择了比最佳排序慢得多的排序方法.(两种类型O(NlogN)都有,但性能比大O行为更多......)

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

另一种想法是使用Comparator对象来跟踪它被调用的次数,并使用它来跟踪排序的进度.您可以利用比较器通常大致会被调用的事实N*log(N),尽管您可能需要针对所使用的实际算法进行校准¹.

顺便提一下,计算对比较器的调用将比通过计算插入数量更好地指示进度.当您接近完成排序时,您不会看到进度速度变慢.

(您将有不同的线程读取和写入计数器,因此您需要考虑同步.volatile以额外的内存流量为代价来声明计数器.如果您对进度条感到满意,也可以忽略该问题有时显示陈旧的价值......取决于您的平台等)

^{1 - 这有问题.存在一些算法,其中比较的数量可以根据被分类的数据的初始顺序而急剧变化.对于这样的算法,没有办法校准将在"非平均"情况下工作的计数器.}