列表搜索优化

Question

first = [(1, text, text, 1, 2, 3), 
         (1, text, text, 1, 0, 3), ... (6054, text, text, 2, 2, 3)]
second = (1, 2, 3, 4, 5 ... 5412)

有没有更快的方法来做到这一点:

data = [x for x in first if x[0] in second]

Answer 1

试试这个:

first = [(1, text, text, 1, 2, 3), 
         (1, text, text, 1, 0, 3), ... (1054, text, text, 2, 2, 3)]
second = (1, 2, 3, 4, 5 ... 5412)
second_set = set(second)
data = [x for x in first if x[0] in second_set]

假设首先有m个元素,第二个有n个元素.

集合是经过哈希处理的,因此搜索它们接近于O(1),总体效率为O(m).在列表中搜索第二个是O(n),其总效率为O(m*n).