비교 최적화로 Python 정렬을 더 빠르게 만드는 방법

이 텍스트에서는 Python과 언어의 참조 구현인 CPython이라는 용어가 같은 의미로 사용됩니다. 이 문서에서는 특히 CPython을 다루며 Python의 다른 구현에는 관련이 없습니다.

Python은 실제 구현의 복잡성을 이면에 남겨두고 프로그래머가 자신의 아이디어를 간단한 용어로 표현할 수 있게 해주는 아름다운 언어입니다.

추상화하는 것 중 하나는 정렬입니다.

'파이썬에서는 정렬이 어떻게 구현되나요?'라는 질문에 대한 답을 쉽게 찾을 수 있습니다. 이는 거의 항상 "파이썬은 어떤 정렬 알고리즘을 사용합니까?"라는 또 다른 질문에 답합니다.

그러나 이로 인해 흥미로운 구현 세부 사항이 뒤처지는 경우가 많습니다.

7년 전 Python 3.7에 도입되었음에도 불구하고 충분히 논의되지 않은 구현 세부 사항이 하나 있습니다.

sorted() 및 list.sort()는 일반적인 경우에 최적화되어 최대 40~75% 더 빨라졌습니다. (bpo-28685의 Elliot Gorokhovsky가 제공)

하지만 시작하기 전에...

Python 정렬에 대한 간략한 재소개

Python에서 목록을 정렬해야 하는 경우 두 가지 옵션이 있습니다.

• 목록 메소드: list.sort(*, key=None, reverse=False), 주어진 목록을 제자리에서 정렬
• 내장 함수: sorted(반복 가능, /, *, key=None, reverse= False), 인수를 수정하지 않고 정렬된 목록을 반환합니다

다른 내장 iterable을 정렬해야 하는 경우 iterable 유형이나 매개변수로 전달된 생성기에 관계없이 sorted만 사용할 수 있습니다.

sorted는 내부적으로 list.sort를 사용하기 때문에 항상 목록을 반환합니다.

다음은 순수 Python으로 재작성된 CPython의 정렬된 C 구현과 대략적으로 동일합니다.

def sorted(iterable: Iterable[Any], key=None, reverse=False):
    new_list = list(iterable)
    new_list.sort(key=key, reverse=reverse)
    return new_list

네, 정말 간단합니다.

Python이 정렬을 더 빠르게 만드는 방법

정렬에 대한 Python의 내부 문서에 따르면 다음과 같습니다.

때때로 더 느린 일반 PyObject_RichCompareBool을 더 빠른 유형별 비교로 대체할 수 있습니다

간단히 이 최적화는 다음과 같이 설명할 수 있습니다.

목록이 동질적인 경우 Python은 유형별 비교 함수

를 사용합니다.

동종 목록이란 무엇입니까?

동질 목록은 한 가지 유형의 요소만 포함하는 목록입니다.

예:

homogeneous = [1, 2, 3, 4]

반면에 이는 동질적인 목록이 아닙니다.

heterogeneous = [1, "2", (3, ), {'4': 4}]

흥미롭게도 공식 Python 튜토리얼에는 다음과 같은 내용이 나와 있습니다.

목록은 변경 가능하며 해당 요소는 대개 동종이며 목록을 반복하여 액세스합니다

튜플에 대한 추가 참고 사항

동일한 튜토리얼에 다음과 같이 나와 있습니다.

튜플은 불변이며 일반적으로 요소의 이질적인 시퀀스를 포함합니다

튜플이나 리스트를 언제 사용해야 하는지 궁금하다면 다음과 같은 경험 법칙을 따르세요.
요소의 유형이 같으면 목록을 사용하고, 그렇지 않으면 튜플을 사용하세요

잠깐, 배열은 어떻습니까?

Python은 숫자 값에 대해 동종 배열 컨테이너 개체를 구현합니다.

그러나 Python 3.12부터 배열은 자체 정렬 방법을 구현하지 않습니다.

정렬하는 유일한 방법은 내부적으로 배열에서 목록을 생성하고 프로세스에서 모든 유형 관련 정보를 삭제하는 sorted를 사용하는 것입니다.

유형별 비교 기능을 사용하면 왜 도움이 되나요?

Python에서는 실제 비교를 수행하기 전에 다양한 검사를 수행하므로 비교에는 비용이 많이 듭니다.

다음은 Python에서 두 값을 비교할 때 내부적으로 어떤 일이 발생하는지에 대한 간단한 설명입니다.

• Python은 비교 함수에 전달된 값이 NULL이 아닌지 확인합니다.
• 값의 유형이 다르지만 오른쪽 피연산자가 왼쪽의 하위 유형인 경우 Python은 오른쪽 피연산자의 비교 함수를 사용하지만 그 반대입니다(예: < for >를 사용함)
• 값이 동일한 유형이거나 다른 유형이지만 어느 쪽도 다른 항목의 하위 유형이 아닌 경우:
  • Python은 먼저 왼쪽 피연산자의 비교 기능을 시도합니다
  • 실패하면 오른쪽 피연산자의 비교 함수를 시도하지만 그 반대입니다.
  • 그것도 실패하고 비교가 같음 또는 같지 않음에 대한 것이라면 항등 비교를 반환합니다(메모리에서 동일한 개체를 참조하는 값의 경우 True)
  • 그렇지 않으면 TypeError가 발생합니다.

