Извлеките два самых высоких элемента из списка, содержащего 100 000 целых чисел

Как получить два самых высоких элемента из списка, содержащего 100 000 целых чисел, без необходимости сначала сортировать весь список?

  • рекурсивная итерация через вложенный json для определенного ключа в python
  • Что такое хорошая стратегия группировки похожих слов?
  • Python: функция принимает 1 позиционный аргумент, но 2 даны, как?
  • Перспективная коррекция в OpenCV с использованием python
  • Развертывание Django для Heroku (ошибка Psycopg2)
  • Загрузка файла Selenium оставляет окно выбора файла открытым (OS / X и Python)
  • Scikit-learn возвращает коэффициент определения (R ^ 2) значений меньше -1
  • tail -f в веб-браузере
  • 12 Solutions collect form web for “Извлеките два самых высоких элемента из списка, содержащего 100 000 целых чисел”

    В Python используйте heapq.nlargest . Это самый гибкий подход, если вы хотите обрабатывать больше, чем только два лучших элемента.

    Вот пример.

     >>> import heapq >>> import random >>> x = range(100000) >>> random.shuffle(x) >>> heapq.nlargest(2, x) [99999, 99998] 

    Документация: http://docs.python.org/library/heapq.html#heapq.nlargest

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

    Если этот код предназначен для использования в производстве, используйте один из более эффективных / кратких ответов. Этот ответ нацелен на кого-то нового для программирования.

    Идея

    Идея проста.

    • Сохраняйте две переменные: largest и second_largest .
    • Перейдите по списку.
      • Если элемент больше largest , назначьте его самому largest .
      • Если элемент больше, чем second_largest , но меньше, чем largest , назначьте его second_largest самому second_largest .

    Начиная

    Давайте начнем.

     def two_largest(inlist): """Return the two largest items in the sequence. The sequence must contain at least two items.""" for item in inlist: if item > largest: largest = item elif largest > item > second_largest: second_largest = item # Return the results as a tuple return largest, second_largest # If we run this script, it will should find the two largest items and # print those if __name__ == "__main__": inlist = [3, 2, 1] print two_largest(inlist) 

    Хорошо, теперь у нас есть ответ JacobM как функция Python. Что происходит, когда мы пытаемся запустить его?

     Traceback (most recent call last): File "twol.py", line 10, in <module> print two_largest(inlist) File "twol.py", line 3, in two_largest if item > largest: UnboundLocalError: local variable 'largest' referenced before assignment 

    По-видимому, нам нужно установить largest прежде чем мы начнем цикл. Это, вероятно, означает, что мы также должны установить second_largest .

    Инициализация переменных

    Давайте установим largest и second_largest на 0.

     def two_largest(inlist): """Return the two largest items in the sequence. The sequence must contain at least two items.""" largest = 0 # NEW! second_largest = 0 # NEW! for item in inlist: if item > largest: largest = item elif largest > item > second_largest: second_largest = item # Return the results as a tuple return largest, second_largest # If we run this script, it will should find the two largest items and # print those if __name__ == "__main__": inlist = [3, 2, 1] print two_largest(inlist) 

    Хорошо. Давайте запустим его.

     (3, 2) 

    Большой! Теперь давайте проверим, когда inlist будет [1, 2, 3]

      inlist = [1, 2, 3] # CHANGED! 

    Давай попробуем.

     (3, 0) 

    … О, о.

    Фиксация логики

    Наибольшее значение (3) представляется правильным. Второе по величине значение совершенно неверно. Что происходит?

    Давайте рассмотрим, что делает функция.

    • Когда мы начинаем, largest равно 0, а second_largest равно 0.
    • Первый элемент в списке, который мы смотрим, равен 1, поэтому largest становится 1.
    • Следующий элемент – 2, поэтому largest становится 2.

    Но как насчет second_largest ?

    Когда мы назначаем новое значение largest , наибольшее значение фактически становится вторым по величине. Нам нужно показать это в коде.

     def two_largest(inlist): """Return the two largest items in the sequence. The sequence must contain at least two items.""" largest = 0 second_largest = 0 for item in inlist: if item > largest: second_largest = largest # NEW! largest = item elif largest > item > second_largest: second_largest = item # Return the results as a tuple return largest, second_largest # If we run this script, it will should find the two largest items and # print those if __name__ == "__main__": inlist = [1, 2, 3] print two_largest(inlist) 

    Давайте запустим его.

     (3, 2) 

    Фантастика.

    Инициализация переменных, часть 2

    Теперь попробуем его со списком отрицательных чисел.

      inlist = [-1, -2, -3] # CHANGED! 

    Давайте запустим его.

     (0, 0) 

    Это совсем не так. Откуда взялись эти нули?

    Оказывается, начальные значения для largest и second_largest были фактически больше всех элементов в списке. Первое, что вы могли бы подумать, – установить largest и second_largest по second_largest самый низкий из возможных значений в Python. К сожалению, Python не имеет минимально возможного значения. Это означает, что, даже если вы установили оба из них на 1 000 000 000 000 000 000, вы можете иметь список значений, меньших этого.

    Так что лучше всего делать? Попробуем установить largest и second_largest для первого и второго элементов в списке. Затем, чтобы избежать двойного подсчета любых элементов в списке, мы смотрим только на часть списка после второго элемента.

     def two_largest(inlist): """Return the two largest items in the sequence. The sequence must contain at least two items.""" largest = inlist[0] # CHANGED! second_largest = inlist[1] # CHANGED! # Only look at the part of inlist starting with item 2 for item in inlist[2:]: # CHANGED! if item > largest: second_largest = largest largest = item elif largest > item > second_largest: second_largest = item # Return the results as a tuple return largest, second_largest # If we run this script, it will should find the two largest items and # print those if __name__ == "__main__": inlist = [-1, -2, -3] print two_largest(inlist) 

    Давайте запустим его.

     (-1, -2) 

    Большой! Попробуем с другим списком отрицательных чисел.

      inlist = [-3, -2, -1] # CHANGED! 

    Давайте запустим его.

     (-1, -3) 

    Чего ждать?

    Инициализация переменных, часть 3

    Давайте снова рассмотрим нашу логику.

    • largest установлено равным -3
    • second_largest установлен на -2

    Подождите прямо там. Это уже кажется неправильным. -2 больше -3. Это вызвало проблему? Давай продолжим.

    • largest – -1; second_largest устанавливается на старое значение largest значения, которое равно -3

    Да, это похоже на проблему. Мы должны убедиться, что largest и second_largest заданы правильно.

     def two_largest(inlist): """Return the two largest items in the sequence. The sequence must contain at least two items.""" if inlist[0] > inlist[1]: # NEW largest = inlist[0] second_largest = inlist[1] else: # NEW largest = inlist[1] # NEW second_largest = inlist[0] # NEW # Only look at the part of inlist starting with item 2 for item in inlist[2:]: if item > largest: second_largest = largest largest = item elif largest > item > second_largest: second_largest = item # Return the results as a tuple return largest, second_largest # If we run this script, it will should find the two largest items and # print those if __name__ == "__main__": inlist = [-3, -2, -1] print two_largest(inlist) 

    Давайте запустим его.

     (-1, -2) 

    Отлично.

    Вывод

    Итак, вот код, красиво прокомментированный и отформатированный. У этого также были все ошибки, которые я мог найти из него. Наслаждаться.

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


    КПД

    Не очень эффективно. Но для большинства целей это должно быть хорошо: на моем компьютере (Core 2 Duo) список из 100 000 элементов может быть обработан за 0,27 секунды (с использованием timeit , в среднем более 100 прогонов).

    Вы перебираете список, поддерживая переменные, которые содержат значение самого высокого и второго по величине элемента, обнаруженного до сих пор. Каждый новый предмет, который встречается, заменяет любой из двух новых элементов выше (если они есть).

    Действительно гладкий способ – использовать heapq . Heapify массив (O (n)), а затем просто введите много элементов, которые вам нужны (log (n)). (Увидел этот вопрос в одном интервью, хороший вопрос, чтобы иметь в виду.)

    «2 высших» невозможно; только один элемент может быть «самым высоким». Возможно, вы имеете в виду «самое высокое 2». В любом случае вам нужно сказать, что делать, когда список содержит дубликаты. Чего вы хотите от [8, 9, 10, 10]: (10, 9) или (10, 10)? Если ваш ответ (10, 10), пожалуйста, рассмотрите ввод [8, 9, 10, 10, 10]. Что вы собираетесь делать с «самыми высокими двумя», когда вы их получите? Измените свой вопрос, чтобы дать это руководство.

    Тем временем, вот ответ, который берет первый подход (два уникальных значения):

     largest = max(inlist) second_largest = max(item for item in inlist if item < largest) 

    Вы должны добавить стражи против менее 2 уникальных значений в списке.

    Это будет работать, но я не знаю, хотите ли вы сохранить элементы в списке:

     max1 = max(myList) myList.remove(max1) max2 = max(myList) 

    Если вы это сделаете, вы можете сделать следующее:

     max1 = max(myList) idx1 = myList.index(max1) myList.pop(idx1) max2 = max(myList) myList.insert(idx1,max1) 

    Скопируйте List в List_copy . Получить наивысшее значение и получить свою позицию:

     Highest_value = max(List_copy) Highest_position = List_copy.index(max(List_copy)) 

    Назначьте 0 для Highest_value .

     List_copy[Highest_position] = 0 

    И снова запустите свою линию.

     Second_Highest = max(List_copy) 

    Итерирование по всему списку – единственный способ сделать это без сортировки.

    Без сортировки списка единственный способ сделать это – перебрать весь список и сохранить самые высокие два числа. Я думаю, вам будет лучше сортировать список.

    Второй самый высокий элемент – довольно простой случай, но для k-го наивысшего элемента вам нужен алгоритм выбора . Эта страница довольно тщательная, поэтому, вероятно, лучше всего это прочитать.

    Лучшее время, которое вы можете ожидать, является линейным, поскольку вы должны хотя бы просмотреть все элементы.

    Вот мой псевдокод, чтобы решить проблему:

     //assume list has at least 2 elements (max, nextMax) = if (list[0] > list[1]) then (list[0], list[1]) else (list[1], list[0]) for (2 <= i < length) { (max, nextMax) = if (max < list[i]) => (list[i], max) elseif (nextMax < list[i]) => (max, list[i]) else (no change) => (max, nextMax) } return (max, nextMax) 

    Я знаю, что эта тема старая, но вот простое решение этой проблемы. Протестировано против heapq.nlargest, и это немного быстрее (сортировка не требуется):

    Работает как для положительных, так и для отрицательных чисел.

    Функция ниже: Максимальное используемое время: 0,12, максимальная используемая память: 29290496 heapq.nlargest: Максимальное время использования: 0,14, максимальная используемая память: 31088640

     def two_highest_numbers(list_to_work): first = None second = None for number in list_to_work: if first is None: first = number elif number > first: second = first first = number else: if second is None: second = number elif number > second: second = number return [first, second] 
    Python - лучший язык программирования в мире.