我正在开发一个为用户提供数十万个标志的系统。这些标志在编号上都是连续的,从 0 到 X,无论 X 最终是什么。X 预计会随着时间的推移而增长。我们也期望有很多很多的用户。
我们主要关心的是:
- 能够快速测试用户是否设置了任何给定的标志。
- 能够快速设置标志。
- 能够将数据存储优化到尽可能小的尺寸。
使用 10k 标志,如果我们使用位向量,我们在内存中查看每个用户大约 1k 的数据。这可能太多了。更糟糕的是,这是在 Javascript 中,存储在序列化为 JSON 的文档数据库中,这意味着我们有多个存储选项,但没有一个是我特别喜欢的。
- 将标志存储为 Uint32Array 对象的 JSON 输出。看起来像:
"{"0":10,"1":4294967295}"
。不幸的是,当标志接近填充状态时,每 4 个字节平均需要 17 个字节,这是内存的 4 倍以上,并且在序列化时会导致大约 5k 的内存。这并不理想。 - 执行我们自己的 JSON 序列化,使用 base64 以避免数字作为字符串方法的臃肿大小。不幸的是,这为 JSON 输入/输出阶段增加了一个额外的处理步骤,这使事情变得复杂,因为现在我们必须在这个过程中修改我们的数据,这会减慢一切。
所以...暂时搁置位向量的想法。我想知道是否有更好的方法。我考虑使用“范围数组”,例如:
[{"m":0,"x":100},{"m":102},{"m":108,"x":204}]
我们可以对这个系统中的数据做一些假设,这就是我采用这种方法的原因:
- 标志永远不会取消设置。一旦设置,它将保持设置。
- 标志通常是聚集在一起的。如果设置了标志 X,则很有可能同时设置 X-1 和 X+1。
- 标志通常会设置为增加的索引值。如果设置了标志 X,则 X-1 比 X+1 更可能被设置,并且 X+1 很可能在不久之后被设置。
因此,由于这些条件,我认为存储范围对象数组可能是最佳解决方案。这样,随着时间的推移,用户的标志最终会浓缩成一个大范围的条目。最理想的情况当然是:
[{"m":0,"x":10000}]
当然,最坏的情况是,如果他们以某种方式设法发现自己处于设置其他所有标志的状态。
[{"m":0},{"m":2},{"m":4},{"m":6},{"m":8},{"m":10}...{"m":10000}]
那会很糟糕。我认为比位向量解决方案差得多。但我们非常有信心这不会发生。
因此,关于快速决定是否设置标志的能力;这只是一个 O(logn) 二进制搜索(因为数组将被排序);只需找到最接近您的号码的范围对象,检查您的号码是否在该范围内,然后返回。
插入更加棘手。它仍然是二进制搜索,但现在我们正在修改数组。
- 一个相邻的兄弟插入:最佳方案。我们找到一个范围,其中最小值或最大值与我们插入的数字相差一个,然后简单地减少或增加当前范围的值。O(1)
- 没有相邻的兄弟节点插入:只需插入一个具有最小值集的新节点。O(n),因为我们将在数组中向下移动它之后的所有内容。
- 两个相邻兄弟插入:将最大值更改为右侧兄弟范围的最大值,从数组中删除右侧兄弟范围并将其后的所有内容向左移动。上)。
所以案例 2+3 让我想知道我是否不应该为此尝试使用某种平衡的二叉搜索树。例如,红黑树。
这值得麻烦吗?这是我想太多了吗?