이 밖에도 유형별 자체 비교 기능으로 추가 점검을 구현했습니다.

For example, when comparing strings, Python will check if the string characters take more than one byte of memory, and float comparison will compare a pair of float's and a float and an int differently.

A more detailed explanation and diagram can be found here: Adding Data-Aware Sort Optimizations to CPython

Before this optimization was introduced, Python had to execute all this various type-specific and non-type-specific checks every time two values were compared during sorting.

Checking List Element's Types in Advance

There's no magical way to know if all the elements of a list are of the same type other than to iterate over the list and check each element.

Python does almost exactly that — checking the types of sorting keys generated by key function passed to list.sort or sorted as a parameter

Constructing a List of Keys

If a key function is provided, Python uses it to construct a list of keys, otherwise it uses the list's own values as sorting keys.

In an oversimplified manner, keys construction can be expressed as the following python code.

if key is None:
    keys = list_items
else:
    keys = [key(list_item) for list_item in list_item]

Note, that keys used internally in CPython are a C array of CPython object references, and not a Python list

Once the keys are constructed, Python checks their types.

Checking Key's Type

When checking the types of keys, Python's sorting algorithm tries to determine if all elements in the keys array are either str, int, float or tuple, or simply of the same type, with some constraints for base types.

It's worth noting that checking the types of the keys adds some extra work up front. Python does this because it usually pays off by making the actual sorting faster, especially for longer lists.

int constraints

int should not be a bignum

Practically this means that for this optimization to work, integer should be less than 2^30 - 1 (this may vary depending on the platform)

As a side note, here is a great article which explains how Python handles big integers: # How python implements super long integers?

str constraints

All characters of a string should take less than 1 byte of memory, meaning that they should be represented by integer values in the range of 0-255

In practice, this means that strings should consist only of Latin characters, spaces, and some special characters found in the ASCII table.

float constraints

There are no constraints for floats in order for this optimization to work.

tuple constraints

• Only the first element's type is checked
• This element itself should not be a tuple itself
• If all tuples share the same type for their first element, the comparison optimization is applied to them
• All other elements are compared as usual

How Can I Apply This Knowledge?

First of all, isn’t it fascinating to know?

Secondly, mentioning this knowledge could be a nice touch in a Python Developer interview.

As for actual code development, understanding this optimization can help you improve sorting performance.

Optimize by Selecting the Type of Values Wisely

According to the benchmark in the PR that introduced this optimization, sorting a list that consists only of floats rather than a list of floats with even a single integer at the end is almost twice as fast.

So when it's time to optimize, transforming list like this

floats_and_int = [1.0, -1.0, -0.5, 3]

Into list that looks like this

just_floats = [1.0, -1.0, -0.5, 3.0] # note that 3.0 is a float now

might improve performance.

Optimize by Using Keys for Lists of Objects

While Python's sorting optimization works well with built-in types, it's important to understand how it interacts with custom classes.

When sorting objects of custom classes, Python relies on the comparison methods you define, such as __lt__ (less than) or __gt__ (greater than).

However, the type-specific optimization doesn't apply to custom classes.
Python will always use the general comparison method for these objects.

Here's an example:

class MyClass:
    def __init__(self, value): 
        self.value = value 

    def __lt__(self, other): 
        return self.value < other.value 

my_list = [MyClass(3), MyClass(1), MyClass(2)] 
sorted_list = sorted(my_list)

In this case, Python will use the __lt__ method for comparisons, but it won't benefit from the type-specific optimization. The sorting will still work correctly, but it may not be as fast as sorting built-in types.

If performance is critical when sorting custom objects, consider using a key function that returns a built-in type:

sorted_list = sorted(my_list, key=lambda x: x.value)

Afterword

Premature optimization, especially in Python, is evil.

CPython의 특정 최적화를 중심으로 전체 애플리케이션을 설계해서는 안 되지만 이러한 최적화에 대해 알아두는 것이 좋습니다. 도구를 잘 아는 것이 더 숙련된 개발자가 되는 방법입니다.

이러한 최적화에 주의를 기울이면 상황이 필요할 때, 특히 성능이 중요할 때 이를 활용할 수 있습니다.

타임스탬프를 기반으로 정렬하는 시나리오를 생각해 보세요. 날짜/시간 개체 대신 동질적인 정수 목록(Unix 타임스탬프)을 사용하면 이 최적화를 효과적으로 활용할 수 있습니다.

그러나 코드 가독성과 유지 관리 가능성이 이러한 최적화보다 우선해야 한다는 점을 기억하는 것이 중요합니다.

이러한 낮은 수준의 세부 사항을 아는 것도 중요하지만 Python을 생산적인 언어로 만드는 높은 수준의 추상화를 이해하는 것도 그만큼 중요합니다.

Python은 놀라운 언어입니다. Python의 깊이를 탐구하면 Python을 더 잘 이해하고 더 나은 Python 프로그래머가 될 수 있습니다.

위 내용은 비교 최적화로 Python 정렬을 더 빠르게 만드는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!