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

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_dict 的复杂度为 O(1)，而 x in some_list 的复杂度为 O(n)。
• 最后，我们会将您的函数重写为生成器，并使用 all 和 izip 检查生成器表达式中两个重新标记的相等性。 all 将在第一次不匹配时停止。

代码如下:

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

编辑:我刚刚意识到只使用 izip 而不是 izip_longest 并预先检查长度会更好。如果确定您传递给 compare_labels 的两个标签的长度始终相同，则可以将此检查留空。