java - 对等价类的元素进行分组的数据结构

Question

我必须实现一个数据结构来对等价类的元素进行分组。

API:

interface Grouper<T>{
  void same(T l, T r);
  Set<EquivalenceClass<T>> equivalenceClasses();
}

interface EquivalenceClass<T>{
    Set<T> members();
}

例如，分组行为如下:

Grouper g;
g.same(a, b);
g.equivalenceClasses() -> [[a,b]]

g.same(b, a);
g.equivalenceClasses() -> [[a,b]]

g.same(b, c);
g.equivalenceClasses() -> [[a,b,c]]

g.same(d, e);
g.equivalenceClasses() -> [[a,b,c], [d,e]]

g.same(c, d);
g.equivalenceClasses() -> [[a,b,c,d]]

我正在寻找一个最多可处理约 1000 万个条目的实现。应该对其进行优化以填充它并获得一次等价类。

Answer 1

看看Union-Find .并集(“相同”)可以在 O(log N) 中轻松完成，并且可以通过一些优化在 O(1) 中有效地完成。 “equivalenceClasses”是 O(N)，这是无论如何访问所有内容的成本。