通过元组元素过滤元组列表

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个二元组。

这些二元组的第一个元素大多是不同的，但有一些重复出现的情况（实际上不确定有多少个，但与列表的基数相比并不多）。

我的问题是：是否有更有效的方法来根据这些元组的元素列表筛选元组列表？

（如果这是离题或重复，请见谅。）

相关问题（未提及效率）：

Filter a list of lists of tuples

- DyingIsFun

---

那么你的实际“filter”列表有多大？为什么你觉得这是低效的，你是否有你真实情况的分析信息？ - Martijn Pieters

过滤器列表包含30,000个单词，元组列表包含约134,000个2元组。 - DyingIsFun

如果列表推导式无法满足你的需求，你应该考虑使用像 numpy 这样用 C 实现的模块。但是请注意，这种情况下你需要有一个大型列表，否则将 Python 列表转换为 numpy 数组的成本将高于从 numpy 获得的性能提升。 - Mazdak

@Silenus：那就是你的问题了，filter列表。 - Martijn Pieters

尝试将你的元组列表转换为字典，并迭代过滤器以获取(key, value)对。我现在无法测试其效率，因此不会将其发布为答案，但这可能值得一试。 - lucasnadalutti

Answer 1

在你的评论中写道：

过滤列表包含30,000个单词，元组列表包含约134,000个2个元素的元组。

in操作符针对列表的包含测试需要O(N)线性时间，当您进行134k次此操作时速度很慢。每次都必须遍历所有这些元素以查找匹配项。考虑到您正在进行过滤操作，不是所有那些第一个元素都会出现在30k列表中，因此您要执行多达30k * 134k == 40亿次比较。

改用集合（set）：

filter_set = set(filter)

集合包含性测试是O(1)常数时间；现在你把问题减少到了134k个测试。

你可以避免花费的更小部分时间是元组赋值；使用索引提取你要测试的那个元素：

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

- Martijn Pieters

---

由于过滤器列表的大小远小于2元组列表的大小，那么将2元组列表转换为字典（可能使用zip）并遍历过滤器列表如何？我不确定这是否有效。字典中值字段中的列表是副本还是引用？ 如果它是引用，那么这种方法应该更有效。 - agamagarwal

将 OP 的答案中的 O(n*m) 降低到 O(n)。 - TemporalWolf

@agamagarwal 不需要使用 zip 将其转换为 dict，只需执行 mydict = dict(tuples) 即可。 - lucasnadalutti

@agamagarwal：这需要那些第一个元素是唯一的。 - Martijn Pieters

我会犹豫更改元组，因为这会使实现依赖于数据...而这个实现set(filter)则不会。即使它们是不同的，我也会使用它，因为未来重复添加可能会以非常难以检测的方式使输出无效，因为它会默默地忽略重复项。 - TemporalWolf