Python: chức năng cmp_to_key của functools hoạt động như thế nào?

Question

Trong Python, cả hai phương pháp list.sort và sorted hàm dựng sẵn chấp nhận tham số tùy chọn có tên key, là một hàm, được đưa ra một phần tử từ danh sách trả về khóa sắp xếp của nó.

Các phiên bản Python cũ sử dụng phương pháp khác sử dụng thông số cmp thay thế, là hai hàm từ danh sách trả về số âm nếu số đầu tiên nhỏ hơn số thứ hai, bằng không nếu có bằng và dương nếu số đầu tiên lớn hơn. Tại một số điểm, tham số này không được chấp nhận và không được bao gồm trong Python 3.

Ngày khác tôi muốn sắp xếp danh sách các phần tử theo cách mà hàm cmp dễ viết hơn nhiều so với số key. Tôi không muốn sử dụng tính năng không dùng nữa vì vậy tôi đọc tài liệu và tôi thấy rằng có một chức năng có tên là cmp_to_key trong mô-đun functools, như tên của nó, nhận hàm cmp và trả về một key một ... hoặc đó là những gì tôi nghĩ đến khi tôi đọc mã nguồn (hoặc ít nhất là một phiên bản tương đương) của chức năng cao cấp này bao gồm trong 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 

Mặc dù thực tế rằng cmp_to_key công trình như mong đợi, tôi bị bất ngờ trước thực tế rằng đây chức năng không trả về hàm nhưng thay vào đó, lớp K. Tại sao? Làm thế nào nó hoạt động? Tôi đoán rằng hàm sorted kiểm tra nội bộ xem cmp là một hàm hay một lớp K hay cái gì đó tương tự, nhưng tôi không chắc chắn.

P.S .: Bất chấp sự lố bịch của anh ấy, tôi thấy rằng lớp K rất hữu ích. Kiểm tra mã này:

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)): 
    ... 

Bằng cách này, bất kỳ danh sách các trường hợp của MyClass có thể, theo mặc định, được sắp xếp theo các tiêu chí quy định tại my_cmp

Answer 1

Không, sorted chức năng (hoặc list.sort) nội bộ không cần phải kiểm tra xem đối tượng mà nó nhận được là một hàm hay một lớp. Tất cả những gì bạn quan tâm là đối tượng mà nó nhận được trong đối số key phải được gọi và phải trả về một giá trị có thể được so sánh với các giá trị khác khi được gọi.

Lớp học cũng có thể gọi được, khi bạn gọi một lớp, bạn sẽ nhận được thể hiện của lớp đó.

Để trả lời câu hỏi của bạn, đầu tiên chúng ta cần hiểu (ít nhất ở mức độ cơ bản) bao key luận hoạt động -

1. Các key callable được gọi là cho mỗi yếu tố và nó nhận lại đối tượng mà nó nên sắp xếp.

2. Sau khi nhận được đối tượng mới, so sánh đối tượng này với các đối tượng khác (một lần nữa nhận được bằng cách gọi key có thể gọi bằng phần tử othe).

Điều quan trọng cần lưu ý ở đây là số mới object nhận được được so sánh với các đối tượng tương tự khác.

Bây giờ trên mã tương đương, khi bạn tạo một thể hiện của lớp đó, nó có thể được so sánh với các phiên bản khác của cùng một lớp bằng cách sử dụng hàm mycmp của bạn. Và sắp xếp khi sắp xếp các giá trị so sánh các đối tượng này (có hiệu lực) gọi hàm mycmp() của bạn để xác định xem giá trị có nhỏ hơn hoặc lớn hơn đối tượng khác hay không.

Ví dụ với báo cáo in -

>>> 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

Tôi chỉ nhận ra rằng, mặc dù không phải là một chức năng, K lớp học là một cuộc gọi, bởi vì nó là một lớp học! và các lớp là các callables, khi được gọi, tạo một cá thể mới, khởi tạo nó bằng cách gọi __init__ tương ứng và sau đó trả về cá thể đó.

Cách này hoạt động như một hàm key vì K nhận đối tượng khi được gọi và kết thúc đối tượng này trong phiên bản K, có thể so sánh với các phiên bản K khác.

Sửa lỗi nếu tôi sai. Tôi cảm thấy tôi đang đi vào, không quen thuộc với tôi, lãnh thổ siêu lớp.

Answer 3

Tôi không nhìn vào nguồn, nhưng tôi tin rằng kết quả của các chức năng quan trọng cũng có thể là bất cứ điều gì, và do đó cũng là một đối tượng có thể so sánh. Và cmp_to_key chỉ tạo mặt nạ cho các đối tượng K đó, so với các đối tượng khác trong khi sắp xếp công việc của nó.

Nếu tôi cố gắng để tạo ra một sắp xếp trên các bộ phận và đảo ngược số phòng như thế này:

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)] 

Đó không phải là những gì tôi muốn, và tôi nghĩ rằng loại chỉ ổn định trên mỗi cuộc gọi, documentation được gây hiểu lầm imo:

Phương thức sắp xếp() được đảm bảo ổn định. Một sắp xếp ổn định nếu nó đảm bảo không thay đổi thứ tự tương đối của các phần tử so sánh bằng nhau - điều này rất hữu ích cho việc sắp xếp theo nhiều lần (ví dụ, sắp xếp theo bộ phận, rồi theo cấp lương).

Cách tiếp cận kiểu cũ làm việc vì mỗi kết quả gọi lớp K trả về một trường hợp K và so sánh kết quả của 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)] 

Đây là một khác biệt quan trọng, mà người ta không thể làm nhiều đèo chỉ ngoài cái hộp. Các giá trị/kết quả của hàm quan trọng phải được sắp xếp tương đối theo thứ tự, không phải là các phần tử cần sắp xếp. Do đó là mặt nạ cmp_to_key: tạo ra những đối tượng có thể so sánh mà chúng ta cần để sắp xếp chúng.

Hy vọng điều đó sẽ hữu ích. và cảm ơn thông tin chi tiết về mã cmp_to_key, cũng giúp tôi rất nhiều :)