从文件中查找 N 个最大的行：如何做得更好？

Question

最近，我在提交此代码后被潜在雇主拒绝。他们认为我技术能力不够。我想知道是否有人可以阐明如何使其更好/更高效。

问题是从多行文件中找到最长的 N 行。这最终归结为一个排序问题，因此我构建了一个算法来从数字列表中查找 N 个最大数字，如下所示：

def selection(numbers, n):

    maximum = []

    for x in range (0, n):

        maximum.append(numbers[x])
        ind = x

        for y in range ( x, len(numbers) ):
            if numbers[y] > maximum[len(maximum)-1]:
                maximum[len(maximum)-1] = numbers[y]
                numbers[ind], numbers[y] = numbers[y], numbers[ind]

    return maximum

运行时间为 O(n)，除非 N = n，其中其运行时间为O(n^2)。我很惊讶听到他们怀疑我的技术能力，所以我想我会把它带给你。我该如何改善？

编辑：感谢您的反馈。澄清一下：我用文件中的逐行字数填充了一个列表，并通过此函数运行它。

编辑2：有些人提到了语法。我只用了大约一两天的Python。我的雇主建议我用 Python 编写它（我提到我不懂 Python），所以我认为小的语法错误和方法不会是这样的问题。

EDIT3：结果是我最初的选择排序的推理存在缺陷。我脑子里认为最小堆是 nlogn，但我忘记了我的代码的平均复杂度是 n^2。感谢大家的帮助。

Answer 1

from heapq import nlargest

def longest_lines(n, filename):
    with open(filename) as input:
        return nlargest(n, input, key=len)

好吧，解决下面的评论：

def longest_lines(n, filename):
    heap = []
    with open(filename) as input:
        for ln in filename:
            push(heap, ln)
            if len(heap) > n:
                pop(heap)
    return heap

其中 push 和 pop 是很好的旧最小堆插入和删除最小算法，可以在任何教科书中找到（而且我从来没有一口气完成，所以我现在不发布它们），按长度比较行。运行时间为 O(N×lg(n))，其中 N 是文件中的行数，消耗 O(n)) 时间>n) 临时空间。

请注意，结果列表不是按长度排序的，而是可以通过弹出元素直到堆为空并反转结果来完成添加。

Answer 2

我会使用堆，但使用最小堆，而不是最大堆，这似乎违反直觉。

Create an empty heap.
For each line, 
  if there are less than N lines in the heap, add the current line;
  otherwise,
    if the current line is longer than the minimum element in the heap,
      remove the minimum element from the heap, and
      add the current line to the heap.
Return the contents of the heap.

Answer 3

这归结为排序吗？如果您有一个可以容纳 N 行的列表，则可以保留几个整数来保存迄今为止找到的最短行的长度及其在列表中的索引。如果读取到的任何行比该行长，则只需迭代列表一次即可找到新的最短行并替换旧的最短行。