Python如何通过列表检查？

Question

我正在为codeacademy for python做一个课程练习,我有几个问题似乎无法找到答案:

对于这段代码,python究竟是如何检查某些内容是否在"in"或"not in"列表中？它是通过列表中的每个项目来检查还是使用更快的过程？

此外,如果运行大量数字列表(数千或数百万),该代码将如何受到影响？它会随着列表大小的增加而减慢,还有更好的选择吗？

numbers = [1, 1, 2, 3, 5, 8, 13]

def remove_duplicates(list):
  new_list = []
  for i in list: 
    if i not in new_list:
      new_list.append(i)
  return new_list

remove_duplicates(numbers)

谢谢!

PS为什么这段代码功能不一样？

numbers = [1, 1, 2, 3, 5, 8, 13]

def remove_duplicates(list):
  new_list = []
  new_list.append(i for i in list if i not in new_list)
  return new_list

Answer 1

为了执行i not in new_listPython,必须对列表进行线性扫描.一旦知道测试结果,扫描循环就会中断,但如果i实际上不在列表中,则必须扫描整个列表以确定它.它以C速度执行,因此它比执行Python循环以显式检查每个项目更快.偶尔进行in some_list测试是可以的,但是如果你需要做很多这样的会员测试,那么使用它会好得多set.

平均而言,对于随机数据,测试成员资格必须扫描列表项目的一半,并且通常执行扫描所花费的时间与列表的长度成比例.在通常的表示法中,列表的大小用表示n,并且该任务的时间复杂度写为O(n).

相反,确定set(或a dict)的成员资格可以在恒定时间内完成(平均),因此其时间复杂度为O(1).有关此主题的更多详细信息,请参阅Python Wiki中的TimeComplexity.谢谢,塞尔,这个链接.

当然,如果您使用a,set那么您可以免费获得重复数据删除,因为无法将重复项添加到集合中.

集合的一个问题是它们通常不保留顺序.但是您可以使用集合作为辅助集合来加速重复数据删除.下面是一种用于对列表或其他有序集合进行重复数据删除的常用技术的示例,该集合确实保留了顺序.我将使用字符串作为数据源,因为我懒得输入列表.;)

new_list = []
seen = set()
for c in "this is a test":
    if c not in seen:
        new_list.append(c)
        seen.add(c)
print(new_list)

产量

['t', 'h', 'i', 's', ' ', 'a', 'e']

请参阅如何在保留订单的同时从列表中删除重复项？更多例子.谢谢Jean-FrançoisFabre的链接.

至于你的PS,该代码附加一个生成器对象new_list,它不附加生成将产生的内容.

我假设你试图用列表理解来做到这一点:

new_list = [i for i in list if i not in new_list]

这不起作用,因为在new_listlist comp完成运行之前不存在,所以这样做in new_list会引发一个NameError.即使你new_list = []在list comp之前做过,它也不会被list comp修改,list comp的结果只会用新的替换那个空列表对象.

顺便说一句,请不要使用list变量名称(即使在示例代码中),因为它会影响内置list类型,这会导致神秘的错误消息.