高效存儲一組數字

我正在尋找最有效的方式來存儲整數集合。現在他們被存儲在一個HashSet<T>，但分析表明，這些集合嚴重影響一些性能關鍵的代碼，我懷疑有更好的選擇。高效存儲一組數字

更多的細節：

隨機查找必須是O（1）或接近它。
集合可以增長很大，所以空間效率是可取的。
這些值均勻分佈在64位空間中。
可變性不是必需的。
尺寸沒有明確的上限，但數千萬個元素並不少見。

現在最痛苦的表現就是創造它們。這似乎與分配有關 - 清除和重用HashSet s在基準測試中有很多幫助，但不幸的是這在應用程序代碼中並不可行。

（增加）實現一個適合任務的數據結構很好。散列表仍然是一種方式嗎？乍一看似乎也是一種可能性，但我對它們沒有任何實際的經驗。

來源

2012-01-19 Sean U

您打算存儲的值是否有上限？「大」有多大？ – dasblinkenlight

你大部分時間在哪裏度過？閱讀或寫入集合？ –

什麼其他數據與整數相關聯？它實際上只是一堆整數還是有其他數據懸掛？（換句話說，「隨機查找」是什麼意思？） – cdeszaq

我決定嘗試並實現使用線性探測處理衝突的特殊用途的基於散列的集合類：

後備存儲long小號
數組的一個簡單的數組的大小是大於要存儲的元素的預期數量。
對於值的散列碼，使用最低有效位31位。

搜索在後備存儲器中的值的位置用一個基本的線性探針完成的，像這樣：

int FindIndex(long value) 
{ 
    var index = ((int)(value & 0x7FFFFFFF) % _storage.Length; 
    var slotValue = _storage[index]; 

    if(slotValue == 0x0 || slotValue == value) return index; 

    for(++index; ; index++) 
    { 
     if (index == _storage.Length) index = 0; 
     slotValue = _storage[index]; 
     if(slotValue == 0x0 || slotValue == value) return index; 
    } 
}

（I能夠確定將永遠不會包括0正被存儲的數據，因此該號碼可安全用於空插槽。）

數組需要大於存儲的元素數。（加載因子小於1.）如果該集合被完全填充，那麼FindIndex()將用於搜索尚未在該集合中的值的無限循環。實際上，它將需要相當多的空白空間，否則當數據開始形成大塊時，搜索和檢索可能會受到影響。

我相信還有優化的空間，我可能會被卡住，使用某種BigArray<T>或分支爲大型集中的後備商店。但最初的結果是有希望的。在負載因子爲0.5的情況下，它的執行速度是HashSet<T>的兩倍，幾乎是負載因子爲0.8的兩倍，即使在0.9時，測試中的速度仍然快40％。

開銷是1/load factor，所以如果這些性能數據在現實世界中保持不變，那麼我相信它也會比HashSet<T>更具有內存效率。我還沒有做過正式的分析，但根據HashSet<T>的內部結構判斷，我很確定它的開銷遠高於10％。

所以我用這個解決方案很高興，但我仍然有其他可能性好奇。也許某種特里？

結語：終於可以對實時數據做這與HashSet<T>的一些有競爭力的基準。（在我使用合成測試集之前）它甚至比我之前的樂觀期望更勝一籌。真實世界的性能比起HashSet<T>要快6倍，具體取決於系列的大小。

來源

2012-01-20 01:42:08

我會做的只是創建一個足夠大小的整數數組來處理您需要的整數。是否有任何理由遠離通用List<T>？ http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx

來源

2012-01-19 18:33:30 DanielG

*「查找必須是O（1）或接近它」* – BrokenGlass

HashSet通常是在這種情況下最好的通用收集。

如果您有關於您的收藏的任何具體信息，您可能有更好的選擇。

如果你有一個固定的上界不是非常大，你可以使用合適大小的位向量。

如果您有一個非常密集的集合，您可以改爲存儲缺少的值。

如果你有非常小的集合，< = 4項左右，你可以將它們存儲在一個普通的數組中。對這種小陣列的全面掃描可能比使用散列集所需的散列更快。

如果您的數據沒有比「int的大型集合」更具體的特徵，則需要HashSet。

來源

2012-01-19 18:35:39

我擔心它不是。例如，'HashSet '既存儲值又存儲哈希碼。在這種情況下，數據可以是自己的哈希碼，但這樣做是不必要的空間使用。它使集合體更緊湊，也更慢（冗餘比較，緩存友好性更低，＆c）。 –

如果值的大小有界，可以使用bitset。它每個整數存儲一位。總的來說，內存的使用應該是log n位，其中n是最大的整數。

另一種選擇是布隆過濾器。布隆過濾器非常緊湊，但您必須爲偶爾的查找誤報做好準備。你可以在維基百科找到更多關於它們的信息。

第三個選項是使用一個simle排序的數組。查找是以n爲整數的數字記錄。它可能夠快。

來源

2012-01-19 18:43:18 Joni

最痛苦的表演權打到現在正在創造他們...

正如您所觀察到的明顯，HashSet<T>沒有一個構造函數一個capacity參數初始化其能力。

一個招，我相信會的工作如下：

int capacity = ... some appropriate number; 
int[] items = new int[capacity]; 
HashSet<int> hashSet = new HashSet<int>(items); 
hashSet.Clear(); 
...

尋找與反射器實施，這將容量初始化爲items數組的大小，忽略了這個數組包含重複的事實。但是，它實際上只會添加一個值（零），所以我認爲初始化和清除應該是相當有效的。

我還沒有測試過這個，所以你必須對它進行基準測試。並願意承擔依賴於無證內部實施細節的風險。

知道爲什麼微軟沒有像其他集合類型那樣爲構造函數提供capacity參數會很有趣。

來源

2012-01-19 19:28:44 Joe

剛剛測試過它。使用這種方法創建它們需要比從空的'HashSet '開始時長大約50％。 –

高效存儲一組數字

回答

相關問題