[pyar] Ordenar lista de tuplas

[Fernando Pelliccioni]

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