7

我正在考虑一个我以前没有遇到过的问题，并且我正在尝试确定要使用的最有效的算法。

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

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

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

4

4 回答 4

11

看看heapq.nlargest：

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

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

于 2013-06-25T14:47:52.927 回答
4

您可以使用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)
于 2013-06-25T14:51:23.770 回答
1

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

于 2013-06-25T14:51:16.093 回答
1

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

希望没有错别字：

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:]
于 2013-06-25T15:05:19.457 回答