0

我正在开发一个为用户提供数十万个标志的系统。这些标志在编号上都是连续的，从 0 到 X，无论 X 最终是什么。X 预计会随着时间的推移而增长。我们也期望有很多很多的用户。

我们主要关心的是：

  1. 能够快速测试用户是否设置了任何给定的标志。
  2. 能够快速设置标志。
  3. 能够将数据存储优化到尽可能小的尺寸。

使用 10k 标志，如果我们使用位向量，我们在内存中查看每个用户大约 1k 的数据。这可能太多了。更糟糕的是，这是在 Javascript 中，存储在序列化为 JSON 的文档数据库中，这意味着我们有多个存储选项，但没有一个是我特别喜欢的。

  1. 将标志存储为 Uint32Array 对象的 JSON 输出。看起来像："{"0":10,"1":4294967295}"。不幸的是，当标志接近填充状态时，每 4 个字节平均需要 17 个字节，这是内存的 4 倍以上，并且在序列化时会导致大约 5k 的内存。这并不理想。
  2. 执行我们自己的 JSON 序列化，使用 base64 以避免数字作为字符串方法的臃肿大小。不幸的是，这为 JSON 输入/输出阶段增加了一个额外的处理步骤，这使事情变得复杂，因为现在我们必须在这个过程中修改我们的数据，这会减慢一切。

所以...暂时搁置位向量的想法。我想知道是否有更好的方法。我考虑使用“范围数组”，例如：

[{"m":0,"x":100},{"m":102},{"m":108,"x":204}]

我们可以对这个系统中的数据做一些假设，这就是我采用这种方法的原因：

  1. 标志永远不会取消设置。一旦设置，它将保持设置。
  2. 标志通常是聚集在一起的。如果设置了标志 X，则很有可能同时设置 X-1 和 X+1。
  3. 标志通常会设置为增加的索引值。如果设置了标志 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) 二进制搜索（因为数组将被排序）；只需找到最接近您的号码的范围对象，检查您的号码是否在该范围内，然后返回。

插入更加棘手。它仍然是二进制搜索，但现在我们正在修改数组。

  1. 一个相邻的兄弟插入：最佳方案。我们找到一个范围，其中最小值或最大值与我们插入的数字相差一个，然后简单地减少或增加当前范围的值。O(1)
  2. 没有相邻的兄弟节点插入：只需插入一个具有最小值集的新节点。O(n)，因为我们将在数组中向下移动它之后的所有内容。
  3. 两个相邻兄弟插入：将最大值更改为右侧兄弟范围的最大值，从数组中删除右侧兄弟范围并将其后的所有内容向左移动。上）。

所以案例 2+3 让我想知道我是否不应该为此尝试使用某种平衡的二叉搜索树。例如，红黑树。

这值得麻烦吗？这是我想太多了吗？

4

0 回答 0