Cara Pengoptimuman Perbandingan Menjadikan Pengisihan Python Lebih Cepat

Dalam teks ini istilah Python dan CPython, yang merupakan pelaksanaan rujukan bahasa, digunakan secara bergantian. Artikel ini secara khusus menangani CPython dan tidak melibatkan pelaksanaan Python yang lain.

Python ialah bahasa yang indah yang membolehkan pengaturcara meluahkan idea mereka dalam istilah mudah meninggalkan kerumitan pelaksanaan sebenar di belakang tabir.

Salah satu perkara yang diabsahkan ialah mengisih.

Anda boleh mencari jawapan kepada soalan "bagaimana cara pengisihan dilaksanakan dalam Python?" yang hampir selalu menjawab soalan lain: "Algoritma pengisihan apakah yang digunakan oleh Python?".

Walau bagaimanapun, ini sering meninggalkan beberapa butiran pelaksanaan yang menarik.

Terdapat satu perincian pelaksanaan yang saya rasa tidak cukup dibincangkan, walaupun ia telah diperkenalkan lebih tujuh tahun lalu dalam python 3.7:

sorted() dan list.sort() telah dioptimumkan untuk kes biasa sehingga 40-75% lebih pantas. (Disumbangkan oleh Elliot Gorokhovsky dalam bpo-28685.)

Tetapi sebelum kita mula...

Pengenalan Semula Ringkas kepada Isih dalam Python

Apabila anda perlu mengisih senarai dalam python, anda mempunyai dua pilihan:

• Kaedah senarai: list.sort(*, key=None, reverse=False), yang mengisih senarai yang diberikan di tempat
• Fungsi terbina dalam: diisih(boleh lelar, /, *, kunci=Tiada, terbalik= Palsu), yang mengembalikan senarai diisih tanpa mengubah suai hujahnya

Jika anda perlu mengisih mana-mana lelaran terbina dalam lain, anda hanya boleh menggunakan diisih tanpa mengira jenis lelaran atau penjana yang diluluskan sebagai parameter.

isih sentiasa mengembalikan senarai kerana ia menggunakan senarai.isih secara dalaman.

Berikut ialah persamaan kasar pelaksanaan C yang diisih CPython yang ditulis semula dalam python tulen:

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

Ya, semudah itu.

Bagaimana Python Membuat Isih Lebih Cepat

Seperti yang dinyatakan dalam dokumentasi dalaman Python untuk pengisihan:

Adakalanya mungkin untuk menggantikan perbandingan khusus jenis yang lebih pantas untuk PyObject_RichCompareBool generik yang lebih perlahan

Dan secara ringkasnya pengoptimuman ini boleh diterangkan seperti berikut:

Apabila senarai adalah homogen, Python menggunakan fungsi perbandingan jenis khusus

Apakah Senarai Homogen?

Senarai homogen ialah senarai yang mengandungi unsur satu jenis sahaja.

Contohnya:

homogeneous = [1, 2, 3, 4]

Sebaliknya, ini bukan senarai homogen:

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

Menariknya, tutorial Python rasmi menyatakan:

Senarai boleh berubah dan elemennya biasanya homogen dan diakses dengan mengulangi senarai

Nota sampingan tentang tupel

Tutorial yang sama menyatakan:

Tuples adalah tidak berubah dan biasanya mengandungi jujukan heterogen unsur

Jadi, jika anda tertanya-tanya bila hendak menggunakan tuple atau senarai, berikut ialah peraturan praktikal:
jika elemen adalah jenis yang sama, gunakan senarai, jika tidak gunakan tuple

Tunggu, dan bagaimana pula dengan tatasusunan?

Python melaksanakan objek bekas tatasusunan homogen untuk nilai angka.

Walau bagaimanapun, pada python 3.12, tatasusunan tidak melaksanakan kaedah isihan mereka sendiri.

Satu-satunya cara untuk mengisihnya ialah dengan menggunakan diisih, yang secara dalaman mencipta senarai daripada tatasusunan, memadamkan sebarang maklumat berkaitan jenis dalam proses.

Mengapa Menggunakan Fungsi Perbandingan Khusus Jenis Membantu?

Perbandingan dalam python adalah mahal, kerana Python melakukan pelbagai semakan sebelum melakukan sebarang perbandingan sebenar.

Berikut ialah penjelasan ringkas tentang perkara yang berlaku di bawah hud apabila anda membandingkan dua nilai dalam python:

• Python menyemak bahawa nilai yang dihantar kepada fungsi perbandingan bukan NULL
• Jika nilai daripada jenis yang berbeza, tetapi operan kanan ialah subjenis kiri, Python menggunakan fungsi perbandingan operan kanan, tetapi diterbalikkan (mis., ia akan menggunakan < untuk >)
• Jika nilai adalah jenis yang sama, atau jenis yang berbeza tetapi bukan subjenis yang lain:
  • Python akan mencuba dahulu fungsi perbandingan operan kiri
  • Jika gagal, ia akan mencuba fungsi perbandingan operan kanan, tetapi diterbalikkan.
  • Jika itu juga gagal, dan perbandingan adalah untuk kesamaan atau ketidaksamaan, ia akan mengembalikan perbandingan identiti (Benar untuk nilai yang merujuk kepada objek yang sama dalam ingatan)
  • Jika tidak, ia menimbulkan TypeError

Selain itu, fungsi perbandingan masing-masing jenis melaksanakan semakan tambahan.

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.

Anda tidak seharusnya mereka bentuk keseluruhan aplikasi anda mengikut pengoptimuman khusus dalam CPython, tetapi adalah baik untuk mengetahui pengoptimuman ini: mengetahui alatan anda dengan baik ialah cara untuk menjadi pembangun yang lebih mahir.

Berhati-hati dengan pengoptimuman seperti ini membolehkan anda memanfaatkannya apabila keadaan memerlukannya, terutamanya apabila prestasi menjadi kritikal:

Pertimbangkan senario di mana pengisihan anda berdasarkan cap masa: menggunakan senarai integer homogen (cap masa Unix) dan bukannya objek masa tarikh boleh memanfaatkan pengoptimuman ini dengan berkesan.

Walau bagaimanapun, adalah penting untuk diingat bahawa kebolehbacaan dan kebolehselenggaraan kod harus diutamakan daripada pengoptimuman tersebut.

Walaupun penting untuk mengetahui tentang butiran peringkat rendah ini, adalah sama pentingnya untuk menghargai abstraksi peringkat tinggi Python yang menjadikannya bahasa yang begitu produktif.

Python ialah bahasa yang menakjubkan, dan meneroka kedalamannya boleh membantu anda memahaminya dengan lebih baik dan menjadi pengaturcara Python yang lebih baik.

Atas ialah kandungan terperinci Cara Pengoptimuman Perbandingan Menjadikan Pengisihan Python Lebih Cepat. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!