2

假设我们有m 个有序集合，我们想要找到它们的交集。

我们应该为有序集使用哪种数据结构，哪种算法最有效？

同一个问题： N 路合并算法

看来文献量很大。因此，一个更好的问题是：有哪些好的实现？

4

2 回答 2

1

您可以创建链接到父节点的二叉树并实现经典的交集/联合算法：

  1. 设置iterA为树的最左边（最小）节点（即从最左边的分支下降到叶子）。
  2. 设置iterB为有序集合的第一个（最小）节点（如果它是用有序数组实现的，或者如果是树，则设置为最左边的节点）。
  3. 通过比较iterAand指向的项目进行分支iterB
    • 如果低于：联合和推进的产量项目iterA
    • 如果等于：yield并集项和交集项并推进两者iterA和itemB
    • 如果更大：联合和推进的产量项目iterB
  4. 重复直到其中一个迭代器无法前进
  5. 其他迭代器可访问的其余项目作为联合项目产出

二叉树迭代器的推进：

  • 如果当前节点有右孩子下降到它并尽可能下降到它最左边的孩子。输出那个项目。
  • 如果节点有父节点上升，并在我们从右孩子上升时重复。输出那个项目。
  • 否则：树的所有项目都已经产生（收集结束）。

更新： 如果您知道您的有序集（经过iterB）比树小得多，您可以使用更复杂的算法进行交集：

  1. 最初设置iterB为有序集的开头（较低的值）。
  2. 设置iterA为 value 的最小上界的节点iterB。
  3. 通过比较iterAand指向的项目进行分支iterB
    • 如果等于：产生交集项。
  4. 前进itemB到下一个值。
  5. 从 current 开始前进iterA到 value 的最小上限。itemBitemA
  6. 重复直到itemB通过有序集合的所有项目。

从特定节点前进到最小上限的位置是：

  • 如果当前节点的值小于目标
    • 通过遍历每个节点的右孩子找到右孩子的上限
    • 如果该分支的最右边节点甚至低于目标：从右子节点移动并从该节点重新启动时上升到父节点。
    • 其他来自我们找到上限的节点
    • 找到小于目标的第一个最左边的孩子值
      • 如果未找到：该分支的最左侧叶子是最小上限
      • 否则从该节点重新启动（更准确地说是使用遍历最左边和最右边节点缩小边界的子算法）。

搜索边界的主要思想是缩小上限和最小边界（“-”是忽略节点，“...”是新的搜索范围）：

for B < X < A
    U
   / \-
  L
-/ \...

for A < X < B
  L
-/ \
    U
.../ \-
于 2012-11-27T14:42:35.410 回答
0

这只是一个草图：请帮助我改进它。

此解决方案将基于使用二分搜索将搜索限制为每个集合的 n/2^i 个元素，并且我将使用有效的数据结构来记住下一个数字的这些比较。

首先要注意的是平衡二叉树擅长执行二叉搜索，只有当搜索的间隔与（子）树的间隔紧密匹配时。

接受二分查找的另外2 个结构是数组和跳过列表。该数组对于插入和删除效率低下，因此跳过列表似乎是最佳选择。

我们将需要m 个大小为 64 的数组，其中将包含每个数组的每个集合的元素，这些元素在二进制搜索中进行比较，按照比较的执行顺序插入。

我们还需要一个双链表，其中将插入二进制搜索中使用的所有集合中的所有元素。 在此处使用跳过列表可以最大限度地减少所需的比较次数。

基本思路是这样的。

  1. 我们使用二分搜索搜索每个集合中的最小元素。
  2. 在每个二分查找步骤中，我们将新元素添加到集合的数组和双链表中。
  3. 要么有一个共同的最小元素，要么没有。
  4. 我们删除双链表中的最小元素。新搜索将从集合的二分搜索数组中的前一个元素开始，并将使用比以前一半的距离。我们使用数组中先前的二分搜索元素来将新搜索限制在已知的最小区间内。
  5. 继续1。
于 2012-11-27T23:36:08.907 回答