[pyar] Ordenar lista de tuplas

[Fernando Pelliccioni]

Perdón por lo complicado.

Justamente porque es complicado lo más simple es medir (ya lo habrás
escuchando mil veces)

Saludos.
On Mar 15, 2016 09:37, "Ezequiel Trapani" <etrapani04 en gmail.com> wrote:

> 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
>
> _______________________________________________
> 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
>
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://listas.python.org.ar/pipermail/pyar/attachments/20160315/de1c32d4/attachment-0001.html>