Подтвердить что ты не робот

Python: как работает функция cmp_to_key functools?

В Python, как list.sort метод и sorted встроенная функция принимает необязательный параметр с именем key, который является функцией, которая, учитывая элемент из списка возвращает его сортировки ключ.

В старых версиях Python использовался другой подход, в котором вместо этого использовался параметр cmp, который представляет собой функцию, которая, учитывая, что два элемента из списка возвращают отрицательное число, если первое меньше второго, и ноль, если есть равные, и положительное число, если первое лучше. В какой-то момент этот параметр устарел и не был включен в Python 3.

На днях я хотел отсортировать список элементов таким образом, чтобы функция cmp была гораздо проще написать, чем key. Я не хотел использовать устаревшую функцию, так что я прочитал документацию, и я обнаружил, что есть Funtion имени cmp_to_key в functools модуле, который, как и его название состояния, получает cmp функцию и возвращает key один... или что что я думал, пока не прочитал исходный код (или хотя бы эквивалентную версию) этой функции высокого уровня, включенной в документы

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

Несмотря на то, что cmp_to_key работает, как и ожидалось, меня удивляет тот факт, что эта функция возвращает не функцию, а класс K Зачем? Как это работает? Я предполагаю, что sorted функция внутренне проверяет, является ли cmp функцией, или классом K, или чем-то подобным, но я не уверен.

PS: Несмотря на эту странность, я обнаружил, что класс K очень полезен. Проверьте этот код:

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

Таким образом, любой список экземпляров MyClass может быть по умолчанию отсортирован по критериям, определенным в my_cmp

4b9b3361

ОТВЕТЫ

Ответ 1

Нет, функция sorted (или list.sort) внутренне не нуждается в проверке, является ли объект, который он получил, функцией или классом. Все, о чем он заботится, состоит в том, что объект, который он получил в аргументе key, должен быть вызываемым и должен возвращать значение, которое можно сравнить с другими значениями при вызове.

Классы также могут быть вызваны, когда вы вызываете класс, вы получаете экземпляр этого класса.

Чтобы ответить на ваш вопрос, сначала нам нужно понять (по крайней мере на базовом уровне), как работает аргумент key -

  • Вызывается key вызываемый для каждого элемента, и он получает обратно объект, с которым он должен сортироваться.

  • После получения нового объекта он сравнивает это с другими объектами (снова получен путем вызова key, вызываемого с помощью элемента othe).

Теперь важно отметить, что полученный новый object сравнивается с другими теми же объектами.

Теперь, когда вы создаете экземпляр этого класса, ваш эквивалентный код можно сравнить с другими экземплярами того же класса, используя вашу функцию mycmp. И сортировка при сортировке значений сравнивает эти объекты (in-effect), вызывающие вашу функцию mycmp(), чтобы определить, меньше или больше значения, чем другой объект.

Пример с инструкциями печати -

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

Ответ 2

Я просто понял, что, не будучи функцией, класс K является вызываемым, потому что это класс! и классы являются вызывающими, которые при вызове создают новый экземпляр, инициализируя его, вызывая соответствующий __init__, а затем возвращает этот экземпляр.

Таким образом, он ведет себя как функция key, потому что K получает объект при вызове и обертывает этот объект в экземпляр K, который можно сравнить с другими экземплярами K.

Исправьте меня, если я ошибаюсь. Я чувствую, что попадаю в незнакомую мне, метаклассическую территорию.

Ответ 3

Я не смотрел в источник, но я считаю, что результатом ключевой функции может быть и все, и, следовательно, также сопоставимый объект. И cmp_to_key просто маскирует создание тех объектов K, которые чем-то сравниваются друг с другом, а сортировка выполняет свою работу.

Если я попытаюсь создать сортировку по разделам и изменить номера комнат в таком виде:

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

Это не то, что я хочу, и я думаю, что сортировка только стабильна при каждом вызове, документация вводит в заблуждение imo:

Метод sort() гарантированно будет стабильным. Сорт стабилен, если он не позволяет изменить относительный порядок элементов, которые сравниваются равными - это полезно для сортировки в несколько проходов (например, сортировка по отделам, затем по классу зарплаты).

Метод старого стиля работает, потому что каждый результат, вызывающий класс K, возвращает экземпляр K и сравнивается с результатами 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)]

Это важная разница, что нельзя делать несколько проходов только из коробки. Значения/результаты ключевой функции должны сортироваться относительно по порядку, а не сортировать элементы. Следовательно, это маску cmp_to_key: создайте сопоставимые объекты, которые нужно упорядочить.

Надеюсь, что это поможет. и спасибо за понимание кода cmp_to_key, также помогли мне:)