Лучший способ отсортировать 1M записывает в Python

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

Однако, похоже, в Python нет ни одной из них. Я не могу этого объяснить; это основной, фундаментальный тип данных на любом языке. Python dict и set - это неупорядоченные контейнеры, которые сопоставляются с базовой структурой данных хеш-таблицы. Он обязательно должен иметь оптимизированную древовидную структуру данных; Если у кого-то есть хорошо оптимизированная структура данных, подобная этой для Python, я бы хотел узнать об этом. (Не все операции хорошо подходят для модели данных Python; например, чтобы получить следующее / предыдущее значение из другого значения, вам нужна ссылка на узел, а не само значение.)

Если у вас есть фиксированное количество полей, используйте кортежи вместо словарей. Поместите поле, которое вы хотите отсортировать, на первую позицию и просто используйте mylist.sort ()

Кажется, это довольно быстро.

raw= [ {'id':'id1', 'hits':200, 'misses':300, 'total':400},
    {'id':'id2', 'hits':300, 'misses':100, 'total':500},
    {'id':'id3', 'hits':100, 'misses':400, 'total':600}
]

hits= [ (r['hits'],r['id']) for r in raw ]
hits.sort()

misses = [ (r['misses'],r['id']) for r in raw ]
misses.sort()

total = [ (r['total'],r['id']) for r in raw ]
total.sort()

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

Вместо того, чтобы пытаться поддерживать порядок в списке, возможно, вам удастся обойтись очередью из кучи. Он позволяет нажимать любой элемент, сохраняя «самый маленький» на h [0] , и выскакивать этот элемент (и «всплывать» следующий самый маленький) имеет значение O (nlogn)

Итак, просто спросите себя:

• нужно ли мне упорядочивать весь список постоянно? : использовать упорядоченную структуру (например, пакет Zope BTree, как упоминал Элдвульф)

• или весь список упорядочен, но только после дневной работы случайных вставок ?: использовать сортировку, как вы делаете, или например ответ С.Лотта

• или несколько «самых маленьких» элементов в любой момент? : use heapq

Другие дали отличные советы, попробуйте их.

В качестве общего совета в подобных ситуациях вам необходимо профилировать свой код. Точно знайте, где вы проводите большую часть времени. Узкие места хорошо скрываются в местах, о которых вы меньше всего ожидаете.
Если требуется много вычислений, то JIT-компилятор, такой как (ныне мертвый) psyco, также может помочь. Когда обработка занимает минуты или часы, действительно имеет значение двукратное ускорение.

• http://docs.python.org/library/profile.html
• http://www.vrplumber.com/programming/runsnakerun/
• http://psyco.sourceforge.net/

sorted(myLists[key], key=mylists[key].get, reverse=True)

должно сэкономить вам время, хотя и немного.

Я бы посмотрел на использование другого алгоритма сортировки. Что-то вроде сортировки слиянием может сработать. Разбейте список на более мелкие списки и отсортируйте их по отдельности. Затем выполните цикл.

Псевдокод:

list1 = []  // sorted separately
list2 = []  // sorted separately

// Recombine sorted lists
result = []
while (list1.hasMoreElements || list2.hasMoreElements):
   if (! list1.hasMoreElements):
       result.addAll(list2)
       break
   elseif (! list2.hasMoreElements):
       result.AddAll(list1)
       break

   if (list1.peek < list2.peek):
      result.add(list1.pop)
   else:
      result.add(list2.pop)

Гленн Мейнард прав, что здесь уместно отсортированное отображение . Это для питона: http://wiki.zope.org/ZODB/guide/node6.html#SECTION000630000000000000000

Честно говоря, лучший способ - не использовать Python. Если для этого важна производительность, используйте более быстрый язык.

Я быстро проанализировал как исходный способ, так и предложение Слотта. Ни в том, ни в другом случае на каждое поле не требуется 5-10 минут. Собственно сортировка не проблема. Похоже, что большую часть времени уходит на переброску данных и их преобразование. Кроме того, использование моей памяти стремительно растет - мой питон занимает более 350 мегабайт оперативной памяти! Вы уверены, что не израсходовали всю свою оперативную память и подкачку на диск? Даже с моим паршивым 3-летним ноутбуком с энергосберегающим процессором я вижу результаты менее 5-10 минут на ключ, отсортированный для миллиона элементов. Что я не могу объяснить, так это вариативность фактических вызовов sort (). Я знаю, что сортировка python отлично подходит для сортировки частично отсортированных списков, поэтому, возможно, его список частично отсортирован при преобразовании необработанных данных в список для сортировки.

Вот результаты для метода слотта:

done creating data
done transform.  elapsed: 16.5160000324
sorting one key slott's way takes 1.29699993134

вот код для получения этих результатов:

starttransform = time.time()
hits= [ (r['hits'],r['id']) for r in myList ]
endtransform = time.time()
print "done transform.  elapsed: " + str(endtransform - starttransform)
hits.sort()
endslottsort = time.time()
print "sorting one key slott's way takes " + str(endslottsort - endtransform)

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

done creating data
done transform.  elapsed: 8.125
about to get stuff to be sorted 
done getting data. elapsed time: 37.5939998627
about to sort key hits
done  sorting on key <hits> elapsed time: 5.54699993134

Вот код:

for k, v in myLists.iteritems():
    time1 = time.time()
    print "about to get stuff to be sorted "
    tobesorted = myLists[k].items()
    time2 = time.time()
    print "done getting data. elapsed time: " + str(time2-time1)
    print "about to sort key " + str(k) 
    mysorted[k] = tobesorted.sort( key=itemgetter(1))
    time3 = time.time()
    print "done  sorting on key <" + str(k) + "> elapsed time: " + str(time3-time2)