python - 以相同顺序打印列表的最大值而不创建新列表

Question

这里有一个列表

[9,1,2,11,8]

我需要打印此列表中的前 3 名，例如

[9,11,8]

很容易排序和获取最高值并循环遍历相同的复制列表以找到给定顺序的最高值 但我不应该为此任务使用新列表。 这可能吗？

Answer 1

def k_largest(iterable, k=3):
    it = iter(iterable)
    result = [next(it) for _ in range(k)] # O(k) space
    r_min = min(result)
    for elem in it:
        if elem > r_min:
            result.remove(r_min)  # O(n*k) time
            result.append(elem)
            r_min = min(result)
    return result

在平局的情况下，第一个值获胜。如果您想要最后一个值取胜，只需将 > 更改为 >=。

对于大数据和小选择，这是一个很好的方法，即其中 n >> k 其中 n 是输入的长度，k 是选择的数字。 在这种情况下，k 项无关紧要，因此该方法的时间复杂度为 O(n)，有利于 O(n log n) 的基于排序的方法。如果 k 很大，这将不再是一个好的解决方案。您应该考虑维护一个排序的结果集，将其一分为二以进行插入，或许还可以使用 quickselect找到最大值。

使用 Python stdlib 的 heapq.nlargest 可以使用另一个具有更简单代码的选项。 ，尽管在实践中通常会更慢:

import heapq
from operator import itemgetter

def k_largest_heap(iterable, k=3):
    ks = heapq.nlargest(k, enumerate(iterable), key=itemgetter(1))
    return [k for i, k in sorted(ks)]

我认为这是O(n log(k))，尽管不可否认我在这里已经达到了知识的边缘。

10,000 个整数列表的一些计时:

from random import randint
nums =  [randint(1, 10000) for _ in range(10000)]
%timeit k_largest(nums)
# 331 µs ± 4.69 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit k_largest_heap(nums)
# 1.79 ms ± 27.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit top_three(nums)
# 1.39 ms ± 16.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

注意 top_three 实现是来自用户 Delirious Lettuce here 的解决方案.