找到两个列表之间的最大差异

Question

我有两个列表,old并且new具有相同数量的元素.

我正在尝试编写一个有效的函数,它将n参数作为参数,在相同位置比较两个列表的元素(按索引),找出n最大的差异,并返回这些n元素的索引.

我认为这最好通过值排序的字典来解决,但是Python中没有一个(并且我不知道任何提供它的库).也许有更好的解决方案？

Answer 1

每当你想到" 最大的 "时,请想一想heapq.

>>> import heapq
>>> import random
>>> l1 = [random.randrange(100) for _ in range(100)]
>>> l2 = [random.randrange(100) for _ in range(100)]
>>> heapq.nlargest(10, (((a - b), a, b) for a, b in zip(l1, l2)))
[(78, 99, 21), (75, 86, 11), (69, 90, 21), (69, 70, 1), (60, 86, 26), (55, 95, 40), (52, 56, 4), (48, 98, 50), (46, 80, 34), (44, 81, 37)]

这将在O(n log x)时间内找到x个最大项目,其中n是列表中项目的总数; 排序在O(n log n)时间内进行.

我突然意识到上面并没有真正按照你的要求去做.你想要一个索引!还是很容易的.我也会abs在这里使用,以防你想要差异的绝对值:

>>> heapq.nlargest(10, xrange(len(l1)), key=lambda i: abs(l1[i] - l2[i]))
[91, 3, 14, 27, 46, 67, 59, 39, 65, 36]