Сортировать список по вложенным значениям кортежа

Question

Есть ли лучший способ сортировки списка по вложенным значениям кортежа, чем написание альтернативы itemgetter, которая извлекает значение вложенного кортежа:

def deep_get(*idx):
  def g(t):
      for i in idx: t = t[i]
      return t
  return g

>>> l = [((2,1), 1),((1,3), 1),((3,6), 1),((4,5), 2)]
>>> sorted(l, key=deep_get(0,0))
[((1, 3), 1), ((2, 1), 1), ((3, 6), 1), ((4, 5), 2)]
>>> sorted(l, key=deep_get(0,1))
[((2, 1), 1), ((1, 3), 1), ((4, 5), 2), ((3, 6), 1)]

Я думал об использовании compose, но это не стандартнобиблиотека:

sorted(l, key=compose(itemgetter(1), itemgetter(0))

Есть ли что-то, что я пропустил в библиотеках, чтобы сделать этот код приятнее?

Реализация должна разумно работать с элементами из 100 тыс.

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

Answer 1

Да, вы можете просто использовать key=lambda x: x[0][1]

Answer 2

Ваш подход довольно хорош, учитывая имеющуюся у вас структуру данных.

Другой подход заключается в использовании другой структуры.

Если вам нужна скорость, то вам нужен стандарт де-фактора NumPy . Его задача - эффективно обрабатывать большие массивы. У него даже есть несколько хороших процедур сортировки для таких массивов, как ваш. Вот как вы бы записали свой вид по счетам, а затем по (a, b):

>>> arr = numpy.array([((2,1), 1),((1,3), 1),((3,6), 1),((4,5), 2)],
                  dtype=[('pos', [('a', int), ('b', int)]), ('count', int)])
>>> print numpy.sort(arr, order=['count', 'pos'])
[((1, 3), 1) ((2, 1), 1) ((3, 6), 1) ((4, 5), 2)]

Это очень быстро (реализовано в C).

Если вы хотите придерживаться стандартного Python, список, содержащий (count, a, b) кортежи, будет автоматически отсортирован так, как вы хотите в Python (который использует лексикографический порядок на кортежах).

Answer 3

Это может быть немного более быстрый вариант вашего подхода:

l = [((2,1), 1), ((1,3), 1), ((3,6), 1), ((4,5), 2)]

def deep_get(*idx):
    def g(t):
        return reduce(lambda t, i: t[i], idx, t)
    return g

>>> sorted(l, key=deep_get(0,1))
[((2, 1), 1), ((1, 3), 1), ((4, 5), 2), ((3, 6), 1)]

Что может быть сокращено до:

def deep_get(*idx):
    return lambda t: reduce(lambda t, i: t[i], idx, t)

или даже просто выписано:

sorted(l, key=lambda t: reduce(lambda t, i: t[i], (0,1), t))

Answer 4

Я сравнил два похожих решения. Первый использует простую лямбду:

def sort_one(d):
    result = d.items()
    result.sort(key=lambda x: (-x[1], x[0]))
    return result

Обратите внимание на минус на x[1], потому что вы хотите, чтобы сортировка сортировалась по убыванию.

Второй использует тот факт, что sort в Python является стабильным. Сначала мы сортируем по (a, b) (по возрастанию). Затем сортируем по количеству по убыванию:

def sort_two(d):
    result = d.items()
    result.sort()
    result.sort(key=itemgetter(1), reverse=True)
    return result

Первый - на 10-20% быстрее (как для небольших, так и для больших наборов данных), и оба выполняются менее чем за 0,5 секунды на моем Q6600 (используется одно ядро) для 100 тыс. Элементов. Таким образом, избегание создания кортежей, кажется, не очень помогает.