按元组元素过滤元组列表

Question

我正在使用Python(2.7.9),并试图通过这些元组的元素列表来过滤元组列表.特别是,我的对象具有以下形式:

tuples = [('a', ['a1', 'a2']), ('b',['b1', 'b2']), ('c',['c1', 'c2'])]
filter = ['a', 'c']

我是Python的新手,过滤我可以发现的元组的最简单方法是使用以下列表理解:

tuples_filtered = [(x,y) for (x,y) in tuples if x in filter]

生成的筛选列表如下所示:

tuples_filtered = [('a', ['a1', 'a2']), ('c',['c1', 'c2'])]

不幸的是,这种列表理解似乎效率很低.我怀疑这是因为我的元组列表比我的过滤器,字符串列表大得多.特别是,过滤器列表包含30,000个单词,元组列表包含大约134,000个2元组.

2元组的第一个元素在很大程度上是不同的,但有一些重复的第一个元素的实例(实际上不确定有多少,但与列表的基数相比,它并不多).

我的问题:是否有更有效的方法来过滤这些元组的元素列表的元组列表？

(如果这是偏离主题或欺骗,请道歉.)

相关问题(未提及效率):

过滤元组列表的列表

Answer 1

在评论中你写道:

筛选器列表包含30,000个单词,元组列表包含大约134,000个2元组.

in对列表的包含测试需要O(N)线性时间,当你这样做134k次时这是很慢的.每次必须迭代所有这些元素以找到匹配项.鉴于您正在过滤,并非所有这些第一个元素都将出现在30k列表中,因此您执行高达30k*134k == 40亿次比较.

改为使用集合:

filter_set = set(filter)

设置包含测试是O(1)常数时间; 现在你把你的问题减少到134k测试.

你可以避免支出的一小部分时间是元组分配; 使用索引来提取您正在测试的一个元素:

tuples_filtered = [tup for tup in tuples if tup[0] in filter_set]