Python快速排序

Question

我正在考虑一个以前从未遇到过的问题，我正在努力确定要使用的最有效的算法。

我在两个列表上迭代，使用每对元素来计算一个我希望排序的值。我的最终目标是获得前二十个结果。我可以将结果存储在第三个列表中，按绝对值对该列表进行排序，然后简单地对前二十个列表进行切片，但这并不理想。

由于这些列表有可能变得非常大，我理想情况下只存储前二十个绝对值，在计算新的最高值时驱逐旧值。

在python中实现这一点最有效的方法是什么？

Answer 1

看看heapq.nlargest:

heapq.nlargest(n, iterable[, key])

从iterable定义的数据集中返回一个包含n最大元素的列表key（如果提供）指定一个参数的函数，该函数用于从可迭代的中的每个元素提取比较键：key=str.lower等效于：sorted(iterable, key=key, reverse=True)[:n]

Answer 2

您可以使用izip并行迭代两个列表，并构建一个生成器对它们进行延迟计算，然后使用heapq.nlargest有效地保持顶部的n:

from itertools import izip
import heapq
list_a = [1, 2, 3]
list_b = [3, 4, 7]
vals = (abs(a - b) for a, b in izip(list_a, list_b))
print heapq.nlargest(2, vals)

Answer 3

有一个大小为20的元组的列表，初始化时使用小于最小计算结果和两个索引-1。在计算结果时，将其附加到结果列表中，使用结果对的索引，仅对值进行排序，并将列表修剪为长度20。应该相当有效，因为你只对长度为21的列表进行排序。

Answer 4

我知道已经选择了最佳答案，但出于教育目的，你也可以考虑我的答案。

我希望没有错别字：

def some_name(list_a, list_b):
    if len(list_a) != len(list_b):
        raise Exception("Too bad")
    result_list = []
    for result in (list_a[i] + list_b[i] for i in range(len(list_a))):
        if len(result_list) >= 20:
            if result_list[0] > result:
                continue
            result_list = result_list[1:]
        result_list.append(result)
        result_list.sort()

经过一些重构，它几乎和heapq.nlargest一样（当然，这里我们必须自己对结果进行排序）：

def some_name(list_a, list_b):
    if len(list_a) != len(list_b):
        raise Exception("Too bad")
    result_list = []
    for result in (list_a[i] + list_b[i] for i in range(len(list_a))):
        result_list.append(result)
        result_list.sort()
        result_list = result_list[-20:]