Python: come funziona la funzione cmp_to_key di functools?

Question

In Python, sia il metodo list.sort che la funzione integrata sorted accettano un parametro opzionale denominato key, che è una funzione che, dato un elemento dall'elenco restituisce la sua chiave di ordinamento.

Le versioni precedenti di Python utilizzavano un approccio diverso utilizzando invece il parametro cmp, che è una funzione che, dati due elementi dall'elenco restituisce un numero negativo se il primo è inferiore al secondo, zero se ci sono uguali e positivo numero se il primo è maggiore. Ad un certo punto, questo parametro era deprecato e non era incluso in Python 3.

L'altro giorno volevo ordinare un elenco di elementi in modo che una funzione cmp fosse molto più semplice da scrivere rispetto a uno key. Non volevo utilizzare una funzionalità deprecata, quindi ho letto la documentazione e ho scoperto che esiste una funzione denominata cmp_to_key nel modulo functools che, come afferma il suo nome, riceve una funzione cmp e restituisce uno key ... o quello è quello che ho pensato fino a quando ho letto il codice sorgente (o almeno una versione equivalente) di questa funzione di alto livello incluso nel docs

def cmp_to_key(mycmp): 
    'Convert a cmp= function into a key= function' 
    class K(object): 
     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 
    return K 

Nonostante il fatto che cmp_to_key opere come previsto, ottengo sorpreso dal fatto che questo la funtion non restituisce una funzione, ma una classe K. Perché? Come funziona? Suppongo che la funzione sorted controlli internamente se cmp è una funzione o una classe K o qualcosa di simile, ma non ne sono sicuro.

P.S .: Nonostante la sua unicità, ho trovato che la classe K è molto utile. Controllare questo codice:

from functools import cmp_to_key 

def my_cmp(a, b): 
    # some sorting comparison which is hard to express using a key function 

class MyClass(cmp_to_key(my_cmp)): 
    ... 

In questo modo, qualsiasi elenco di istanze di MyClass può essere, per impostazione predefinita, ordinato secondo i criteri definiti nel my_cmp

Answer 1

No, sorted funzione (o list.sort) internamente non è necessario controllare se l'oggetto ricevuto è una funzione o una classe. Tutto ciò che importa è che l'oggetto ricevuto nell'argomento key deve essere richiamabile e deve restituire un valore che può essere confrontato con altri valori quando viene chiamato.

Le classi sono anche chiamabili, quando si chiama una classe, si riceve l'istanza di quel corso.

Per rispondere alla tua domanda, in primo luogo abbiamo bisogno di capire (almeno a livello di base) come funziona key argomento -

1. Il key callable è chiamato per ogni elemento e riceve indietro l'oggetto con il quale dovrebbe ordinare

