Найдите N самых больших строк в файле: как бы вы могли это улучшить?

Я недавно получил отказ от потенциального работодателя после отправки этого кода. Они предположили, что я недостаточно технически способен. Мне интересно, может ли кто-нибудь пролить свет на то, как сделать это лучше / эффективнее.

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

РЕДАКТИРОВАТЬ3: Оказывается, мои первоначальные рассуждения были ошибочными в отношении сортировки по выбору. У меня в голове было, что минимальная куча будет nlogn, но я забыл, что средняя сложность для моего кода - n ^ 2. Спасибо всем за помощь.

0
задан casper 2 February 2012 в 20:45
поделиться