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

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

我看到有两点可以改进。首先，由于您对看到的标签使用 list，因此 l not in seen 和 seen.index(l) 操作需要 O(n) 时间。您可以使用 dict.

而不是 list

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

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 2

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

我们将使用字典 seen 而不是列表，因为 list.index 的开销为 O(n)
seen 会将项目映射到它们的新名称，这只是字典的当前长度 - 但 len 的 O(1) 成本较低。 x in some_dict 也是 O(1)，与 x in some_list.
最后，我们会将您的函数重写为生成器，并使用 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))

edit：我刚刚意识到只使用 izip 而不是 izip_longest 并预先检查长度会更好。如果确信你传递给compare_labels的两个标签总是一样长的，你可以把这个check out掉。

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 集中查找值的速度（这不会改变渐近速度，但可能会带来很大的收益在实践中）。

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

Efficiently comparing lists of arbitrarily-assigned labels

python

algorithm

list

comparison