如何存儲一組數字

-1

我有一組1,000,000個唯一的數字。數字介於0到50,000,000之間。考慮一下，這些數字是隨機的。我需要一個可以容納他們的數據結構。數據結構應該儘可能少地需要內存。應該可以快速找到數字是否在沒有錯誤的集合中。如何存儲一組數字

我發現了一個布隆過濾器的解決方案。是的，布隆過濾器有誤報的可能性，但由於「正好」有50,000,000個可能的數字，我可以找到所有錯誤並將它們保存在std :: set中。通過這種方法，我可以將所有數字存儲在2.3MB的內存中。

你能找到更好的方法嗎？

2014-02-07 smrt28

一個普通的位矢量在技術上需要更多的空間，但它仍然是一個微薄的6 MiB，並且所有操作都快速點亮，甚至可能比bloom濾鏡更快。它也很容易實現（我敢說微不足道）。 – delnan

在我的情況下，空間更重要，然後加快速度 – smrt28

<4個額外的MiB真的很重要嗎？如果不是，我會選擇更簡單的（因此更可能是正確的）選擇。在任何情況下，'std :: set'應該有重大的每項開銷（整個節點加上每個int的分配器元數據）;一個普通的排序數組或另一個節省空間的數據結構應該節省一些空間。 – delnan

而不是範圍0到50,000,000，那麼1,024個單獨的範圍是65,536？這會給你一個64 MB的範圍。我想你可以做到763而不是1,024，這會給你50,003,968。

喜歡的東西ushort[763][];

現在你存儲百萬的16位值，而不是32位值。

行中的值被排序。因此，要確定數字是否在集合中，您將數字除以763以確定要查找哪個數組，然後在number % 65536上執行二分搜索。

數字本身的存儲量爲2,000,000字節。加上少量的陣列開銷。

這樣執行起來會更快，比布盧姆過濾器方法更小，不會出現誤報，並且更容易實現。

來源

2014-02-07 23:52:00

通常存儲這種向量的最小空間是884,002字節。它將一個整數索引（一個非常大的整數）存儲到所有可能的50,000,000,000,000,000的選項列表中。

你可以用一個簡單的快速字節編碼來接近它。給定排序的數字列表，將每個數字替換爲與最後一個數字的差異。（假設-1在第一個數字之前）。差異全部是一個或多個，所以減去一個。如果結果是254或更少，則將其編碼爲一個字節。否則，寫入255，然後跟着兩個字節，差別較大，減去255。如果它不適合，寫入三個255，然後跟隨三個字節的差異。這將幾乎總是編碼小於1,012,000字節的向量。

來源

2014-02-08 00:47:58

如何存儲一組數字

回答

相關問題