Java：排序的集合，允許重複，提高內存效率，並提供快速插入+更新

Question

具體而言，我需要一個集合，它使用一個字段A進行訪問，另一個（字段S）進行排序，但是一個接受重複的排序集合就足夠了。

我經常到這裏，我需要這個集合和TreeMap不是一個選項，因爲它不允許重複。所以現在是時候在這裏問問了。還有的指出了計算器here和here幾種解決方法 - 即有：

• 的PriorityQueue：更新緩慢（刪除（對象）+新增（對象）），和原始的鑰匙
• 的拳擊斐波那契堆：（？）浪費內存
• TreeMap<Field_S, List<Value>>：我的問題是列表的內存開銷，和原始密鑰的拳擊
• 排序列表或數組：問題是緩慢的插入和刪除 - >我應該實現一個分段的排序列表？
• TreeMultimap從番石榴（docs）：（？）對外依存度大概內存低效

任何人只要有更好的建議？或者我應該扮演我自己的排序數據結構（哪一個？）？另外其他來源（在Java中，開源，單元測試和小代價）會很好。

---

更新我的使用情況下，在時刻

更多細節（雖然我有在最後一次類似的需求）。我有一個集合（以百萬計），我希望能夠

• 輪詢或領域的
• 值相同的幫助下獲得的最小元素有關S區域
• 和更新S區域的引用的字段S可能發生。字段A實際上是指向另一個數組的一個整數
• 我想要的唯一依賴項是trove4j。如果需要的話，我可以使用不同的mahout集合。但不是番石榴，雖然這是一個很好的庫，但這些集合沒有被調整爲高效內存（裝箱/拆箱）。

因此，所有對斐波那契堆的呼聲，但我擔心它有太多的元素開銷 - >這是我想到更高效的內存「排序+分段數組」的解決方案的原因。

Answer 1

我決定推出我自己的但不是最佳的解決方案只是一個TreeMap變種。如果我對這個集合關於內存進行微調，我會保持更新。因爲我需要這個集合，速度已經比先前的PriorityQueue嘗試好很多了。除去（Object）方法（用於更新的條目）：

package com.graphhopper.coll; 

import gnu.trove.iterator.TIntIterator; 
import gnu.trove.set.hash.TIntHashSet; 
import java.util.Map.Entry; 
import java.util.TreeMap; 

/** 
* A priority queue implemented by a treemap to allow fast key update. Or should we use a standard 
* b-tree? 
*/ 
public class MySortedCollection { 

    private int size; 
    private int slidingMeanValue = 20; 
    private TreeMap<Integer, TIntHashSet> map; 

    public MySortedCollection(int size) { 
     map = new TreeMap<Integer, TIntHashSet>(); 
    } 

    void remove(int key, int value) { 
     TIntHashSet set = map.get(value); 
     if (set == null || !set.remove(key)) 
      throw new IllegalStateException("cannot remove key " + key + " with value " + value 
        + " - did you insert " + key + "," + value + " before?"); 
     size--; 
     if (set.isEmpty()) 
      map.remove(value); 
    } 

    public void update(int key, int oldValue, int value) { 
     remove(key, oldValue); 
     insert(key, value); 
    } 

    public void insert(int key, int value) { 
     TIntHashSet set = map.get(value); 
     if (set == null) 
      map.put(value, set = new TIntHashSet(slidingMeanValue)); 
//  else 
//   slidingMeanValue = Math.max(5, (slidingMeanValue + set.size())/2); 
     if (!set.add(key)) 
      throw new IllegalStateException("use update if you want to update " + key); 
     size++; 
    } 

    public int peekValue() { 
     if (size == 0) 
      throw new IllegalStateException("collection is already empty!?"); 
     Entry<Integer, TIntHashSet> e = map.firstEntry(); 
     if (e.getValue().isEmpty()) 
      throw new IllegalStateException("internal set is already empty!?"); 
     return map.firstEntry().getKey(); 
    } 

