Python에서sorted 비교 논리 사용자 정의 방법

Python에서 교체 가능한 대상을 정렬하는 것은 흔한 작업입니다. 일반적으로sorted () 함수를 사용합니다.

num_list = [4, 2, 8, -9, 1, -3]
sorted_num_list = sorted(num_list)
print(sorted_num_list)

위의 코드는 정수 목록num_list는 작은 것부터 큰 것까지 순서대로 정렬하여 얻은 결과는 다음과 같다

[-9, -3, 1, 2, 4, 8]

때때로 원소 자체를 정렬하는 것이 아니라 원소 값을 토대로 계산한 후에 비교한다. 예를 들어num_를목록의 요소는 제곱값의 크기에 따라 정렬됩니다.
Python 2에서sorted () 함수의 cmp나 키 파라미터를 통해 이러한 사용자 정의 비교 논리를 실현할 수 있습니다.cmp 비교 함수는 두 개의 매개 변수 x와 y(x와 y는 모두 목록에 있는 요소)를 수신하고 한 숫자를 되돌려줍니다. 만약에 정수 x > y를 되돌려주면 0 x = = y를 되돌려주고 음수 x < y를 되돌려줍니다.키 함수는 매개 변수를 수신하여 결과를 다시 계산한 다음에 계산된 결과로 정렬 비교에 참여한다.따라서 Python 2에서 제곱값 크기에 따라 정렬하면 다음과 같은 두 가지 실현 방식이 있을 수 있다

num_list = [4, 2, 8, -9, 1, -3]
# cmp   Python 2  ，Python 3   cmp  
sorted_num_list = sorted(num_list, cmp=lambda x, y: x ** 2 - y ** 2)
sorted_num_list = sorted(num_list, key=lambda x: x ** 2)

그러나 Python 3.0이 발표됨에 따라 cmp 매개 변수도 제거되었다. 즉, Python 3에서 사용자 정의 비교 논리는 키 매개 변수를 통해서만 실현될 수 있다는 것이다.cmp 매개 변수를 제거하는 이유는 Python의 것입니다Issue tracker 그중에 긴 토론이 있는데 주로 다음과 같은 두 가지 원인이 있다

cmp는 불필요한 매개 변수로 cmp를 사용하는 모든 장면은 키로 대체할 수 있다

키를 사용하는 것이 cmp를 사용하는 것보다 성능이 빠르다. N개의 요소가 있는 목록에 대해 정렬 과정에서 cmp를 호출하여 비교한다면 cmp의 호출 횟수는 Nlog(N)량급(비교적인 정렬을 바탕으로 하는 가장 빠른 시간 복잡도)이고 키 파라미터를 사용하면 모든 요소에 키 함수를 한 번만 호출하고 N번만 호출할 수 있다.키 매개 변수를 사용해도 O(Nlog(N) 등급 비교 횟수를 진행해야 하지만, 이러한 비교는 C 언어 층에서 사용자 정의 함수를 호출하는 것보다 빠르다..

상기 성능에 관한 문제에 관하여 나는 실험을 하여 각각 무작위로 1000, 10000, 100000과 1000000개의 정수를 생성한 다음에 키와 cmp의 방식으로 각각 정렬하고 정렬하는 시간 소모를 기록하였다

import random
import time

counts = (1000, 10000, 100000, 1000000)

def custom_cmp(x, y):
  return x ** 2 - y ** 2

def custom_key(x):
  return x ** 2

print('%7s%20s%20s' % ('count', 'cmp_duration', 'key_duration'))
for count in counts:
  min_num = -count // 2
  max_num = count // 2
  nums = [random.randint(min_num, max_num) for _ in range(count)]
  start = time.time()
  sorted(nums, cmp=custom_cmp)
  cmp_duration = time.time() - start
  start = time.time()
  sorted(nums, key=custom_key)
  key_duration = time.time() - start
  print('%7d%20.2f%20.2f' % (count, cmp_duration, key_duration))

제 노트북에서 실행한 결과는 다음과 같습니다.

 count    cmp_duration    key_duration
  1000        0.00        0.00
 10000        0.02        0.01
 100000        0.34        0.11
1000000        4.75        1.85

목록에 있는 숫자의 수량이 100000을 초과할 때 키 함수를 사용하는 성능의 장점이 매우 뚜렷하고 cmp보다 2~3배 빠르다는 것을 알 수 있다.
자바나 C++ 등 다른 프로그래밍 언어에 익숙한 학생들에게는 cmp의 비교 방식을 더 잘 알 수 있다.사실 Python 3에서도 functools 도구 패키지의 cmp_를 통해to_키 () 함수는 cmp를 키로 변환하여 두 파라미터를 수신하는 사용자 정의 비교 함수 cmp를 사용합니다.

import functools

num_list = [4, 2, 8, -9, 1, -3]

def custom_cmp(x, y):
  return x ** 2 - y ** 2

sorted_num_list = sorted(num_list, key=functools.cmp_to_key(custom_cmp))
print(sorted_num_list)

그럼, cmp_to_키 () 함수는 어떻게 cmp를 키로 변환합니까? 우리는 원본을 통해 끝까지 탐구할 수 있습니다

def cmp_to_key(mycmp):
  """Convert a cmp= function into a key= function"""
  class K(object):
    __slots__ = ['obj']
    def __init__(self, obj):
      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
    __hash__ = None
  return K

사실 cmp_to_키 () 는 클래스 K를 되돌려줍니다. 클래스 K에 여러 가지 비교 연산자를 다시 불러왔을 뿐입니다. 다시 불러오는 과정에서 사용자 정의 비교 함수 mycmp를 사용하여 K의 크기 비교 논리가 mycmp와 일치하도록 합니다.이렇게num_list의 모든 요소num은 한 번 K(num)를 실행하여 클래스 K의 실례를 생성한 다음 서로 다른 K의 실례의 크기를 비교하여 정렬합니다.
cmp를 통해서_to_키 () 는 사용자 정의 cmp 함수를 호출할 수 있지만, 키 함수를 우선적으로 사용해야 합니다. cmp_를 통해to_key() 방식은 정렬 과정에서 많은 종류의 K를 만드는 실례를 만들어 성능에 큰 영향을 미친다. 다음은 cmp_to_키()와 키의 성능 비교

 count     cmp_to_key    key_duration
  1000        0.01        0.00
 10000        0.10        0.01
 100000        1.36        0.09
1000000        16.89        1.13

당num_list의 수가 1000000일 때 키비 cmp_to_키가 15배 가까이 빨라졌어요.
본고는 주로sorted 함수에서 사용자 정의 비교 논리를 소개했다. Python2에서는 cmp나 키를 통해 실현할 수 있고 cmp는 2개의 파라미터를 수신하여 되돌아오는 수치를 통해 두 파라미터의 크기를 판단하고 키는 새로운 결과를 다시 계산하여 비교에 참여한다.Python 3에서 cmp의 성능과 불필요한 원인을 고려하여 제거했습니다.Python 3.2에서 functools를 제공합니다.cmp_to_키라는 함수는 사용자 정의 비교 함수 cmp를 사용하지만, 성능을 고려하여 우리는 키를 우선적으로 사용하여 정렬해야 한다.
이상은Python에서sorted가 어떻게 비교 논리를 사용자 정의하는지에 대한 상세한 내용입니다.pythonsorted 사용자 정의 비교 논리에 대한 더 많은 자료는 저희 다른 관련 글을 주목해 주십시오!