このデータ構造にはフレンドリーな名前がありますか？

Question

Pythonでの機械学習アルゴリズムの機能セレクタで作業しながら、私は、次のコードとデータ構造を生成した：タプル{2}のリストであり、groupsであり、results、

# 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) 

私の入力はセットのリスト私のコードは必ずしも効率的ではないことに注意してください。説明の目的でのみ提供されています。

マイデータ構造、groupsは、次のプロパティがあります。各(jthName,kthName)に対して

• ：

  • (jthName,kthName)のどちらの要素がどの含まれているセットで発見された場合は、私たちのリストの中set((jthName,kthName))を作成セット。
  • (jthName,kthName)の1つが含まれているセットの1つだけが見つかった場合は、その未知の要素をそのセットに統合します。
  • (jthName,kthName)の各要素が異なるセットにある場合、2つの参照セットを1つのセットに統合します。

• ループ不変：jthNameとkthNameは、複数のセットに含まれていることはできません。

このデータ構造のための私の正当化は、各固有の要素名はノードであり、それぞれ固有のペアはエッジで接続nodegraphsの未知の組の平坦分解を作成することです。私の理論的根拠は、私のグラフは不完全であり、私はだけを選択するためにこのビューを必要とします。regressively determineグラフの接続性と方向性のアルゴリズムにフィードするために各グラフの既知のメンバーが表示されます（つまり、DAGsの完全なセットデータによって）。しかし、私は逃げる。

変数groupsで表されるデータ構造のフレンドリ名はありますか？そうである場合、またはそうでない場合には、この分解を実行するためのより時間的または空間的に効率的な手段がありますか？

Answer 1

あなたが探しているものは、Disjoint-set data structureと呼ばれるものだと思います。

これは、パス圧縮を使用して分離セットデータ構造を実装すると、償却されたnlog * n（実際にはそれよりも少ない）時間にn回のルックアップを実行できるため、Kruskalを実行するときによく使用されます。

実装するのはかなり妥当で、私はwikiページの擬似コードがPythonにうまく対応していると思います。さらに援助が必要な場合は、this SO question might help。

あなたは素集合データ構造を使用した場合、あなたのコードは次のようになります。

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

    union(jName, kName)