    public int peekKey() { 
     if (size == 0) 
      throw new IllegalStateException("collection is already empty!?"); 
     TIntHashSet set = map.firstEntry().getValue(); 
     if (set.isEmpty()) 
      throw new IllegalStateException("internal set is already empty!?"); 
     return set.iterator().next(); 
    } 

    public int pollKey() { 
     size--; 
     if (size < 0) 
      throw new IllegalStateException("collection is already empty!?"); 
     Entry<Integer, TIntHashSet> e = map.firstEntry(); 
     TIntHashSet set = e.getValue(); 
     TIntIterator iter = set.iterator(); 
     if (set.isEmpty()) 
      throw new IllegalStateException("internal set is already empty!?"); 
     int val = iter.next(); 
     iter.remove(); 
     if (set.isEmpty()) 
      map.remove(e.getKey()); 
     return val; 
    } 

    public int size() { 
     return size; 
    } 

    public boolean isEmpty() { 
     return size == 0; 
    } 

    public int getSlidingMeanValue() { 
     return slidingMeanValue; 
    } 

    @Override 
    public String toString() { 
     return "size " + size + " min=(" + peekKey() + "=>" + peekValue() + ")"; 
    } 
} 

Answer 2

番石榴TreeMultiset？你所要求的：一個接受重複的排序後的集合。儘管對它的表現一無所知。

Answer 3

當您需要排序的集合時，您應該仔細分析您的需求。
如果大部分操作是插入並且只有少數操作是使用排序後的集合進行搜索即保持元素在中的排序總是，這不是一個好的選擇（由於保持元素在insert上的排序是最常見的操作）。
在這種情況下，最好保留未排序的集合，並僅在需要時進行排序。即在搜索之前。您甚至可以使用簡單的List並在需要時對其進行分類（使用Collections.sort即mergesort）。但我謹慎地推薦這一點，因爲這是有效率的，因此假設您正在處理大量數據。在非常小的數據中，即使是線性搜索也足夠了。

如果大多數操作是搜索那麼你可以使用一個有序集合，從我的觀點有數據結構從（有些你已經提到）來選擇，你可以基準，看看哪一個適合你的需要。

Answer 4

我有TreeMultimap http://guava-libraries.googlecode.com/svn/tags/release05/javadoc/com/google/common/collect/TreeMultimap.html

Answer 5

你需要決定是否要外部依賴或沒有很好的經驗。我不會推出我自己的實現這樣的事情。

也就是說，您幾乎沒有告訴我們您使用此功能的內容以及您打算如何使用此功能。沒有足夠的數據，只有很多我們可以告訴你 - 你是否真的需要隨機訪問元素？你認爲這個系列有多大？我們實際上沒有足夠的數據來根據您的需求選擇合適的數據結構。

這就是說，這裏有一些選擇，我會考慮。

• ArrayList或PriorityQueue，這取決於你是否真的需要支持remove(Object)。你做？你是肯定？ （即使您確實需要支持remove(Object)，如果收藏可能會保持較小，我會選擇此選項。）
• 不是您鏈接到的TreeList，而是Apache Commons Collections TreeList。儘管有這個名字，它並沒有實際維護排序的順序，但它所做的是支持O（log n）添加，刪除和從列表中的任何位置獲取。使用二分搜索，您可以根據值的排序部分，實現O（（log n）^ 2）時間，用於添加，刪除或查找。
• 您鏈接到的TreeList或者 - 如果您像我一樣關心List合同 - 自定義番石榴ListMultimap，用獲得。

如果你還在乎原始拳擊，或不能耐受第三方依賴，你將別無選擇，只能寫你自己的數據結構。我只是將上面的一個實現適應到您的原始類型，但這將是一個皇家的痛苦。

終於：我會真的喜歡聽你的用例。番石榴對這樣的事情沒有任何支持，因爲我們沒有足夠的需求，或者看到一個更復雜的數據結構真正適合的用例。

Answer 6

我會去與skiplist - 更多的內存比樹高效，允許重複，對於插入物提供了O（logn）時間和刪除。你甚至可以實現一個索引的跳過列表，它可以讓你有索引訪問，這是一個很難用樹得到的東西。