2. Dopo aver ricevuto il nuovo oggetto, esso confronta questo ad altri oggetti (nuovamente ricevuti chiamando il key richiamabile con l'elemento othe).

Ora la cosa importante da notare qui è che il nuovo object ricevuto viene confrontato con altri oggetti stessi.

Ora sul codice equivalente, quando si crea un'istanza di tale classe, può essere confrontata con altre istanze della stessa classe utilizzando la funzione mycmp. E ordina quando l'ordinamento dei valori confronta questi oggetti (in effetti) chiamando la tua funzione mycmp() per determinare se il valore è minore o maggiore rispetto all'altro oggetto.

Esempio con dichiarazioni di stampa -

>>> def cmp_to_key(mycmp): 
...  'Convert a cmp= function into a key= function' 
...  class K(object): 
...   def __init__(self, obj, *args): 
...    print('obj created with ',obj) 
...    self.obj = obj 
...   def __lt__(self, other): 
...    print('comparing less than ',self.obj) 
...    return mycmp(self.obj, other.obj) < 0 
...   def __gt__(self, other): 
...    print('comparing greter than ',self.obj) 
...    return mycmp(self.obj, other.obj) > 0 
...   def __eq__(self, other): 
...    print('comparing equal to ',self.obj) 
...    return mycmp(self.obj, other.obj) == 0 
...   def __le__(self, other): 
...    print('comparing less than equal ',self.obj) 
...    return mycmp(self.obj, other.obj) <= 0 
...   def __ge__(self, other): 
...    print('comparing greater than equal',self.obj) 
...    return mycmp(self.obj, other.obj) >= 0 
...   def __ne__(self, other): 
...    print('comparing not equal ',self.obj) 
...    return mycmp(self.obj, other.obj) != 0 
...  return K 
... 
>>> def mycmp(a, b): 
...  print("In Mycmp for", a, ' ', b) 
...  if a < b: 
...   return -1 
...  elif a > b: 
...   return 1 
...  return 0 
... 
>>> print(sorted([3,4,2,5],key=cmp_to_key(mycmp))) 
obj created with 3 
obj created with 4 
obj created with 2 
obj created with 5 
comparing less than 4 
In Mycmp for 4 3 
comparing less than 2 
In Mycmp for 2 4 
comparing less than 2 
In Mycmp for 2 4 
comparing less than 2 
In Mycmp for 2 3 
comparing less than 5 
In Mycmp for 5 3 
comparing less than 5 
In Mycmp for 5 4 
[2, 3, 4, 5] 

Answer 2

ho capito che, pur non essendo una funzione, il K la classe è un callable, perché è una classe! e le classi sono callables che, quando chiamato, crea una nuova istanza, inizializza chiamando il corrispondente __init__ e quindi restituisce quell'istanza.

In questo modo si comporta come una funzione key perché K riceve l'oggetto quando viene chiamato e avvolge questo oggetto in un'istanza K, che può essere confrontato con altre istanze K.

Correggimi se sbaglio. Sento che mi sto avvicinando al territorio che non conosco, meta-classi.

Answer 3

Non ho guardato nella sorgente, ma credo che il risultato della funzione chiave può anche essere qualsiasi cosa, e quindi anche un oggetto simile. E cmp_to_key maschera solo la creazione di quegli oggetti K, che sono confrontati l'uno con l'altro mentre sort fa il suo lavoro.

se cerco di creare una sorta su reparti e invertire i numeri di stanza in questo modo:

departments_and_rooms = [('a', 1), ('a', 3),('b', 2)] 
departments_and_rooms.sort(key=lambda vs: vs[0]) 
departments_and_rooms.sort(key=lambda vs: vs[1], reverse=True) 
departments_and_rooms # is now [('a', 3), ('b', 2), ('a', 1)] 

Questo non è quello che voglio, e penso sorta è stabile solo per ogni chiamata, il documentation è fuorviante imo:

Il metodo sort() è garantito come stabile. Un ordinamento è stabile se garantisce di non modificare l'ordine relativo di elementi che si equivalgono - questo è utile per l'ordinamento in più passaggi (ad esempio, ordina per dipartimento, quindi per grado di stipendio).

L'approccio vecchio stile funziona perché ogni risultato chiamando la classe K restituisce un'istanza K e mette a confronto i risultati di mycmp:

def mycmp(a, b):        
    return cmp((a[0], -a[1]), (b[0], -b[1])) 

departments_and_rooms = [('a', 1), ('a', 3),('b', 2)] 
departments_and_rooms.sort(key=cmp_to_key(mycmp)) 
departments_and_rooms # is now [('a', 3), ('a', 1), ('b', 2)] 

E 'una differenza importante, che non si può fare più passaggi solo fuori dalla scatola. I valori/risultati della funzione chiave devono essere ordinabili relativi in ​​ordine, non gli elementi da ordinare. Quindi la maschera cmp_to_key: crea quegli oggetti comparabili che è necessario ordinarli.

Spero che questo aiuti. e grazie per la comprensione del codice cmp_to_key, mi ha aiutato molto anche :)