[pyar] Ordenar lista de tuplas

[Ezequiel Trapani]

Buenísimo tu aporte, un poco complicado de entender pero es una cosa
importante a tener en cuenta cuando necesitamos ordenar.

2016-03-14 18:07 GMT-03:00 Fernando Pelliccioni <fpelliccioni en gmail.com>:

> Me gustaría hacer algunos comentarios al respeto:
>
> En Python2 se puede usar tanto la "función de comparación" o la "función
> de extracción del key".
> La documentación dice que en general "cmp" es más costosa que "key". Sí,
> en *general*, lo que significa que no siempre es más costoso usar cmp que
> key.
> (https://docs.python.org/2/library/functions.html#sorted)
>
> (A) ¿Qué implica usar cmp? (En Python2):
> (Siendo N el tamaño de la secuencia (list, array, etc...) a ordenarse.)
>
> 1. Ejecución el algoritmo de ordenamiento propiamente dicho. (variante de
> Mergesort)
> Se realizarán aproximadamente N*log(N) comparaciones de la siguiente forma:
> cmp(b, a) < 0       (para saber si *b* es menor que *a*)
>
> ** cmp puede programarse para realizar una comparación "compleja". Con
> compleja me refiero a que se pueden comparar, por ejemplo, más de un campo
> con distintos ordenamientos.
>
> (B) ¿Qué implica usar key? (En Python2, *1):
> 1. key va a invocarse exactamente N veces. Una vez para cada uno de los N
> elementos de la secuencia original. (A cada elemento de la secuencia
> original lo voy a llamar E)
> Ki = key_function(Ei)
>
> 2. Se "alocan" dinámicamente N objetos K (yo los denomino K, de Key) para
> almacenar el resultado de la ejecución de la key-function para cada uno de
> los N elementos de la secuencia original.
> El tamaño de cada objeto K depende de la key-function que nosotros
> definimos.
> Los objetos K no necesariamente están almacenados contiguamente en memoria.
>
> 3. Se "alocan" dinámicamente N objetos P (de Pair).
> Cada objeto P es un par de punteros (más el header de cada objeto Python)
> a los objetos K y E anteriores.
> Cada objeto P tiene un tamaño de 32 bytes en máquinas de 64-bits.
>    Los objetos P no necesariamente están almacenados contiguamente en
> memoria.
>
> 4. Ejecución el algoritmo de ordenamiento propiamente dicho...
> Se realizarán aproximadamente N*log(N) comparaciones de la siguiente forma:
> Kb < Ka       (Dónde Ka y Kb son los Keys asociados a los elementos Ea y
> Eb)
> Luego de este paso queda ordenada la lista de objetos P.
>
> 5. Se re-genera la lista a partir de la lista de objetos P.
>
> 6. Se destruyen/liberan los objetos K y P.
>
> ** Para poder realizar un ordenamiento "complejo", es necesario ejecutar
> varias veces la función sorted (o list.sort), utilizando diferentes key
> functions en cada ejecución.
>
>
> Si uno lee esto debería pensar: "Entonces usar key es mucho más lento que
> cmp". No siempre.
> Entonces, ¿Cuál es más lento?.
>
> Eso depende de:
> 1. Cuán complejo es nuestro criterio de ordenamiento.
> 2. El tamaño de nuestra secuencia, N.
>
> Para N chicos y criterios simples, key es más rápido que cmp. Cuando N va
> creciendo o la complejidad del criterio de ordenamiento aumenta, cmp tiende
> a ser más rápido que key.
> Así que comparto con la documentación de Python, *en general*, key es más
> rápido que cmp. PERO.... para cada caso en particular les recomiendo
> **medir** ambas variantes.
>
> La otra pregunta que debería surgir es:
> Dada la complejidad de (B) en comparación a (A). ¿Por qué key es más
> rápido usar key que cmp?
>
> Porque en Python, lo que sí es muy costoso es el llamado a funciones y por
> sobre todo, es costosísimo el llamado a Function-Objects (funciones pasadas
> como parámetro a otras funciones, como cmp y key). Es tan costoso el
> llamado a Function-Objects que **supongo** que tuvieron que crear esta
> optimización de las key-function. (Es costoso en comparación a otros
> lenguajes, específicamente, lenguajes compilados).
>
> Aclaración 1: En lenguajes compilados, donde el optimizing-compiler puede
> hacer inlining de los function-objects, no tendría sentido usar algo como
> las key-functions, ya que la ejecución de las funciones "cmp" no tiene un
> overhead asociado como lo hay en Python.
>
> Aclaración 2: Más allá de todo este análisis, el uso de funciones de
> comparación "cmp" como lo había en Python2 o lo hay en Java o .Net me
> parece pobre en comparación al uso de total/weak-order-relations.
>
> Aclaración 3: Me refiero siempre a CPython (La implementación canónica y
> más popular de Python¿?) No tengo idea si todo esto es cierto en otras
> implementaciones.
>
> Se abre el debate :)
>
> Saludos,
> Fernando.
>
> *1: En Python3 optimizan un poco este algoritmo, pero en general, es
> bastante similar. Igual, no hay chance de usar cmp en Python3.
>
>
> 2016-03-02 18:28 GMT-03:00 Carlos Matías <cmdelatorre en gmail.com>:
>
>> ---------- Forwarded message ----------
>>> From: Facundo Batista <facundobatista en gmail.com>
>>> To: Python Argentina <pyar en python.org.ar>
>>> Cc:
>>> Date: Wed, 2 Mar 2016 11:47:57 -0300
>>> Subject: Re: [pyar] Ordenar lista de tuplas
>>> 2016-02-28 13:45 GMT-03:00 Ezequiel Trapani <etrapani04 en gmail.com>:
>>>
>>> > import operator
>>> > d = sorted(result, key = operator.itemgetter(0), reverse=True)
>>> > s = sorted(d, key = operator.itemgetter(1))
>>> >
>>> > no se si es muy eficiente pero funciono. Interesante lo de definir la
>>> función de comparación del método sort, para tenerlo en cuenta.
>>>
>>> Lo que hiciste está perfecto.
>>>
>>> Pero NO hay que tener en cuenta "la función de comparación" del sort,
>>> o sea "cmp". La "cmp" es vieja, está deprecada (no está en Py3), y
>>> además es CARISIMA.
>>>
>>> ¿Por qué es carísima? Porque llama a la función cada vez que tiene que
>>> comparar dos elementos, lo cual puede suceder infinidad de veces. En
>>> cambio, la función que vos le pasás al "key" se llama *solamente* una
>>> vez por cada elemento de lo que tiene que ordenar.
>>>
>>
>> ¡Este es el tipo de conocimiento por el que vale la pena estar en la
>> lista!
>>  (y muchas otras cosas, está claro. Trolls abstenerse.)
>>
>> --
>> Carlos Matías
>>
>> _______________________________________________
>> pyar mailing list pyar en python.org.ar
>> http://listas.python.org.ar/listinfo/pyar
>>
>> PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
>>
>> La lista de PyAr esta Hosteada en USLA - Usuarios de Software Libre de
>> Argentina - http://www.usla.org.ar
>>
>
>
> _______________________________________________
> pyar mailing list pyar en python.org.ar
> http://listas.python.org.ar/listinfo/pyar
>
> PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
>
> La lista de PyAr esta Hosteada en USLA - Usuarios de Software Libre de
> Argentina - http://www.usla.org.ar
>



-- 
Ezequiel Trapani
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://listas.python.org.ar/pipermail/pyar/attachments/20160315/ee7afd4b/attachment.html>