python algorithm sorting cmp python-internals

python 3 reduce



¿Cómo funciona la función cmp_to_key de Python? (1)

El método cmp_to_key devuelve un objeto especial que actúa como una clave sustituta:

class K(object): __slots__ = [''obj''] def __init__(self, obj, *args): self.obj = obj def __lt__(self, other): return mycmp(self.obj, other.obj) < 0 def __gt__(self, other): return mycmp(self.obj, other.obj) > 0 def __eq__(self, other): return mycmp(self.obj, other.obj) == 0 def __le__(self, other): return mycmp(self.obj, other.obj) <= 0 def __ge__(self, other): return mycmp(self.obj, other.obj) >= 0 def __ne__(self, other): return mycmp(self.obj, other.obj) != 0 def __hash__(self): raise TypeError(''hash not implemented'')

Al ordenar, cada tecla se comparará con la mayoría de las otras teclas en la secuencia. ¿Este elemento en la posición 0 es menor o mayor que el otro objeto?

Cuando esto sucede, se invocan los métodos de los métodos especiales, por __lt__ se llama a __lt__ o __gt__ , y la clave sustituta se convierte en una llamada al método cmp .

Así que la lista [1, 2, 3] se clasifica como [K(1), K(2), K(3)] , y si, por ejemplo, K(1) se compara con K(2) para ver si K(1) es más bajo, luego se llama K(1).__lt__(K(2)) , que se traduce a mycmp(1, 2) < 0 .

Así es como funcionaba el viejo método cmp todos modos ; devuelve -1, 0 o 1 dependiendo de si el primer argumento es menor que, igual o mayor que el segundo argumento. La clave sustituta traduce esos números nuevamente a valores booleanos para los operadores de comparación.

En ningún momento la clave sustituta necesita saber nada sobre las posiciones absolutas . Solo necesita saber acerca de otro objeto con el que se está comparando, y los métodos especiales proporcionan ese otro objeto.

Me encontré con esta función here .

Estoy desconcertado sobre cómo se implementaría esto. ¿Cómo sabe la función key generada por cmp_to_key qué "posición" debe tener un elemento dado sin verificar cómo se compara el elemento dado con todos los demás elementos de interés?