在对列表中查找唯一对

Question

我有一个(大)整数列表列表,例如,

a = [
    [1, 2],
    [3, 6],
    [2, 1],
    [3, 5],
    [3, 6]
    ]

大多数对将出现两次,其中整数的顺序无关紧要(即[1, 2]相当于[2, 1]).我现在想找到只出现一次的对,并得到一个布尔列表来表示.对于上面的例子,

b = [False, False, False, True, False]

由于a通常很大,我想避免显式循环.frozenset可能会建议映射到s,但我不确定这是否过度.

Answer 1

ctr = Counter(frozenset(x) for x in a)
b = [ctr[frozenset(x)] == 1 for x in a]

我们可以使用Counter来获取每个列表的计数(将列表转到冻结集以忽略顺序),然​​后对每个列表检查它是否只出现一次.

Answer 2

这是NumPy的解决方案,比建议的frozenset解决方案快10倍:

a = numpy.array(a)
a.sort(axis=1)
b = numpy.ascontiguousarray(a).view(
        numpy.dtype((numpy.void, a.dtype.itemsize * a.shape[1]))
        )
_, inv, ct = numpy.unique(b, return_inverse=True, return_counts=True)
print(ct[inv] == 1)

• 排序是快速,并确保边缘[i, j],[j, i]原始数组中识别彼此.比frozensets或tuples 快得多.

• 排名统一受到/sf/answers/1188145731/的启发.

不同阵列尺寸的速度比较:

情节是用.创建的

from collections import Counter
import numpy
import perfplot


def fs(a):
    ctr = Counter(frozenset(x) for x in a)
    b = [ctr[frozenset(x)] == 1 for x in a]
    return b


def with_numpy(a):
    a = numpy.array(a)
    a.sort(axis=1)
    b = numpy.ascontiguousarray(a).view(
            numpy.dtype((numpy.void, a.dtype.itemsize * a.shape[1]))
            )
    _, inv, ct = numpy.unique(b, return_inverse=True, return_counts=True)
    res = ct[inv] == 1
    return res


perfplot.show(
        setup=lambda n: numpy.random.randint(0, 10, size=(n, 2)),
        kernels=[fs, with_numpy],
        labels=['frozenset', 'numpy'],
        n_range=[2**k for k in range(12)],
        xlabel='len(a)',
        logx=True,
        logy=True,
        )