Есть ли понятное имя для этой структуры данных?

Question

Работая над селектором функций для алгоритма машинного обучения в Python, я создал структуру данных со следующим кодом:

# Perform set partitioning on the results
groups = []
for t in results:
    (jthName,kthName) = t
    jthGroup = -1
    kthGroup = -1

    # Just a simple list of hashes with online merging
    for idx,group in enumerate(groups):
        if jthName in group:
            jthGroup = idx
        if kthName in group:
            kthGroup = idx
    if jthGroup == kthGroup:
        if jthGroup == -1: # Implicit: "and kthGroup == -1"
            groups.append(set((jthName,kthName)))
    elif jthGroup != kthGroup:
        if kthGroup == -1:
            # Merge kthName into jthGroup
            groups[jthGroup].add(kthName)
        elif jthGroup == -1:
            # Merge jthName into kthGroup (redundant if naturally-ordered)
            groups[kthGroup].add(jthName)
        else:
            # Merge jthGroup and kthGroup, since we have a connecting pair
            merged = set()
            merged.update(groups[jthGroup])
            merged.update(groups[kthGroup])
            groups.remove(groups[jthGroup])
            groups.remove(groups[kthGroup])
            groups.append(merged)

Где мой ввод, results, это список кортежей {2}, а groups это список множеств. Обратите внимание, что мой код не обязательно эффективен здесь; предоставляется только в иллюстративных целях.

Моя структура данных, groups, имеет следующие свойства:

• Для каждого (jthName,kthName):

  • Если ни один из элементов (jthName,kthName) не найден ни в одном из содержащихся наборов, создайте set((jthName,kthName)) в нашем списке наборов.
  • Если ровно один из (jthName,kthName) найден в одном содержанном наборе, объедините найденный элемент в этом наборе.
  • Если каждый элемент (jthName,kthName) найден в другом наборе, объедините два указанных набора в один набор.

• Инвариант цикла: jthName и kthName не могут содержаться более чем в одном наборе.

Мое оправдание этой структуры данных состоит в том, чтобы создать плоскую декомпозицию неизвестного набора связанных графов узлов, где каждое уникальное имя элемента является узлом, а каждая уникальная пара - ребром. Мое обоснование состоит в том, что мои графы неполные, и я требую, чтобы это представление выбрало только известных членов каждого графа для подачи в алгоритм, который будет регрессивно определять связность графа и направленность ребра (то есть полный набор DAG , выраженный данными). Но я отвлекся.

Есть ли понятное имя для структуры данных, представленной переменной groups? Если да или нет, есть ли более эффективные с точки зрения времени или пространства средства для выполнения этой декомпозиции?

Answer 1

Я думаю, что то, что вы ищете, называется структурой данных Disjoint-set .

Он часто используется при выполнении Крускала, потому что он позволяет вам делать n поисков в амортизированном nlog * n (фактически меньше) времени, если вы реализуете структуру данных с несвязным множеством со сжатием пути.

Это довольно разумно реализовать, и я думаю, что псевдокод вики-страницы прекрасно подходит для python. Если вам нужна дополнительная помощь, этот вопрос SO может помочь .

Если бы вы использовали структуру данных с несвязным множеством, ваш код выглядел бы так:

for t in results:
   (jName, kName) = t

   union(jName, kName)