4

我有以下两个列表：

lst1 = [('vr1', '635', '1'), ('vr1', '32', '1'), ('vr1', '784', '0.526'), ('vr1', '431', '1')]

lst2 = [('vr1', '635', '3'), ('vr1', '784', '2.526'), ('vr1', '431', '2')]

lst1目前，我使用以下代码确定什么是独特的。比较基于每个条目的前两列的内容。

uniq = set([i[0:2] for i in lst1]).difference([j[0:2] for j in lst2])

给予：

set([('vr1', '32')])

然后，我搜索其中的每个条目（lst1如果它包含在其中）uniq以获取完整条目。

uniq_full = [i for i in lst1 if i[0:2] in uniq]

它以我想要的方式返回条目。

[('vr1', '32', '1')]

我的问题是：有没有更快的方法来获得完整的条目？

4

4 回答 4

4

目前，您正在循环lst1并lst2一次生成uniq. 然后您lst1再次循环以生成uniq_full.

相反，您可以循环lst2一次以生成要删除的键，然后循环lst1一次以过滤掉不需要的元素：

lst1 = [('vr1', '635', '1'), ('vr1', '32', '1'), ('vr1', '784', '0.526'), ('vr1', '431', '1')]    
lst2 = [('vr1', '635', '3'), ('vr1', '784', '2.526'), ('vr1', '431', '2')]

remove_keys = set([item[:2] for item in lst2])
unique = [item for item in lst1 if item[:2] not in remove_keys]
print(unique)

产量

[('vr1', '32', '1')]

这是一个 timeit 测试（使用IPython），它表明它更快：

def orig(lst1, lst2):
    uniq = set([i[0:2] for i in lst1]).difference([j[0:2] for j in lst2])
    uniq_full = [i for i in lst1 if i[0:2] in uniq]
    return uniq_full

def alt(lst1, lst2):
    remove_keys = set([item[:2] for item in lst2])
    unique = [item for item in lst1 if item[:2] not in remove_keys]
    return unique

In [4]: %timeit orig(lst1, lst2)
100000 loops, best of 3: 2.29 µs per loop

In [5]: %timeit alt(lst1, lst2)
1000000 loops, best of 3: 1.36 µs per loop

关于@otus 的评论（下）：让我们看看在创建时使用生成器表达式是否remove_keys可以提高速度：

def alt2(lst1, lst2):
    remove_keys = set(item[:2] for item in lst2)
    unique = [item for item in lst1 if item[:2] not in remove_keys]
    return unique

In [7]: %timeit alt2(lst1, lst2)
1000000 loops, best of 3: 1.54 µs per loop

以下是包含 ~10**4 个项目的列表的基准：

In [8]: lst1 = [('vr1', '635', '1'), ('vr1', '32', '1'), ('vr1', '784', '0.526'), ('vr1', '431', '1')]*10000

In [9]: lst2 = [('vr1', '635', '3'), ('vr1', '784', '2.526'), ('vr1', '431', '2')]*10000

In [10]: %timeit alt(lst1, lst2)
100 loops, best of 3: 9.34 ms per loop

In [11]: %timeit alt2(lst1, lst2)
100 loops, best of 3: 9.49 ms per loop

In [12]: %timeit orig(lst1, lst2)
100 loops, best of 3: 13.5 ms per loop

这是另一个包含 ~10**6 项的列表的基准：

In [19]: %timeit alt(lst1, lst2)
1 loops, best of 3: 972 ms per loop

In [20]: %timeit alt2(lst1, lst2)
1 loops, best of 3: 957 ms per loop

因此，对于中小型列表，列表理解更快，但对于较大的列表，使用生成器表达式更快。当然，什么被认为是大或小取决于您的机器。您需要使用timeit进行基准测试，以了解最适合您的方法。

通常，当您有足够的内存时，如果您需要遍历整个集合，使用列表推导式似乎比生成器更快。当您没有足够的内存或不需要遍历整个集合时，生成器会更好。

查看@thg435 的解决方案也很有趣。在某些情况下它更快：

def using_dicts(lst1, lst2):
    d1 = {x[0:2]:x for x in lst1}
    d2 = {x[0:2]:x for x in lst2}
    return [d1[key] for key in set(d1) - set(d2)]

如果您的列表包含大量重复键：

lst1 = [('vr1', '635', '1'), ('vr1', '32', '1'), ('vr1', '784', '0.526'), ('vr1', '431', '1')]*10000

lst2 = [('vr1', '635', '3'), ('vr1', '784', '2.526'), ('vr1', '431', '2')]*10000

然后using_dicts比alt：

In [31]: %timeit alt(lst1, lst2)
100 loops, best of 3: 8.39 ms per loop

In [32]: %timeit using_dicts(lst1, lst2)
100 loops, best of 3: 7.98 ms per loop

我认为这是因为在上面的示例中，lst1并且lst2包含很多重复x[0:2]的 sd1并且d2很小。

如果您的lst1和lst2包含许多唯一键，例如何时

lst1 = [(i,i,i) for i in range(10**4+100)]
lst2 = [(i,i,i) for i in range(10**4)]

然后alt比using_dicts：

In [34]: %timeit alt(lst1, lst2)
100 loops, best of 3: 3.12 ms per loop

In [35]: %timeit using_dicts(lst1, lst2)
100 loops, best of 3: 5.93 ms per loop
于 2013-10-25T09:33:48.677 回答
3

你if i[:2] in uniq相当于if i[:2] not in [j[0:2] for j in lst2]. 所以你可以简单地将第二个列表变成一个集合并对其进行测试。

second = set(i[:2] for i in lst2)
full = [i for i in lst1 if i[:2] not in second]
于 2013-10-25T09:33:59.593 回答
1

我只是使用dicts not sets：

lst1 = [('vr1', '635', '1'), ('vr1', '32', '1'), ('vr1', '784', '0.526'), ('vr1', '431', '1')]
lst2 = [('vr1', '635', '3'), ('vr1', '784', '2.526'), ('vr1', '431', '2')]

d1 = {x[0:2]:x for x in lst1}
d2 = {x[0:2]:x for x in lst2}

for key in set(d1) - set(d2):
    print d1[key]   # ('vr1', '32', '1')

不知道这是否更快，但看起来更透明。

于 2013-10-25T09:38:01.993 回答
0

您无需使用代理模式进行最后一次搜索即可实现此目的：

class Wrapper:
    def __init__(self, tuple):
        self.tuple = tuple

    def __eq__(self, other):
        return self.tuple[0:2] == other.tuple[0:2]

    def __ne__(self, other):
        return not self.__eq__(other)

    def __hash__(self):
        return 0

    def __str__(self):
        return str(self.tuple)

    def __repr__(self):
        return repr(self.tuple)

lst1 = [Wrapper(('vr1', '635', '1')), Wrapper(('vr1', '32', '1')), Wrapper(('vr1', '784', '0.526')), Wrapper(('vr1', '431', '1'))]

lst2 = [Wrapper(('vr1', '635', '3')), Wrapper(('vr1', '784', '2.526')), Wrapper(('vr1', '431', '2'))]

uniq = set(lst1) - set(lst2)

print uniq

给出：

设置（[（'vr1'，'32'，'1'）]）

thg435 的答案要简单得多。我的唯一优点是您可以在Wrapper. 虽然不确定速度。

于 2013-10-25T09:36:16.273 回答