使用 lambda 函数对 filter() 进行复杂性分析

给定两个列表，list1 and list2

list3 = filter(lambda x: x in list1,list2)

这将返回两个列表的交集。

我怎样才能找到这个算法的复杂度？我发现时间复杂度x in list1 is O(n)其中 n 是列表中的元素数量，但是怎么样filter?

你的代码确实O(len(list1) * len(list2))元素的比较操作。

• 您的 lambda 函数已执行O(len(list2))次，每个过滤元素一次。请参阅文档filter在Python 3中 (Python 2):

  filter(function, iterable)

  构建一个iterator from 的那些元素iterable哪个函数返回 true. iterable可以是序列、支持迭代的容器或迭代器

  （强调我的）

  显然，对于可迭代中的每个（不同）元素，该函数至少被调用 1 次 - 知道何时不需要调用它也意味着解决一般情况下的停止问题，甚至连 Python 核心开发人员都还没有解决这个问题；-)。在 Python 3 的实践中filter builtin创建一个迭代器，当advanced，对迭代顺序中的每个元素（无论是否不同）执行该函数一次。

• The x in list1 does O(len(list1))如记录的那样，对平均情况和最坏情况进行比较。

要加快速度，请使用set;而且你根本不需要 lambda 函数（使用__contains__魔术方法）

list3 = filter(set(list1).__contains__, list2)

这构建了一个set of the list1曾在O(len(list1))时间并对其运行过滤器O(len(list2))平均复杂度为O(len(list1) + len(list2))

如果元素的顺序为list2 不要紧那么你也可以做

set(list1).intersection(list2)

其常数应该比执行的要低filter多于;对于真正快速的代码，您应该对列表进行排序，以便smaller变成一个集合（因为交集和集合构建都记录了平均复杂度O(n)，但由于调整大小，集合构建很可能会有更大的常数set，因此从较小的集合构建集合以减少这些常量的权重是有意义的）：

smaller, larger = sorted([list1, list2], key=len)
result = set(smaller).intersection(larger)

请注意，Python 2 和 3 彼此不同。filter在 Python 3 中返回一个生成器，实际运行时间取决于生成的生成器消耗的元素数量，而在 Python 2 中将预先生成一个列表，如果您只需要第一个值，则成本可能会更高。