这个数据结构有一个友好的名称吗？

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

我认为你所寻找的东西叫做一个不相交的数据结构.

它经常在做Kruskal时使用,因为如果你用路径压缩实现不相交的数据结构,它允许你在分摊的nlog*n(实际上小于那个)时间内进行n次查找.

这是非常合理的实现,我认为维基页面伪代码非常适合python.如果您需要更多帮助,这个SO问题可能有所帮助.

如果您使用了不相交的数据结构,那么您的代码将如下所示:

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

   union(jName, kName)