Найдите 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 *) 1014 *) временное пространство.

Обратите внимание, что результирующий список не отсортирован по длине, но можно добавить, что это можно сделать, вытолкнув элементы до тех пор, пока куча не опустеет, и не изменит результат этого.

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 строк, вы можете оставить пару строк, которые содержат длину самой короткой из найденных строк и ее индекс в списке.Если прочитана какая-либо строка, которая длиннее этой строки, вам нужно будет выполнить итерацию списка только один раз, чтобы найти новую самую короткую строку, а также заменить старую самую короткую строку.