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

Question

我有两个列表，分别叫做 old 和 new，它们的元素数量是一样的。

我想写一个高效的函数，这个函数接收一个参数 n，然后比较这两个列表中相同位置（也就是索引相同）的元素，找出这 n 个元素之间最大的差异，并返回这些元素的索引。

我在想，可能用一个按值排序的字典来解决这个问题，但在Python中并没有这样的字典（我也不知道有没有相关的库可以使用）。也许还有更好的解决办法？

Answer 1

根据你的问题，我觉得你想要的是这个：

在 difference.py 文件中：

l1 = [15,2,123,4,50]
l2 = [9,8,7,6,5]


l3 = zip(l1, l2)

def f(n):
    diff_val = 0
    index_val = 0
    l4 = l3[:n]

    for x,y in l4:
        if diff_val < abs(x-y):
            diff_val = abs(x-y)
            elem = (x, y)
            index_val = l3.index(elem)

    print "largest diff: ", diff_val
    print "index of values:", index_val


n = input("Enter value of n:") 

f(n)

执行结果：

[avasal@avasal ]# python difference.py 
Enter value of n:4
largest diff:  116
index of values: 2
[avasal@avasal]#

如果这不是你想要的，请考虑详细描述一下你的问题。

Answer 2

假设你列表里的元素数量不是特别多，你可以先把所有元素的差值算出来，然后排序，最后选出前 n 个：

print sorted((abs(x-y) for x,y in zip(old, new)), reverse=True)[:n]

这样做的时间复杂度是 O(k log k)，这里的 k 是你原始列表的长度。

如果 n 比 k 小很多，最好的办法是使用 nlargest 这个函数，它在 heapq 模块里：

import heapq
print heapq.nlargest(n, (abs(x-y) for x,y in zip(old, new))

这样做的时间复杂度是 O(k log n)，而不是 O(k log k)，这在 k >> n 的情况下会有很大的区别。

另外，如果你的列表真的很大，使用 itertools.izip 可能会比普通的 zip 函数更好。

Answer 3

每当你想到“n个最大值”时，就要想到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]