Python函数无故变慢

2 投票

6 回答

664 浏览

提问于 2025-04-15 15:56

我有一个用Python写的函数，功能是从list1中删除那些已经在list2里的项目。我是在Windows XP上使用Python 2.6.2。

def compareLists(list1, list2):
    curIndex = 0
    while curIndex < len(list1):
        if list1[curIndex] in list2:
            list1.pop(curIndex)
        else:
            curIndex += 1

这里，list1和list2都是列表的列表。

list1 = [ ['a', 11221, '2232'], ['b', 1321, '22342'] .. ]

# list2 has a similar format.

我用这个函数处理了一个包含38,000个元素的list1和一个包含150,000个元素的list2。如果我在代码里加一个打印语句来显示当前的迭代次数，我发现随着每次迭代，函数的速度变得越来越慢。最开始的时候，它每秒能处理大约1000个以上的项目，但过了一段时间后，这个速度降到了每秒大约20到50个。这是为什么呢？

补充说明：在我的数据中，curIndex的值一直保持在0或者非常接近0，所以对list1的pop操作几乎总是针对第一个项目。

如果可以的话，有人能建议一种不同的方法来实现同样的功能吗？

性能优化列表操作数据结构内存管理数据处理编程调试算法复杂度迭代效率

6 个回答

代码变慢的唯一原因是你有两个列表中都包含很多相同的元素（所以 list1[curIndex] in list2 这个检查会花更多时间）。

这里有几种解决办法：

如果你不在乎顺序，可以把两个列表都转换成 set（集合），然后用 set1.difference(set2) 来处理。
如果 list1 的顺序很重要，那么至少把 list2 转换成集合，因为用 set 来检查元素是否存在会快很多。
最后，可以试试用过滤器： filter(list1, lambda x: x not in set2)。

[编辑] 由于 set() 不适用于递归列表（这点没想到），可以试试：

result = filter(list1, lambda x: x not in list2)

这样做应该会比你原来的版本快很多。如果还是不快，那你最后的选择就是确保两个列表中没有重复的元素。这样你就可以从两个列表中移除元素（这样在比较 list2 的元素时会更省时间）。

回答于 2025-04-15 由 Python大师

分享举报

你的算法有两个问题，导致它在处理大量数据时表现不佳：

x in list这个操作需要花费O(n)的时间。
pop(n)如果n在数组的中间位置，这个操作同样需要O(n)的时间。

这两种情况都会让算法在处理大量数据时变得很慢，整体复杂度达到O(n^2)。gnud的实现可能是最好的解决方案，因为它解决了这两个问题，同时不会改变元素的顺序或删除可能的重复项。

回答于 2025-04-15 由 Python大师

分享举报

试试更符合Python风格的过滤方法，比如这样：

[x for x in list1 if x not in set(list2)]

把两个列表都转成集合其实没必要，而且在处理大量数据时会非常慢，还会占用很多内存。

因为你的数据是一个列表的列表，所以你需要做点什么来进行哈希处理。

试试这个：

list2_set = set([tuple(x) for x in list2])
diff = [x for x in list1 if tuple(x) not in list2_set]

我用以下测试数据测试了你原来的函数和我的方法：

list1 = [[x+1, x*2] for x in range(38000)]
list2 = [[x+1, x*2] for x in range(10000, 160000)]

时间记录 - 这不是科学测试，但还是有参考价值：

 #Original function
 real    2m16.780s
 user    2m16.744s
 sys     0m0.017s

 #My function
 real    0m0.433s
 user    0m0.423s
 sys     0m0.007s

回答于 2025-04-15 由 Python大师

分享举报

Python函数无故变慢

6 个回答

撰写回答