algorithm - 用于维护已排序的 <5k 整数列表的内存效率最高的数据结构是什么？

Question

我有很多排序整数列表，每个列表都少于 3600 个项目。我想尽可能多地将它们保存在内存中，因此我正在寻找一种节省空间的数据结构。

最常见的操作是插入、成员资格测试和范围查询。

整数将主要在 1 到 100 亿的范围内，尽管理论上可能存在一些整数会低得多的极端情况。

我一直在研究跳过列表，它非常好，但我觉得那里可能有更高效的结构。

Answer 1

这实际上取决于访问模式和查找相对于修改的比例。当查找比修改(在您的情况下，显然是插入)更常见时，这很常见，您实际上可以摆脱排序数组，这将为您提供最佳的内存效率。

如果插入实际上更常见，那么排序数组可能就不行了，您将不得不求助于更复杂的数据结构。 B 树听起来像是一个可能的候选者，因为它们将许多节点打包在一起，因此不会像 AVL、跳过列表或红黑树那样受到链接开销的影响。

我认为研究基数树同样会很有趣，特别是如果您的列表中恰好有很多连续的整数，因为这样的范围会被基数树“压缩”。

值得注意的是，布隆过滤器可以帮助进一步优化您的成员(member)查询。在某种程度上，它们是成员资格查询最节省空间的数据结构，但由于是概率性的，您只能将它们与其他一些确定性数据结构结合使用，除非您当然可以返回不正确的答案 :-)。