4

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

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 万个条目的实现。应该对其进行优化以填充它并获得一次等价类。

4

3 回答 3

5

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

于 2010-12-09T16:54:12.720 回答
1

如果您只想查询等价类一次，最好的解决方案是在元素上构建无向图。每个等价是两个项目之间的无向边，等价类对应于连通分量。如果你做得对，时间和空间复杂度都是线性的。

或者，您可以使用 Union-Find 数据结构，这将为您提供几乎线性的时间复杂度。它也可以被认为更简单，因为所有的复杂性都封装在数据结构中。Union-Find 不是线性的原因归结为在类增长时支持高效查询。

于 2010-12-09T17:54:32.630 回答
0

Union-find 是解决您的问题的最佳数据结构，只要您只关心总运行时间（某些操作可能很慢，但所有操作的总成本保证几乎是线性的）。但是，教科书中 union-find 的普通版本通常不支持枚举每个集合的成员。顾名思义，union-find 通常只支持 union (ie, same) 和 find，它返回的标识符保证与调用 find 在同一集合中的元素上返回的标识符相同。如果您需要枚举每个集合的成员，您可能必须自己实现它，以便您可以添加例如子指针，以便您可以遍历表示一个集合的每棵树。

如果您自己实现这一点，则不必实现完整的联合查找数据结构来实现每个操作的摊销 O(lg n) 时间。本质上，在这个“轻量级”版本的 union-find 中，每个集合都是一个单链表，每个节点内部都有一个额外的指针，该指针指向一个集合标识符节点，可用于测试两个节点是否属于同一个列表。执行该same方法时，您只需将较小的列表附加到较大的列表中，并更新较小列表中元素的集合标识符。每个元素的总成本最多为 O(lg n)，因为一个元素最多可以是same操作中涉及的较小列表的成员 O(lg n) 次。

于 2010-12-09T19:18:53.743 回答