python 性能问题，代码可以工作，但考虑在长列表中花费很长时间

kcugc4gi 于 2022-12-21 发布在 Python

关注(0)|答案(3)|浏览(122)

为什么下面的代码在时间复杂度方面被认为是低效的，我该如何改进它？ia in n的时间复杂度为o（n），因此问题出现了。
我累了什么？我最初排序了n，a和B，但性能没有变化。
客观，求h-m之和注：len（a）始终等于len（B）

n=[1, 5, 3] #//can be with 100K+ items
a=set([3,1]) #//can be with 50K+ items
b=set([5,7])

h=0
m=0
for ia, ib in zip(a,b):
    if ia in n:
        h+=1
    if ib in n:
        m+=1

print (h-m)

编辑：我意识到仅仅讨论概念是不够的，比如为什么它被认为是低效的，而没有明确地解决时间/空间复杂性。我相应地改变了问题。

python

来源：https://stackoverflow.com/questions/73780903/performance-problem-code-works-but-consider-takes-long-time-in-long-list

3条答案

按热度按时间

js81xvg61#

由于n是一个list，而且它非常大（超过10万个条目），因此每个if WHATEVER in n:都在做O(n)的工作，涉及超过10万个相等性检查。
基本上你的类型是反着来的你使用set来做你迭代的事情（作为set除了可能从你的输入中删除重复之外，可以节省一点），使用list来做你的成员测试（O(n)包含检查在大型list上比O(1)包含检查在任何大小的set上要昂贵得多）。
假设n的元素是可散列的，在循环之前将它们转换为set，并对set使用包含测试：

n=[1, 5, 3] #can be with 100K+ items
nset = set(n)   # Cache set view of n
a=set([3,1]) #can be with 50K+ items
b=set([5,7])

h=0
m=0
for ia, ib in zip(a,b):
    if ia in nset:  # Check against set in O(1)
        h+=1
    if ib in nset:  # Check against set in O(1)
        m+=1

print (h-m)

注意，zip ing除了可能从被迭代的元素中排除一些元素之外什么也不做; if len(a) != len(b)，则无法检查迭代长度超过最短set的元素。如果要计算所有元素，最简单的解决方案是拆分循环，将单个循环替换为：

h = sum(1 for ia in a if ia in nset)  # sum(ia in nset for ia in a) also works, but it's somewhat slower/less intuitive
m = sum(1 for ib in b if ib in nset)

赞(0）回复(0）举报 2022-12-21

fv2wmkja2#

这里有一个简单的方法-使用set.intersection-并且不使用for循环或zip函数：

n = [1, 5, 3]  # can be with 100K+ items
a = {3, 1}  # can be with 50K+ items
b = {5, 7}

nset = set(n)  # cache set view of n

h = len(nset & a)
m = len(nset & b)

print(h - m)

赞(0）回复(0）举报 2022-12-21

x9ybnkn63#

推测一下，if x in y测试是最慢的，把a和b作为集合可能没有多大帮助--你只是在压缩和枚举，但是如果n是一个集合，那么成员资格测试可能会更快。
可能没有必要压缩，因为你似乎没有对ia和ib做任何事情，使它们交互，但我怀疑这会引入很多开销。

赞(0）回复(0）举报 2022-12-21