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

Question

我有两个列表old和new，具有相同数量的元素。

我正在尝试编写一个高效的函数，它以n为参数，比较相同位置(按索引)的两个列表的元素，查找n最大的差异，并返回这些n元素的索引。

我认为最好的解决方法是使用一个值排序的字典，但是Python语言中有一个isn't available (我不知道有什么库提供它)。也许有更好的解决方案？

Answer 1

每当你想到"n largest“的时候，就想想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]

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小得多，那么最好使用heapq模块提供的nlargest函数：

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

从你的问题看，我想这就是你想要的：

在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]#

如果这不是您想要的，请考虑更详细地说明问题。