Вместо этого сортируйте кортежи.
tuples = [(d['index'], d['value'])
for d in array]
tuples.sort()
Вы не опубликовали timeit данных.
Покажите нам репрезентативные данные,
и фактическое время,
а затем опишите, какой пересмотренный график будет приемлемым.
Не ясно, что вы можете победить Тимсорт ,
хотя, безусловно, лямбда-издержки будут значительными.
Если вам нужно еще быстрее, уберите неактуальный атрибут value:
indices = [d['index']
for d in array]
indices.sort()
Несколько прошедших времен имеют значение:
- время для создания списка
- время сортировать список
- время использовать отсортированный список
Как указано, ваш вопрос недостаточно уточнен,
поскольку он не ограничивает (1.) или (3.),
и мы все знаем, что есть ложь, проклятая ложь и микро-ориентиры.
начальный (полусортированный) заказ,
распределение ценностей,
и шаблон доступа к отсортированному списку все имеет значение
за прошедшее время.
Некоторые проблемы требуют только подмножества полной семантики Python3,
и поддаются оптимизации numba .
Вы не сказали нам достаточно
сказать, применимо ли это к вашей бизнес-проблеме.
EDIT
Timsort на современной платформе может легко сортировать 4 миллиона элементов в секунду
в форме кортежа,
несколько меньше, чем если lambda накладные расходы необходимы.
Вы не опубликовали данные о времени.
Вы описали требование сортировать 700 тыс. Элементов в секунду
на неизвестном оборудовании,
и утверждал, что опубликованный код не способен на это.
В размещенном коде предложены индексы в последовательном (отсортированном) порядке,
что казалось странным, но я воспроизвел этот аспект для сортировки кортежей
в коде ниже.
Вот что я запускаю на ноутбуке Intel Core i7 Mac с частотой 2,9 ГГц:
#! /usr/bin/env python
from time import time
import random
def elapsed(fn):
def print_elapsed(*args, **kw):
t0 = time()
ret = fn(*args, **kw)
print(fn.__name__, '%.3f sec' % (time() - t0))
return ret
return print_elapsed
@elapsed
def get_values(k=2_000_000, base_val=42):
return [dict(index=random.randint(0, 3e6), value=i + base_val + i % 10)
for i in range(k)]
@elapsed
def get_tuples(dicts):
return [(d['index'], d['value'])
for d in dicts]
@elapsed
def get_indices(dicts):
return [d['index']
for d in dicts]
@elapsed
def sort_dicts(dicts):
dicts.sort(key=lambda x: x['index'])
@elapsed
def sort_values(x, reverse=False):
x.sort(reverse=reverse)
if __name__ == '__main__':
dicts = get_values()
sort_dicts(dicts)
tuples = get_tuples(dicts)
sort_values(tuples)
indices = get_indices(dicts)
sort_values(indices)
Выход для 2 M предметов:
get_values 3.307 sec
sort_dicts 2.121 sec
get_tuples 1.355 sec
sort_values 0.414 sec
get_indices 0.715 sec
sort_values 0.329 sec
Уменьшение размера задачи до заявленных вами 20 К пунктов,
get_values 0.034 sec
sort_dicts 0.006 sec
get_tuples 0.005 sec
sort_values 0.001 sec
get_indices 0.002 sec
sort_values 0.001 sec
или даже в десять раз больше 200 K элементов, которые сталкиваются с отсутствием кэша:
get_values 0.325 sec
sort_dicts 0.105 sec
get_tuples 0.111 sec
sort_values 0.027 sec
get_indices 0.064 sec
sort_values 0.021 sec
Трудно понять, как вы могли столкнуться с медлительностью, которую вы описали.
Там должен быть какой-то невидимый аспект проблемы:
вы работаете на медленном процессоре,
или на каком-то уровне кеш целевого хоста маленький,
или ДРАМ медленный,
или есть другой аспект данных, которые вы сортируете, который вы еще не раскрыли нам.
Часть вашего вопроса со списками не видна в опубликованном вами коде.
Вы еще не обратились к таким методам, как Cython или Numba
имеют отношение к вашей бизнес-проблеме.
Может быть, у вас есть техническая проблема "медленной сортировки",
но то, что вы поделились с нами, еще не является доказательством этого.