Python 3: diferencias de orden

domingo, 7 de diciembre de 2008
Otro de los cambios introducidos en Python 3 es la abolición del argumento cmp en la operación de ordenamiento de secuencias. Este argumento permitía especificar una función de comparación para utilizar como criterio de ordenamiento, lo cual era bastante cómodo en muchas situaciones. La función debía seguir el modelo de cmp (la builtin).
>>> cmp(1,2)
-1
>>> cmp(2,1)
1
>>> cmp(1,1)
0
Esto se usa mucho para ordenar según el valor de alguna clave particular en el caso de objetos personalizados.
>>> def cmp_edad(p1, p2):
...     return cmp(p1.edad, p2.edad)
... 
>>> class Persona:
...     def __init__(self, nombre, edad):
...             self.nombre = nombre
...             self.edad = edad
...     def __repr__(self):
...             return "%s (%s años)" % (self.nombre, self.edad)
... 
>>> personas = [Persona('Juan', 15), Persona('Lautaro', 3), Persona('Ifigenio', 73)]
>>> personas
[Juan (15 años), Lautaro (3 años), Ifigenio (73 años)]
>>> personas.sort(cmp=cmp_edad)
>>> personas
[Lautaro (3 años), Juan (15 años), Ifigenio (73 años)]
Python 3 elimina esta posibilidad para forzar en cambio la utilización del argumento key. La diferencia es sutil: el valor de key es una función de un único argumento que devuelve una clave que luego se utilizar para ordenar. Esta técnica se llama DSU (por Decorate, Sort, Undecorate) o transformación de Schwartz. Es realmente meritorio lo de este tipo Schwartz, porque logró ponerle su nombre a algo muy simple en 1994, uniéndose a otros personajes avivados similares (como Bolzano!).

La ventaja está en que la implementación con cmp realiza O(n log n) llamadas a la función de comparación, mientras que usando DSU la clave se evalúa una única vez para cada elemento de la secuencia, lo cual es O(n). Si la función de cálculo de la clave es costosa, esto puede hacer una diferencia apreciable en el rendimiento del algoritmo.

Veamos como quedaría el código anterior:
>>> def key_edad(p):
...     return p.edad
... 
>>> personas.sort(key=key_edad)
>>> personas
[Lautaro (3 años), Juan (15 años), Ifigenio (73 años)]
Hay una cuestión más sutil respecto de porqué se decidió eliminar cmp. No solo la función se ejecuta más veces, sino que además el uso corriente utiliza una función anónima (lambda) para hacerlo. Algo del estilo de:
>>> personas.sort(cmp=lambda x,y: cmp(x.edad, y.edad))
Esto tiene el problema añadido de que, si bien la rutina de sorting está implementada en C, la función de comparación no. Esto implica que cada vez que hace falta comparar dos elementos, hay además que hacer un cambio de contexto a Python con el costo adicional que esto representa. El idiom que utiliza key viene con un aditamento: el módulo operator incluye, a partir de 2.4, las funciones attrgetter y itemgetter. Estas funciones, al estar implementadas en C, son mucho más rápidas que sus contrapartidas en Python. Veamos como quedaría lo anterior utilizando la "forma Python 3":
>>> personas.sort(key=operator.attrgetter('edad'))
De esta forma, todo el ciclo de ordenamiento se ejecuta en C y no se repiten cálculos innecesarios, logrando así ordenar de forma muy eficiente. Hay mucha más información sobre ordenamiento de secuencias en Python (pre-3.0) en el wiki oficial.

En resumen, lo que se hizo fue eliminar una forma popular de ordenar secuencias. Las razones son técnicas además de filosóficas: la variante cmp no solo introduce una decisión a la hora de ordenar (¿qué uso? ¿cmp o key?), sino que una de las opciones produce código naturalmente menos eficiente que la otra.

Benchmark

A pedido del público, una comparación entre la alternativa típica de Python 2 usando cmp con lambda contra la versión de Python 3. En el código de prueba ordeno una larga secuencia de objetos en base al valor de su atributo (entero) i. El código que resulta es el siguiente:
class Pepe:
    def __init__(self, i):
        self.i = i

nums = range(1000000)
random.shuffle(nums)
pepos = map(Pepe, nums)

p1 = pepos[:]
p2 = pepos[:]

t = Timer()

# Version cmp
t.start()
p1.sort(lambda x,y: cmp(x.i, y.i))
print "Version lambda: ",
t.stop()

# Version key
t.start()
p2.sort(key=operator.attrgetter('i'))
print "Version key:    ",
t.stop()
La diferencia es abrumadora, no hay más que ver la salida del programa para una secuencia de 1 millón de elementos:
Version lambda:  21.29 segundos
Version key:     3.78 segundos
La versión key es unas 6 veces más rápida. Solo porque es divertido, les dejo un gráfico que compara la performance de los dos métodos (tiempo en segundos vs. cantidad de objetos a ordenar).

10 comentarios:

Pablo Antonio dijo...

Estaría bueno ver una comparación del comportamiento (algo así como un benchmark) de cmp vs. DSU. Me parece que, como bien decís vos, la diferencia sólo se hace apreciable cuando la función que calcula la clave es muy costosa (en general, suele no serlo tanto).

Pablo Antonio dijo...

BTW, muy graciosa la referencia al señor Bolzano :)

GomoX dijo...

A la orden :)

La diferencia es más importante de lo que yo pensaba!

Pablo Antonio dijo...

