带有lambda函数的filter（）的复杂性分析 [英] Complexity analysis of filter() with a lambda function

问题描述

给定两个列表， list1 和 list2

 list3 = filter（lambda x：x in list1，list2）
  

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

如何找到此算法的复杂性？我发现list1 中 x的时间复杂度是 O（n） 其中n是列表中元素的数量，但过滤器？

$如何b $ b

解决方案

您的代码不会执行 O（len（list1）* len（list2））比较操作元素。

• 您的lambda函数执行 O（len（list2））次，每过滤一个元素一次。 在Python中查看 filter 的文档3 （ Python 2 ）：

  
  

  filter（函数，可迭代）

  
  
  

  从那些 iterable 的元素构造一个迭代器，该函数返回true 。 iterable 可以是一个序列，支持迭代的容器或者迭代器。
  

  （强调我的）

  
  
  

  显然，函数对迭代中的每个（不同的）元素至少调用一次 - 知道何时不需要调用它意味着还解决一般情况下的停机问题，即使Python核心开发人员尚未解决;-) 。实际上，在CPython 3中， filter code> builtin 创建一个迭代器，它在先进的，在迭代顺序中为每个元素执行一次函数（distinct或not）。

x in list1 does O（len（list1） ）在平均和最差情况下的比较，如记录。

---

为了加快速度，使用 set ;你也不需要lambda函数（使用 __包含__ 魔术方法）

  list3 = filter（set（list1）.__ contains__，list2）
  

这会建立一个<$ O（len（list1））中的 list1 的c $ c> set （len（list1）+ len（list2））的平均复杂度< O（len（list2）） / code>

---

如果 list2 并不重要然后你也可以做

  set（list1）.intersection（list2） 
  

它们的常量应小于过滤器以上;对于真正快速的代码，您应该对列表进行排序，以使 变成一个集合（因为交集和集合构建的文档平均复杂度均为 O（n），但由于调整了 set 的大小，set build很可能会有更大的常量，因此从小到大建立集合以减少这些常量的权重）：

 更小，更大= sorted（[list1，list2]，key = len）
 result = set（small）.intersection（large）
  

---

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

Given two lists, list1 and list2

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

This returns the intersection of the two lists.

How can I find the complexity of this algorithm? I have found out that the time complexity of x in list1 is O(n) where n is number of elements in the list, but how about the filter?

解决方案

Your code does O(len(list1) * len(list2)) comparison operations for elements.

• Your lambda function is executed O(len(list2)) times, once per each element filtered. See documentation for filter in Python 3 (Python 2):

  filter(function, iterable)

  Construct an iterator from those elements of iterable for which function returns true. iterable may be either a sequence, a container which supports iteration, or an iterator

  (emphasis mine)

  Clearly the function is called at least 1 time for each (distinct) element in iterable - knowing when not to need call it would mean also solving the Halting problem in general case, which not even the Python core developers are yet to solve ;-). In practice in CPython 3 the filter builtin creates an iterator which when advanced, executes the function once for each element (distinct or not) in the iteration order.

• The x in list1 does O(len(list1)) comparisons in average and worst case, as documented.

---

To speed it up, use a set; also you do not need a lambda function at all (use __contains__ magic method)

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

This builds a set of the list1 once in O(len(list1)) time and runs the filter against it with O(len(list2)) average complexity for O(len(list1) + len(list2))

---

If the ordering of elements of list2 does not matter then you can also do

set(list1).intersection(list2)

which should have lower constants than doing the filter above; and for really fast code, you should order the lists so that the smaller is turned into a set (since both intersection and set building have documented average complexity of O(n), but set building most probably will have larger constants due to resizing the set, thus it will make sense to build the set from the smaller to decrease the weight of these constants):

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

---

Notice that Python 2 and 3 differ from each other. filter in Python 3 returns a generator, and the actual running time depends on the number of elements consumed from the resulting generator, whereas in Python 2 a list will be generated upfront, which might be more costly if you need only the first values.

这篇关于带有lambda函数的filter（）的复杂性分析的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！