[pyar] Ordenar lista de tuplas

[Ezequiel Trapani]

Si no se si es lo mas simple medir, porque como decís vos depende de la
cantidad de datos. Capas lo medís con una cantidad de datos no
representativa y terminas eligiendo la forma incorrecta. Entendiendo el
funcionamiento podes tener un criterio mejor que te ayude a elegir.

2016-03-15 11:21 GMT-03:00 Fernando Pelliccioni <fpelliccioni en gmail.com>:

> 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
>>
>
> _______________________________________________
> 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/02c40d99/attachment.html>