Структура данных для группировки элементов классов эквивалентности

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]]

Я ищу реализацию, которая работает до ~ 10 миллионов записей.Он должен быть оптимизирован, чтобы заполнить его и получить классы эквивалентности один раз.

Answer 1

Взгляните на Union-Find .Объединение («то же самое») может быть выполнено тривиально в O(log N), и может быть эффективно выполнено O(1) с некоторыми оптимизациями.«Эквивалентные классы» равны O(N), что в любом случае означает стоимость посещения всего.

Answer 2

Если вы собираетесь запрашивать классы эквивалентностей только один раз, лучшее решение - построить неориентированный граф на элементах.Каждая эквивалентность является неориентированным ребром между двумя элементами, а классы эквивалентности соответствуют связанным компонентам.Если вы все сделаете правильно, сложность времени и пространства будет линейной.

В качестве альтернативы вы можете использовать структуру данных Union-Find, которая даст вам почти линейную сложность времени.Это также можно считать более простым, потому что все сложности заключены в структуру данных.Причина, по которой Union-Find не является линейной, сводится к поддержке эффективных запросов во время роста классов.

Answer 3

Union-find - лучшая структура данных для вашей задачи, если вы заботитесь только об общем времени выполнения (некоторые операции могут быть медленными, но общая стоимость всех операций гарантированно будет почти линейной).Перечисление членов каждого набора обычно не поддерживается в простой версии union-find в учебниках.Как следует из названия, union-find обычно поддерживает только union (т. Е. same) и find, который возвращает идентификатор, который гарантированно совпадает с идентификатором, возвращаемым вызовом для поиска элемента в том же наборе.Если вам нужно перечислить элементы каждого набора, вам, возможно, придется реализовать его самостоятельно, чтобы вы могли добавить, например, дочерние указатели, чтобы вы могли обходить каждое дерево, представляющее набор.

Если вы реализуете этосамостоятельно, вам не нужно реализовывать полную структуру поиска по объединению, чтобы получить амортизированное время O (lg n) на операцию.По сути, в этой «легкой» версии union-find каждый набор будет представлять собой односвязный список с дополнительным указателем внутри каждого узла, который указывает на узел идентификатора набора, который можно использовать для проверки того, принадлежат ли два узла одному и тому же списку.Когда метод same выполняется, вы можете просто добавить меньший список к большему и обновить идентификаторы набора для элементов меньшего списка.Общая стоимость составляет не более O (LG N) на элемент, потому что элемент может быть членом меньшего списка, участвующего в операции same не более O (LG N) раз.