有效地比较任意分配的标签列表

Question

我有两个项目标签列表（来自集群），它们表示相同的项目，但分配了不同的（任意）标签。一个例子：

labels1 = [1, 1, 2, 2, 3, 3, 3, 1, 1]
labels2 = [0, 0, 1, 1, 4, 4, 4, 0, 0]

每个列表中的结构都是相同的，因此找到的簇除了标签之外是相同的。通过按标签首次出现的顺序重命名标签，可以将它们转换为以下列表。

renamed = [0, 0, 1, 1, 2, 2, 2, 0, 0]

我正在寻找一种检查此属性的方法，因此问题归结为在下面的relabel函数中找到一种有效的重新标记方法。

labels1 = [1, 1, 2, 2, 3, 3, 3, 1, 1]
labels2 = [0, 0, 1, 1, 4, 4, 4, 0, 0]
def relabel(labels):
    """Rename list of labels to the order they first appear in the list.
    """
    seen = []
    renamed = []
    for l in labels:
        if l not in seen:
            seen.append(l)
        renamed.append(seen.index(l))
    return renamed
assert relabel(labels1) == relabel(labels2)

我所做的工作，我只是想知道是否有一种我所缺少的更有效的方法来进行比较。例如，如果列表很大，使用生成器表达式会有帮助吗？

Answer 1

您的原始函数没有返回结果，我很惊讶您说它有效。我们可以在这里优化一些东西：

• 我们将使用字典seen而不是列表，因为list.index对于O（n）是昂贵的
• seen会将项目映射到它们的新名称，这只是字典的当前长度，但len使用O（1）的成本更低。此外，与x in some_list的O（n）相比，x in some_dict也是O（1）
• 最后，我们将把您的函数重写为生成器，并用all和izip检查生成器表达式中两个relabel的相等性。CCD_ 10将在第一次失配时停止

这是代码：

from itertools import izip
def relabel(labels):
    seen = {}
    for l in labels:
        if l not in seen:
            seen[l] = len(seen)
        yield seen[l]
def compare_labels(l1,l2):
    if len(l1) != len(l2):
        return False
    l1 = relabel(l1)
    l2 = relabel(l2)
    return all(x==y for x,y in izip(l1,l2))

edit：我刚刚意识到，只使用izip而不是izip_longest，并提前检查长度更好。如果确保传递给compare_labels的两个标签始终具有相同的长度，则可以不进行此检查。

Answer 2

我看到了两件可以改进的事情。首先，由于所看到的标签使用list，因此l not in seen和seen.index(l)操作需要O(n)时间。您可以使用dict而不是list。

然后，正如您自己建议的那样，您可以返回一个带有yield关键字的生成器，而不是返回一个列表。

def relabel(labels):
    """
    Rename list of labels to the order they first appear in the list.
    """
    seen = dict()
    for l in labels:
        if l not in seen:
            seen[l] = len(seen)
        yield seen[l]
assert all(x == y for x, y in zip(relabel(labels1), relabel(labels2)))

Answer 3

除上述答案外，您不需要重新标记两次，也不需要浏览整个列表（您可以在第一次不匹配时停止）。如果目标是验证这个属性，那么：

 def verify(labels1, labels2):
     seen = {}
     used = {}
     for (x, y) in izip_longest(labels1, labels2):
         if x == None or y == None: return False
         if seen.has_key(x):
             if seen[x] != y: return False
         else:
             if used.has_key(y): return False
             seen[x] = y
             used[y] = True
     return True

该算法在O（min（len（labels1），len（labels2））中工作，并且它使用O（num（labels1）+num（labels2））内存。

如果标签集是有限的（最好是小的），那么您可以通过使用位运算来加快在used集中查找值的速度（这不会改变渐进速度，但在实践中可能会导致大的增益）。