Как я могу отсортировать 1 миллион чисел и напечатать только 10 лучших в Python?

Если вам нужны только первые 10 значений, вы потратите много времени на сортировку каждого числа.

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

Это будет означать, что вам нужно сделать только один проход через файл (т.е. временная сложность тета (n))

Простая задача

Вы можете рассматривать свою проблему как обобщение поиска максимального значения в списке чисел. Если бы вам дали {2,32,33,55,13, ...} и попросили найти наибольшее значение, что бы вы сделали? Типичное решение состоит в том, чтобы пройтись по списку, запоминая при этом наибольшее число, встречавшееся до сих пор, и сравнивая его со следующим числом.

Для простоты предположим, что мы имеем дело с положительными числами.

Initialize max to 0
0 < 2, so max = 2
2 < 32, so max = 32
32 < 33, so max = 33
33 < 55, so max = 55
55 > 13, so max = 55
...
return max

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

Обобщение

Поиск 10 первых значений в списке очень похож. Единственная разница в том, что нам нужно отслеживать топ-10, а не только максимум (топ-1).

Суть в том, что вам нужен контейнер, который содержит 10 значений. Когда вы перебираете свой гигантский список чисел, единственное значение, которое вас волнует в контейнере size-10, — это минимум. Это потому, что это номер, который будет заменен, если вы обнаружите новый номер, который заслуживает того, чтобы быть в топ-10 на данный момент.

В любом случае оказывается, что структура данных, лучше всего подходящая для быстрого поиска минут, — это куча минут. Но я не уверен, что вы уже знаете о кучах, и накладные расходы на использование кучи для 10 элементов могут перевесить ее преимущества.

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

Лучшая сортировка — это частичная сортировка, доступная в библиотеке Python как heapq.nlargest.

Вам нужен хороший алгоритм выбора.

Следующий код Python основан на функции partition() partition, которая разбивает список на две части. Значения меньше "pivotValue" перемещаются в начало списка. Значения больше, чем pivotValue, перемещаются в конец списка. Это делается за O(N) операций, проходя по списку от начала до конца, каждый раз, когда он просматривает значение, он перемещает его ближе к началу списка, только если оно меньше, чем опорное значение.

(обратите внимание, что в вашем случае мы фактически перемещаем большие значения в начало списка, так как вам нужны самые большие значения, а не самые маленькие).

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

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

Вот код:

def partition(_list,left,right,pivotIndex):
    pivotValue=_list[pivotIndex]
    _list[right],_list[pivotIndex]=pivotValue,_list[right]
    storeIndex=left
    for i in range(left,right):
        if _list[i] > pivotValue:
            _list[storeIndex],_list[i]=_list[i],_list[storeIndex]
            storeIndex+=1
    _list[right],_list[storeIndex]=_list[storeIndex],_list[right]
    return storeIndex

from random import randint
def select(_list,left,right,k):
    if left==right:
        return _list[:left+1]
    pivotIndex=randint(left,right)
    pivotNewIndex=partition(_list,left,right,pivotIndex)
    pivotDist=pivotNewIndex-left+1
    if pivotDist==k:
        return _list[:pivotNewIndex+1]
    elif k<pivotDist:
        return select(_list,left,pivotNewIndex-1,k)
    else:
        return select(_list,pivotNewIndex+1,right,k-pivotDist)

_list=[1,2,109,2234,23,6,1,234,11,4,12451,1]

left=0
right=len(_list)-1
pivotIndex=4

print _list
"[1, 2, 109, 2234, 23, 6, 1, 234, 11, 4, 12451, 1]"
print partition(_list,left,right,pivotIndex) #partition is order(N).
"7" #index 7, so the lowest number are in the first 7 numbers of the list [1, 2, 1, 6, 1, 11, 4, 23]
print _list
"[1, 2, 1, 6, 1, 11, 4, 23, 2234, 109, 12451, 234]"
print select(_list,left,right,10)
"[1, 2, 1, 1, 4, 11, 6, 23, 109, 234]"

with open('nums.txt') as f:
    numbers=map(int,f.readlines())
    print select(numbers,0,len(numbers)-1,10)
    "[1132513251, 2000, 23512, 13252365, 1235, 1251, 324, 100, 82, 82]"