紧凑的数据结构,用于存储大量的整数值

Question

我正在开发一个需要传递大量Int32值的应用程序.这些集合应包含~1,000,000-50,000,000项目,其中每个项目都是该范围内的数据库键0-50,000,000.我希望任何给定集合中的id分布在这个范围内是有效随机的.我需要的操作很简单:

• 添加新值
• 迭代所有值.

关于这些集合的内存使用情况存在严重问题,因此我正在寻找一种能够比简单List<int>或更高效地存储id的数据结构HashSet<int>.我看过了BitArray,但这可能是浪费,取决于ID的稀疏程度.我也考虑过一点点trie,但我不确定如何计算该解决方案对于预期数据的空间效率.Bloom Filter会很棒,只要我能容忍假阴性.

我将不胜感激任何适用于此目的的数据结构的建议.我对开箱即用和定制解决方案感兴趣.

编辑:回答你的问题:

• 不,这些物品不需要分类
• 通过"传递"我的意思是在方法之间传递并序列化并通过线路发送.我显然应该提到这一点.
• 一次可以在内存中有相当数量的这些集合(~100).

Answer 1

使用BitArray.它只使用大约6MB的内存; 唯一真正的问题是迭代是Theta(N),即你必须遍历整个范围.引用的位置很好,您可以在一个操作中分配整个结构.

至于浪费空间:在最坏的情况下你会浪费6MB.

编辑:好的,你有很多套,你正在序列化.对于在磁盘上序列化,我建议6MB文件:)

对于通过线路发送,只需迭代并考虑发送范围而不是单个元素.这确实需要排序结构.

你需要很多这些套装.考虑一下你是否有600MB备用.否则,请查看:

• Bytewise尝试:O(1)插入,O(n)迭代,比按位尝试低得多的常数因子
• 一个自定义哈希表,也许是通过C++/CLI的Google sparsehash
• BST存储范围/间隔
• 超级节点BST