Ordenar la lista por tupla anidada valora

Question

¿Hay una mejor manera de ordenar una lista por un valor de tuplas anidadas que escribir una alternativa itemgetter que extrae el valor tupla anidada:

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)] 

pensé acerca del uso de componer, pero eso es no en la biblioteca estándar:

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

¿hay algo que había perdido en las librerias que haría que el código más bonito?

La implementación debería funcionar razonablemente con 100k elementos.

Contexto: me gustaría ordenar un diccionario de elementos que son un histograma. Las claves son una tupla (a, b) y el valor es el recuento. Al final, los elementos se deben ordenar por conteo descendente, a y b. Una alternativa es aplanar la tupla y usar el elemento selector directamente, pero de esta manera se generarán muchas tuplas.

Answer 1

Sí, es posible que utilices una key=lambda x: x[0][1]

Answer 2

Su enfoque es bastante bueno, teniendo en cuenta la estructura de datos que tiene.

Otro enfoque sería usar otra estructura.

Si desea velocidad, el factor NumPy es el camino a seguir. Su trabajo es manejar eficientemente grandes matrices. Incluso tiene algunas buenas rutinas de clasificación para matrices como la tuya. Así es como se escribiría su tipo en los conteos, y luego sobre (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)] 

Esto es muy rápido (que está implementado en C).

Si quiere seguir con Python estándar, una lista que contenga (contar, a, b) tuplas se ordenaría automáticamente de la manera que desee Python (que usa orden lexicográfico en tuplas).

Answer 3

He comparado dos soluciones similares. El primero utiliza un lambda simple:

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

Nota al menos en x[1], porque desea que la especie que se va descendiendo en el recuento.

El segundo se aprovecha del hecho de que sort en Python es estable. Primero, ordenamos por (a, b) (ascendente). Luego ordenar por conteo, descendente:

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

El primero es del 10-20% más rápido (tanto en las pequeñas y grandes conjuntos de datos), y ambos completo bajo 0.5 segundos en mi Q6600 (un núcleo utilizado) por 100 mil artículos . Así que evitar la creación de tuplas no parece ayudar mucho.

Answer 4

Esto podría ser un poco versión más rápida de su enfoque:

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)] 

que podría ser acortado a:

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

o incluso simplemente por escrito de salida:

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