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

Question

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

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

我认为这最好通过值排序字典来解决，但是一个isn't available在 Python 中(我不知道有任何库提供它)。也许有更好的解决方案？

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]