用於維護一個<5k的整數列表的最高內存有效的數據結構是什麼？

Question

我有很多排序整數的列表，每個列表都不到3600個條目。我想盡可能地將它們保存在內存中，所以我正在尋找一種節省空間的數據結構。

最常見的操作是插入，成員資格測試和範圍查詢。

整數將大部分在1到100億範圍內，儘管理論上可能存在一些整數將會低得多的角落情況。

我一直在尋找跳躍列表，這是相當不錯的，但我覺得那裏可能會有更高效的結構。

Answer 1

這實際上取決於訪問模式和相對於修改的查找比例。當查找比修改更常見（在你的情況下，顯然插入），這是很常見的，你實際上可以逃避排序的數組，這將給你最佳的內存效率。

如果插入實際上更常見，排序後的數組可能不會這樣做，您將不得不求助於更復雜的數據結構。 B樹聽起來像是一個可能的候選者，因爲它們將許多節點放在一起，因此不會像AVL，跳過列表或紅黑樹那樣受到連接開銷的影響。

我認爲調查基數樹會特別有趣，特別是如果在列表中碰巧有很多連續的整數，因爲這樣的範圍會被基數樹「壓縮」。

值得注意的是，布隆過濾器可以幫助進一步優化您的會員查詢。從某種意義上說，它們是用於成員查詢的空間效率最高的數據結構，但是它只是概率性的，您只能將它們與其他確定性數據結構結合使用，除非您被允許返回不正確答案:-)。