我有许多排序整数列表，每个列表都少于 3600 个项目。我想尽可能地将它们保存在内存中，所以我正在寻找一种节省空间的数据结构。
最常见的操作是插入、成员资格测试和范围查询。
整数将主要在 1 到 100 亿范围内，尽管理论上可能存在一些整数会低得多的极端情况。
我一直在看skiplists，这很不错，但我觉得那里可能有更有效的结构。
问问题
1923 次
1 回答
2
这实际上取决于访问模式和相对于修改的查找比例。当查找比修改（在您的情况下，显然是插入）更常见时，这很常见，您实际上可以摆脱排序数组，这将为您提供最佳的内存效率。
如果插入实际上更常见，排序数组可能不会这样做，您将不得不求助于更复杂的数据结构。B 树听起来像是一个可能的候选者，因为它们将许多节点打包在一起，因此不会像 AVL、跳过列表或红黑树那样受到链接开销的影响。
我认为研究基数树会同样有趣，特别是如果您的列表中碰巧有很多连续的整数，因为这样的范围会被基数树“压缩”。
值得注意的是，布隆过滤器可以帮助进一步优化您的会员查询。在某种程度上，它们是成员查询中最节省空间的数据结构，但由于是概率性的，您只能将它们与其他一些确定性数据结构结合使用，除非您当然可以返回不正确的答案:-)。
于 2013-08-16T12:18:44.023 回答