1

我有这种情况，我有N个时间线，每个时间线都包含块。这些块包含具有特定索引的令牌，并且知道它们的最大和最小令牌索引。还有一个索引将块的第一个索引映射到（时间轴，块）对。这是一个例子：

Timeline 1: [1 2 5 8 9 11] [14 17 18 21] [22 23 25 26] ...
Timeline 2: [3 4 6 7 10 12] [13 15 16 19 20 24] [27 28 34 45] ...

Index:
  1 -> timeline 1, block 1
  3 -> timeline 2, block 1
  13 -> timeline 2, block 2
  14 -> timeline 1, block 2
  22 -> timeline 1, block 3
  27 -> timeline 2, block 3

如您所见，没有丢失令牌（没有间隙）。

这些数据结构是我最初拥有的。优化特定令牌索引查询的最佳替代数据结构是什么？假设我要检索令牌 19。现在我要做的是：在索引中进行二分搜索以找到每个时间线的好块，然后在每个块内进行完整搜索。使用令牌 19，二分搜索将产生可以包含 19 的块 (1, 2) 和 (2, 2)，然后进行完整的线性搜索以找到令牌 19（这里不可能在块内进行二分搜索，因为令牌有各种大小，尚未包含在任何数据结构中）。

谢谢！

编辑：我正在考虑使用包含所有时间线间隔的间隔树。问题是查询仍然会产生许多间隔。另外，与二进制搜索相比，它并没有优化太多。

4

3 回答 3

0

也许您可以使用稀疏空间填充曲线？当您拥有索引时，它是一个减少维度的函数。空间填充曲线是相同的，但它也在索引中添加了空间信息。空间填充曲线或空间索引的另一种数据结构是四叉树。因此，您可以使用四叉树或 kd-tree 进行搜索。

于 2012-05-19T03:36:58.837 回答
0

我认为最简单的方法（如果它不占用大量内存空间）是创建一个 blob 值数组，其中 index 是您的查询令牌（19 - 在您的示例中），该值是对应于的 blob 部分它。阵列应该很好，因为你没有差距。构造这个数组是 O(n) 并且在那里搜索是 O(1)。但这只有在查询量比较大的情况下才会带来一些好处，因为现有的结构也已经很好地优化了。（实际上应该在这里进行测试，哪种方式更快。）

构造数组：

array = []
foreach ( timeline in timelines ){
  foreach ( block in timeline){
    foreach( token in block ){
      array[token.index] = token.value
    }
  }    
}

如果这太昂贵，请尝试仅保存令牌的时间线编号。这样，当查询到来时，您就不必搜索每个时间线。您所要做的就是获取时间线，二进制搜索一个块，并在一个块内进行简单的前向搜索。

于 2012-05-18T21:12:35.940 回答
0

您可以拥有一个包含t个指向对象的指针的数组A，这些对象包含指向令牌、其时间线和块的指针。如果您可以使用您的语言喜欢的任何机制将引用保存在数组中。如果您不能在块内进行二进制搜索，我不确定您能做什么。

于 2012-05-18T20:35:52.100 回答