Набросок здесь. Где N = len(data_list) и S = sqrt(N), использует O(S) дополнительную память и занимает наихудший случай O(N*log(N)) время:
Для каждого последовательного фрагмента длины S в оригинале данные, скопируйте этот фрагмент во временный список, используйте .sort(), чтобы отсортировать его на месте, затем запишите результат в уникальный временный файл. Всего будет около S временных файлов.
Введите эти временные файлы в heapq.merge(). Это генератор, отслеживающий только S наименьших на данный момент значений на входах S, поэтому эта часть также имеет O(S) нагрузку на память.
Удаление временных файлов .
Чем больше памяти вы можете использовать для этого, тем меньше временных файлов потребуется, и тем быстрее это будет go.
Сокращение постоянного коэффициента
Как отмечается в комментариях, надежда для алгоритма времени суб-квадратичного c невелика. Тем не менее, вы можете сделать многое, чтобы сократить постоянный коэффициент в вашем исходном алгоритме, сократив количество проходов по данным. Вот один из способов получения следующих K записей при каждом проходе по данным. Тем не менее, оно остается в квадрате c -время общего времени.
def sorted_nocopy_generator(data_list, K=100):
import itertools
from bisect import insort
assert K >= 1
total = 0
too_small = None
while total < len(data_list):
active = [] # hold the next K entries
entry2count = {}
for entry in data_list:
if entry in entry2count:
entry2count[entry] += 1
elif ((too_small is None or too_small < entry) and
(len(active) < K or entry < active[-1])):
insort(active, entry)
entry2count[entry] = 1
if len(active) > K: # forget the largest
del entry2count[active.pop()]
for entry in active:
count = entry2count[entry]
yield from itertools.repeat(entry, count)
total += count
too_small = active[-1]
И устранение наихудших случаев
Как и в ответе @ btilly, наихудшие случаи в приведенном выше коде можно обойти, используя максимальная куча вместо. Затем добавление новой записи в active имеет наихудшее время O(log(K)) вместо O(K).
К счастью, модуль heapq уже предоставляет что-то пригодное для этой цели. Но работа с дубликатами становится чем-то вроде головной боли - максимальная куча «под прикрытием», используемая heapq, не раскрывается.
Так что в следующих особых случаях самый большой из самых маленьких K записей интерес, используя .count() (как в вашей исходной программе), чтобы сделать полный проход, чтобы подсчитать, сколько их.
Но вместо того, чтобы делать это для каждого уникального элемента, он требуется только один раз для K элементов.
Дополнительное использование памяти пропорционально K.
def sorted_nocopy_generator(data_list, K=100):
import itertools
from heapq import nsmallest
assert K >= 1
too_small = None
ntodo = len(data_list)
while ntodo:
if too_small is None:
active = nsmallest(K, data_list)
else:
active = nsmallest(K, (x for x in data_list
if x > too_small))
too_small = active[-1]
for x in active:
if x == too_small:
break
yield x
ntodo -= 1
count = data_list.count(too_small)
yield from itertools.repeat(too_small, count)
ntodo -= count
assert ntodo >= 0