一千萬個為什麽

搜索

在顯示進度時對大型集合進行排序

更新進度條時對集合進行排序的最佳方法是什麽?目前我的代碼如下:

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的解決方案,因為它非常幹凈,並允許我輕松添加多線程排序算法。

最佳答案

你想在這裏小心。您已選擇使用逐步構建排序數據結構的算法,以便(我接受)您可以顯示進度條。但是,在執行此操作時,可能選擇的排序方法明顯慢於最佳排序。 (兩種排序都是 O(NlogN)但是性能要比big-O行為更多......)

如果您擔心這可能是一個問題,請比較使用 TreeMapCollections.sort 對典型集合進行排序的時間。後者的工作原理是將輸入集合復制到數組中,對數組進行排序,然後將其復制回來。 (效果最好 如果輸入集合是ArrayList。如果您不需要將結果作為可變集合,則可以使用 Collection.toArrayArrays.sortArrays.asList <�來避免最終復制。/code>而不是。)

另一種想法是使用Comparator對象來跟蹤它被調用的次數,並使用它來跟蹤排序的進度。您可以利用比較器通常被稱為大約 N * log(N)次的事實,盡管您可能需要根據使用的實際算法校準 1

順便提一下,計算對比較器的調用將比通過計算插入數量更好地指示進度。當您接近完成排序時,您不會看到進度速度變慢。

(您將有不同的線程讀取和寫入計數器,因此您需要考慮同步。將計數器聲明為 volatile 將會起作用,代價是額外的內存流量。您也可以忽略該問題如果您對進度條感到高興,有時會顯示陳舊的價值......取決於您的平臺等)


1 - 這有問題。存在一些算法,其中比較的數量可以根據被分類的數據的初始順序而急劇變化。對於這樣的算法,沒有辦法校準將在“非平均”情況下工作的計數器。

轉載註明原文: 在顯示進度時對大型集合進行排序