Gonzalo, muchas gracias por tomarte el trabajo. Espero que no te moleste, pero se me ocurren un par de preguntas más :)

1. La primera, es sólo de molesto. Entiendo que la última pieza de código la ejecutaste en Python 3. ¿Estás seguro que la llamada a sort pasándole una función anónima (en Python 3) se comporta exactamente igual que el sort de Python 2 pasándole lo mismo en su parámetro "cmp"? En realidad, no veo razón para que esto no sea así, pero qué se yo. Como me queda la duda, te lo pregunto.

2. Cuando decís: "Esto tiene el problema añadido de que, si bien la rutina de sorting está implementada en C, la función de comparación no." ¿A qué función de comparación te referís? ¿A la que uno crea, o a cmp?

3. No es pregunta en realidad. Sólo decirte que no me había quedado del todo claro (ahora sí, porque me fijé usando el intérprete) que el parámetro key de sort también existe en Python 2.

4. ¿Existe la posibilidad de ejecutar (aunque sin usar DSU) en Python 2 todo el ciclo de ordenamieno en C? Se me ocurre esta pregunta porque decís que el módulo operator también está en 2.4.

5. ¿Qué programa usaste para generar el gráfico? Parece gnuplot pero no sé por qué lo veo raro.

Muchas gracias y perdón por quitarte tanto tiempo con mis preguntas :)

GomoX dijo...

Hola Pablo,

No hay drama, me interesa a mí también. Van respuestas ->

1) El código lo ejecuté todo en Python 2.5.2, no podría ejecutarlo en Python 3 porque no soporta más el argumento cmp. No hice la comparación usando cmp en Python 2 y key en Python 3 porque no me pareció "justa" - hay otras diferencias entre Python 2 y 3 que podrían influir. No hay nada que me permita suponer que key se comporta distinto en Python 2 que en Python 3 - ambas versiones son de la misma base de código.

2) La función que uno declara con lambda está hecha en Python, más allá de que luego la función lambda llame a cmp (que está hecho en C). El overhead proviene de llamar una función en Python, cualquiera sea el contenido de esta.

3) En efecto, "key" se agregó en Python 2.4 junto con operator.itemgetter y operator.attrgetter. Entiendo que se agregaron juntos precisamente porque la idea de las funciones es que sean utilizadas en el contexto de list.sort(key=...).

4) Si, en efecto si usás list.sort(key=operator.itemgetter) en Python 2.4+ obtenés el mismo comportamiento (con DSU - ese es el chiste de usar key) que en Python 3. La novedad en Python 3 es que se eliminó la otra opción -list.sort(cmp=...)- que era por lejos más popular.

De todas maneras te cuento que hoy también benchmarkee list.sort(key=...) utilizando la función hecha en Python (un lambda, en lugar de operators.attrgetter) y si bien era más lenta, la diferencia era muy leve (al punto que decidí no incluírla en el gráfico!). Hablo de un 10%, así que por lo visto el overhead no es tan terrible como plantée antes.

5) El gráfico lo hice con el OpenOffice.org Calc, Gnuplot siempre me resultó muy feo. Por lo general uso Matlab pero no lo tengo en la computadora que usé para eso :)


Saludos ;)

Pablo Antonio dijo...

1. ¿Con "[Python 3] no soporta más el argumento cmp" querés decir que ahora no hay manera de crearte una función de comparación? ¿Sí o sí tenés que ingeniártelas para trabajar con algún atributo que te haga de key? Igual, supongo que no tenía mucho sentido tampoco generar las claves al vuelo (ni modificarlas mientras estás ordenando).

En cuanto a lo demás, está todo debidamente aclarado :) De nuevo, muchas gracias por responder.

¡Ah! Quizás te diría que le eches una mirada a Octave (en lugar de usar MATLAB), pero sólo porque me siento un entusiasta del software libre.

GomoX dijo...

1) En efecto en Python 3 se eliminó cmp, lo voy a aclarar en el post si no se entendió.

El tema es que es difícil pensar un caso en que no se pueda convertir la comparación a una clave. Si el orden es consistente (transitivo - si a < b y b < c entonces a < c) entonces se puede armar una clave. Sin embargo, podría no ser demasiado fácil hacerlo. Se discutió largamente el tema en las listas de mail de Python, así que confío en la decisión que se tomó.

Anónimo dijo...

hola no logro ordenar la lista creo que tienes un error
>>> def key_edad(p):
... return p.edad
...
>>> personas.sort(key=key_edad)
>>> personas
[Lautaro (3 años), Juan (15 años), Ifigenio (73 años)]
key_edad tiene un parametro p que luego debajo cuandollamas el metodo no se lo pasas como puede el interprete asumir ese parametro???
yo sigo sin poder ordenar la lista en python 3 por favor si puedes enviame un codigo que funcione a: mfigueroa@estudiantes.uci.cu
saludos

GomoX dijo...

Hola mfigueroa,

El interprete no asume el parámetro, cuando utilizo personas.sort(key=key_edad) no se llama a la función, sino que se pasa a la función key_edad como parámetro de sort.

Esto se llama "funciones de alto orden" (puesto que sus parámetros no son valores, sino funciones). El código a mí me funciona, así que el problema debe estar en otro lado.

Saludos ;)

Anónimo dijo...

Disculpa si la pregunta se sale un poco de tema, pero ¿que modulo usas para medir el tiempo de las funciones? ¿Existe un modulo igual para python3? Gracias por las respuestas

Publicar un comentario