找到要删除的项目

Question

我有一个数据池(X ₁ ..X _N),我想要找到相同值的组.比较非常昂贵,我无法将所有数据保存在内存中.

我需要的结果是,例如:

X ₁等于X ₃,X ₆
X ₂是唯一的
X ₄等于X ₅

(行的顺序或行内的顺序无关紧要).

如何通过成对比较实现这一点？

---

这是我到目前为止所拥有的:

比较所有对(X _i,X _k)和i <k,并利用传递性:如果我已经找到X ₁ == X ₃和X ₁ == X ₆,我不需要比较X ₃和X ₆.

所以我可以使用以下数据结构:

  map: index --> group
  multimap: group --> indices

其中组被任意分配(例如输出中的"行号").

对于一对(X _i,X _k),其中i <k:

• 如果i和k已经分配了一个组,请跳过

• 如果他们比较平等:

  • 如果我已经分配了一个组,则将k放入该组
  • 否则,为i创建一个新组并将k放入其中

• 如果他们不平等:

  • 如果我还没有分配组,请为i分配一个新组
  • 同样的k

如果我对项目的顺序很谨慎,这应该有用,但我想知道这是否是解决这个问题的最佳/最不令人惊讶的方法,因为这个问题似乎有点普遍.

---

背景/更多信息:目的是重复删除项目的存储.他们已经有一个哈希,如果发生碰撞,我们希望保证完整的比较.所讨论数据的大小具有非常尖锐的长尾分布.

迭代算法(找到任意两个重复项,共享它们,重复直到没有重复项)可能会更容易,但我们需要非修改诊断.代码库是C++,适用于STL/boost容器或算法的东西会很好.

[编辑]关于哈希:为了这个问题的目的,请假设一个无法替换的弱哈希函数.

这需要对现有数据进行一次性重复数据删除,并且需要处理散列冲突.最初的选择是"快速哈希,并在碰撞时进行比较",所选择的哈希结果有点弱,但改变它会破坏向后兼容性.即便如此,我还是会用一个简单的陈述睡得更好:如果发生碰撞,你就不会得到错误的数据.而不是关于狼攻击的博客.

Answer 1

这是另一种可能更简单的利用传递性的数据结构。列出您需要进行的比较。例如，如果有 4 个项目，则为 [ (1,2), (1,3), (1,4), (2,3), (2,4), (3,4) ] 。还有一个数组用于您已经完成的比较。在每次比较之前，检查之前是否已完成该比较，并且每次找到匹配项时，请遍历队列并将匹配项索引替换为其较低的索引等效值。

例如，假设我们弹出(1,2)，比较，它们不相等，将(1,2)压入数组already_visited并继续。接下来，弹出(1,3)，发现它们相等。此时，遍历队列并将所有 3 替换为 1。队列将为 [(1,4)、(2,1)、(2,4)、(1,4)]，依此类推。当我们到达(2,1)时，它已经被访问过，所以我们跳过它，与(1,4)相同。

但我确实同意前面的答案。由于比较的计算成本很高，因此您可能希望首先计算一个快速、可靠的哈希表，然后才将此方法应用于冲突。