Bekerja dengan Senarai Isih dalam Python: Keajaiban Modul `bisect`

Mengusahakan senarai yang diisih kadangkala boleh menjadi agak rumit. Anda perlu mengekalkan susunan senarai selepas setiap sisipan dan mencari elemen di dalamnya dengan cekap. Carian binari ialah algoritma yang berkuasa untuk mencari dalam senarai yang diisih. Walaupun melaksanakannya dari awal tidak terlalu sukar, ia boleh memakan masa. Nasib baik, Python menawarkan modul dua belah, yang menjadikan pengendalian senarai yang diisih lebih mudah.

Apakah Carian Binari?

Carian binari ialah algoritma yang mencari kedudukan nilai sasaran dalam tatasusunan yang diisih. Bayangkan anda sedang mencari nama dalam buku telefon. Daripada bermula dari halaman pertama, anda mungkin bermula di tengah-tengah buku dan memutuskan sama ada untuk meneruskan carian pada separuh pertama atau kedua, berdasarkan sama ada nama itu lebih besar mengikut abjad atau kurang daripada nama di tengah. Carian binari beroperasi dengan cara yang sama: ia bermula dengan dua petunjuk, satu di permulaan dan satu lagi di hujung senarai. Elemen tengah kemudiannya dikira dan dibandingkan dengan sasaran.

Modul dua belah: Memudahkan Operasi Senarai Isih

Walaupun carian binari berkesan, menulis pelaksanaan setiap masa boleh membosankan. Tetapi bagaimana jika anda boleh melakukan operasi yang sama dengan hanya satu baris kod? Di situlah modul dua belah Python masuk. Sebahagian daripada perpustakaan standard Python, dua belah membantu anda mengekalkan senarai yang diisih tanpa perlu mengisihnya selepas setiap sisipan. Ia melakukannya menggunakan algoritma pembahagian dua yang mudah.

Modul belah dua menyediakan dua fungsi utama: dua belah dan selit. Fungsi dua belah mencari indeks di mana elemen harus disisipkan untuk memastikan senarai diisih, manakala sisipan memasukkan elemen ke dalam senarai sambil mengekalkan susunannya yang diisih.

Menggunakan Modul dua belah: Contoh Praktikal

Mari mulakan dengan mengimport modul:

import bisect

Contoh 1: Memasukkan Nombor ke dalam Senarai Isih

Andaikan kita mempunyai senarai nombor yang diisih:

data = [1, 3, 5, 6, 8]

Untuk memasukkan nombor baharu sambil mengekalkan senarai diisih, hanya gunakan:

bisect.insort(data, 7)

selepas menjalankan kod ini, data akan kelihatan seperti ini:

[1, 3, 5, 6, 7, 8]

Contoh 2: Mencari Titik Sisipan

Bagaimana jika anda hanya ingin mengetahui di mana nombor akan dimasukkan tanpa benar-benar memasukkannya? Anda boleh menggunakan fungsi dua belah kiri atau dua belah kanan:

index = bisect.bisect_left(data, 4)
print(index)  # Output: 2

Ini memberitahu kita bahawa nombor 4 harus dimasukkan pada indeks 2 untuk memastikan senarai diisih.

Contoh 3: Mengekalkan Susunan Isih dalam Senarai Dinamik

Katakanlah anda menguruskan senarai yang berkembang secara dinamik dan perlu memasukkan elemen sambil memastikan ia kekal diisih:

dynamic_data = []
for number in [10, 3, 7, 5, 8, 2]:
    bisect.insort(dynamic_data, number)
    print(dynamic_data)

Ini akan mengeluarkan senarai pada setiap langkah apabila elemen dimasukkan:

[10]
[3, 10]
[3, 7, 10]
[3, 5, 7, 10]
[3, 5, 7, 8, 10]
[2, 3, 5, 7, 8, 10]

Contoh 4: Menggunakan dua belah dengan Objek Tersuai

Andaikan anda mempunyai senarai objek tersuai, seperti tupel, dan anda ingin memasukkannya berdasarkan kriteria tertentu:

items = [(1, 'apple'), (3, 'cherry'), (5, 'date')]
bisect.insort(items, (2, 'banana'))
print(items)  # Output: [(1, 'apple'), (2, 'banana'), (3, 'cherry'), (5, 'date')]

Atau anda mungkin mahu memasukkan berdasarkan elemen kedua setiap tuple:

items = [('a', 10), ('b', 20), ('c', 30)]
bisect.insort(items, ('d', 25), key=lambda x: x[1])
print(items)  # Output: [('a', 10), ('b', 20), ('d', 25), ('c', 30)]

dua belah dalam Tindakan: Mencari Perkataan

Modul belah dua tidak terhad kepada nombor; ia juga boleh berguna untuk mencari dalam senarai rentetan, tupel, aksara dll.
Contohnya, untuk mencari perkataan dalam senarai diisih:

def searchWord(dictionary, target):
    return bisect.bisect_left(dictionary, target)


dictionary = ['alphabet', 'bear', 'car', 'density', 'epic', 'fear', 'guitar', 'happiness', 'ice', 'joke']
target = 'guitar'

Atau untuk mencari perkataan pertama dalam kumpulan perkataan dengan awalan tertentu:

def searchPrefix(dictionary, prefix):
    return bisect.bisect_left(dictionary, prefix), bisect.bisect_right(dictionary, prefix + 'z') # adding 'z' to the prefix to get the last word starting with the prefix
# bisect_rigth function will be discussed in a moment


dictionary = ['alphabet', 'bear', 'car', 'density', 'epic', 'fear', 'generator', 'genetic', 'genius', 'gentlemen', 'guitar', 'happiness', 'ice', 'joke']
prefix = 'gen'

Walau bagaimanapun, perlu diingat bahawa bisect_left mengembalikan indeks di mana sasaran harus dimasukkan, bukan sama ada sasaran itu wujud dalam senarai.

Varian belah dua dan sisipan

Modul ini juga termasuk varian sebelah kanan: dua belah kanan dan insort_kanan. Fungsi ini mengembalikan indeks paling kanan untuk memasukkan elemen jika ia sudah ada dalam senarai. Contohnya, bisect_right akan mengembalikan indeks elemen pertama yang lebih besar daripada sasaran jika sasaran berada dalam senarai, manakala insort_right memasukkan elemen pada kedudukan tersebut.

belah Di Bawah Tudung

Kuasa modul dua belah terletak pada pelaksanaan algoritma carian binari yang cekap. Apabila anda memanggil bisect.bisect_left, sebagai contoh, fungsi pada asasnya melakukan carian binari pada senarai untuk menentukan titik sisipan yang betul untuk elemen baharu.

Begini cara ia berfungsi di bawah tudung:

1. Permulaan: Fungsi bermula dengan dua penunjuk, lo dan hi, yang mewakili sempadan bawah dan atas julat carian dalam senarai. Pada mulanya, lo ditetapkan pada permulaan senarai (indeks 0), dan hi ditetapkan pada penghujung senarai (indeks sama dengan panjang senarai). Tetapi anda juga boleh menentukan nilai lo dan hi tersuai untuk mencari dalam julat tertentu senarai.

2. Bisection: Within a loop, the function calculates the midpoint (mid) between lo and hi. It then compares the value at mid with the target value you’re looking to insert.

3. Comparison:

* If the target is less than or equal to the value at `mid`, the upper bound (`hi`) is moved to `mid`.
* If the target is greater, the lower bound (`lo`) is moved to `mid + 1`.

1. Termination: This process continues, halving the search range each time, until lo equals hi. At this point, lo (or hi) represents the correct index where the target should be inserted to maintain the list's sorted order.

2. Insertion: For the insort function, once the correct index is found using bisect_left, the target is inserted into the list at that position.

This approach ensures that the insertion process is efficient, with a time complexity of O(log n) for the search and O(n) for the insertion due to the list shifting operation. This is significantly more efficient than sorting the list after each insertion, especially for large datasets.

bisect_left code example:

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    if key is None:
        while lo < hi:
            mid = (lo + hi) // 2
            if a[mid] < x:
                lo = mid + 1
            else:
                hi = mid
    else:
        while lo < hi:
            mid = (lo + hi) // 2
            if key(a[mid]) < x:
                lo = mid + 1
            else:
                hi = mid
    return lo

insort_left code example:

def insort_left(a, x, lo=0, hi=None, *, key=None):

    if key is None:
        lo = bisect_left(a, x, lo, hi)
    else:
        lo = bisect_left(a, key(x), lo, hi, key=key)
    a.insert(lo, x)

Conclusion

The bisect module makes working with sorted lists straightforward and efficient. The next time you need to perform binary search or insert elements into a sorted list, remember the bisect module and save yourself time and effort.

Atas ialah kandungan terperinci Bekerja dengan Senarai Isih dalam Python: Keajaiban Modul `bisect`. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!