在JAVA中訂購一個沒有重複的集合

我需要使用自定義比較器來訂購一個集合而不在內存中複製它。在JAVA中訂購一個沒有重複的集合

天真的實現將是：

Set<MyClass> newSet = new TreeSet<>(myComparator); 
newSet.addAll(oldSet);

但是這將意味着，即使在有限的時間，我有兩套內存：oldSet（無序）和newSet（有序）。由於它們會非常大，我想避免這種情況。

我想這樣的事情進行：

oldSet = new TreeSet<>(oldSet, myComparator);

這實際上是不可能的，因爲沒有構造函數TreeSet中採用這種結構形式。

難道這是一個解決方案？

Iterator<MyClass> it = oldSet.iterator(); 
Set<MyClass> newSet = new TreeSet<>(myComparator); 
while(it.hasNext()) 
{ 
    newSet.add(it.next()); 
    it.remove(); 
}

更好的建議？

謝謝

來源

2013-12-20 user1923631

@kai沒有'it.remove（）'OP將一次在內存中有兩個全集，這是他的問題所在。 –

你作爲一個Set沒有被定義有序，沒有辦法訂購Set，所以（因爲你這樣做），你必須使用一個有序的數據結構。但是，如果您執行addAll，Java不會執行您所看到的問題，Java將不會執行Set的深層副本，它只會複製幾乎不使用RAM的引用。

因此，您的addAll解決方案是一個乾淨和正確的解決方案。

來源

2013-12-20 11:31:13 LionC

「由於'Set'沒有按照定義排序，所以沒有辦法訂購'Set'」否，Java中的Set僅僅是無序的，除非另有規定。 'SortedSet'（其中'TreeSet'是一個實現）的合約保證了這些項目有一個明確定義的順序。 – Smallhacker

@Smallhacker我在說一個Set，如果你有一個Set，它沒有命令，期間。 TreeSet是一個特殊的Set，它改變了這個行爲 – LionC

啊，所以你的意思是「沒有辦法訂購一個Set _that還沒有ordered_」？好吧，那時我很糟糕。 – Smallhacker

如果你能空的所有引用到老的做

newSet.addAll(oldSet); 
oldSet = null;

如果你不能爲null所有舊組使用Set.clear方法的引用

newSet.addAll(oldSet); 
oldSet.clear();

注意，後清除HashSet的內部哈希表不會縮小

來源

2013-12-20 11:36:11

哈希表可能會保留，但所有'Map.Entry's都將消失。 –

使用TreeSet不會是最高效的內存，它甚至不會是最快的方法。

您應該使用ArrayList和執行上有一個排序：

List<MyClass> sorted = new ArrayList<>(oldSet.size()); 
oldSet = null; 
Collections.sort(sorted, myComparator);

內ArrayList使用單個陣列的開銷不應該是一個問題，在任何情況下，你可以有最小的問題。

單次批量排序操作比找到TreeSet中每個單獨項目的正確位置以及此時所需的所有分配要快。

來源

2013-12-20 11:49:48

好吧，我期望'n日誌n'批量Collection.sort（mergesort）和TreeSet插入（n個插入每個日誌n） –

@guido這是常數因素，而不是抽象的複雜性。 –

如果你擔心在內存中對數組進行排序的常量因素，你應該檢查你的基礎設施.. :)只是chitchatting，其實我會提出相同的答案，我喜歡，如果你還沒有，所以你會得到我的+1 –

當您在構造函數中使用set創建集合時，您將創建燕子副本。您僅複製參考。當你刪除你也刪除引用。這是在下面的代碼可見：

MyComparator myComparator = new MyComparator(); 
Set<Object> newSet = new TreeSet<>(myComparator); 
Object mc = new Object(); 
newSet.add(mc); //set is created 

Set<Object> newerSet = new TreeSet<>(myComparator); 
newerSet.addAll(newSet); 
System.out.println(newSet); 
System.out.println(newerSet);

輸出： [[email protected]] [java.lang中。Object @ 1bb1deea]

引用同一個對象。

newerSet.remove(mc); 
System.out.println("After deletion"); 
System.out.println(newSet); 
System.out.println(newerSet);

缺失後[[email protected]] []

僅參照被去除。

來源

2013-12-20 11:50:09 Pawel

您應該編寫一個Iterator實現，其中每次調用next()都會爲您提供下一個已排序的項目。它不會佔用額外的內存，但與複製無序的Set相比，額外內存的數量很小。你也不會有新的Set，但你可以遍歷它。

低內存版本，但效率低下的算法會將最近訪問的項目存儲在Iterator中。每次您需要退回下一個物品時，您都會查看襯墊Set中的所有物品，找出下一個物品。

來源

2013-12-20 12:02:12 dbrown0708

在JAVA中訂購一個沒有重複的集合

回答

相關問題