python函数减速没有明显的原因

问题描述：

我有一个python函数定义如下，我用来从list1中删除已经在list2中的项目。我使用Python 2.6.2在Windows XPpython函数减速没有明显的原因

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

这里，列表1和List2是列出

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

# list2 has a similar format.

列表我试着用38000元列表1和List2此功能150,000元。如果我在打印语句中打印当前的迭代，我发现该函数在每次迭代时都会变慢。起初，它在一秒钟内处理大约1000个或更多的物品，然后一段时间后会减少到每秒20-50个。为什么会发生这种情况？

编辑：在我的数据的情况下，curIndex保持0或非常接近0，所以在list1上的弹出操作几乎总是在第一个项目上。

如果可能的话，有人可以提出一种更好的方式来以不同的方式做同样的事情吗？

compareLists（l1，l2）可能是破坏性地修改其中一个输入的函数的错误名称。如何removeDupes（l1，l2）？ – Suppressingfire 2009-11-12 16:35:00

这里有几个很好的解决方案。在这一点上，你最好的选择是尝试每种方法并计时，并确定哪种方法最有效。这实际上取决于实际瓶颈的位置。 – 2009-11-12 16:38:03

list2的嵌套程度如何？它只是一个列表清单还是结构更递归？ – 2009-11-12 16:43:20

答

尝试一个更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

set（list2）不起作用，因为Python无法散列列表：'set（[['a'，1]]）' - > TypeError：列表对象不可用。没想到要么...... – 2009-11-12 16:41:10

这一行给我一个错误TypeError：不可用类型：'list' – randomThought 2009-11-12 16:41:21

虽然（set（[（'（'a'，1），]）''），它可以与元组一起工作。有没有一种快速的方法来将'list2'中的列表转换为元组？ – 2009-11-12 16:42:16

答

编辑：我已经更新了我的答案，以解释列表不可用，以及其他一些反馈。这一个甚至被测试。

它可能涉及从列表中间弹出一个项目的成本。

或者你是否尝试过使用集合来处理这个问题？

def difference(list1, list2): 
    return [x for x in list1 if tuple(x) in set(tuple(y) for y in list2)]

然后，您可以设置列表中的一个所得到的名单，如果这是你的意图做

list1 = difference(list1, list2)

集是纯粹的喜悦。很好的选择。 – 2009-11-12 16:32:36

在我的数据的情况下，curIndex保持为0或非常接近于0，因此list1上的弹出操作几乎总是在第一项上 – randomThought 2009-11-12 16:33:11

您要花费调整数组大小的代价，请尝试使用方法I'发帖并看看。我想这会导致更快的操作，因为大部分处理都会发生在C端而不是循环内部。 – 2009-11-12 16:35:30

答

如果我们排除了数据结构本身出来，看看你的内存使用情况未来。如果你最终要求操作系统为你换取内存（例如，列表占用的内存比你多），Python会坐在等待操作系统的IP地址上，以便从磁盘中获取页面，这是有道理的。描述。

当这种放缓发生时，Python坐在iowait的按摩浴缸中吗？环境中还有其他事情吗？

（如果你不知道，更新你的平台和我们的人会告诉你如何辨别真假。）

你可以看到，在Linux上做顶部并看着它在io上等待的时间百分比。这是百分比的wa部分。他们可能会在做多少次编辑操作。 – 2009-11-12 16:33:30

我怎样才能找到？我在Windows XP上运行它。 – randomThought 2009-11-12 16:33:58

在XP上，您将不得不使用第三方玩具来实现这一点。看看http://technet.microsoft.com/en-us/sysinternals/bb896653.aspx - 我过去使用过Process Explorer，它会告诉你Python正在做的一切。虽然不能告诉你如何使用虚拟内存来查找Windows（这就是它所称的交换）。 – 2009-11-12 16:37:24

答

的代码变慢的唯一原因是你在这两个列表中都有很大的元素，它们共享许多共同的元素（所以list1[curIndex] in list2需要更多时间）。

这里有一些方法来解决这个问题：

如果你不关心顺序，两个列表转换成set S和使用set1.difference(set2)
如果在列表1的顺序是重要的，那么至少将list2转换成一个集合，因为in要快得多，set。
最后，尝试筛选器：filter(list1, lambda x: x not in set2)

[编辑]由于set()不递归列出工作（没想到），尝试：

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

它应该仍然比你的版本快得多。如果不是，那么你最后的选择是确保两个列表中都不能有重复的元素。这将允许您从中删除列表中的项目（并因此使得比较更便宜，因为您从list2中找到元素）。

答

有2个问题，导致你的算法不佳规模：

x in list复杂度为O（n）的操作。
pop(n)其中n在阵列的中间是O（n）操作。

这两种情况都会导致它对大量数据缩小O（n^2）。 gnud的实现可能是最好的解决方案，因为它可以在不改变元素顺序或删除潜在重复的情况下解决这两个问题。

答

通常建议set不会在这里工作，因为这两个列表包含列表，这是不可能的。你需要首先改变你的数据结构。

可以

转换成子列表元组类的实例，使他们可哈希，然后使用套。
保持两个列表的排序，那么你只需要比较列表的头。

python函数减速没有明显的原因

相关推荐