'Berhati-hati dengan perangkap kerumitan masa\'-Tutorial Python-php.cn

“Be wary of time complexity pitfalls

Berhati-hati dengan perangkap kerumitan masa

Tulis Di Sini

Vedio bilibili juga menunjukkan ini : [Video Bilibili][https://www.bilibili.com/video/BV16u4m1c7cU/?spm_id_from=333.999.0.0] dan saya rasa ia adalah vedio yang bagus, tetapi bahasanya adalah bahasa Cina.

kerumitan masa

Apakah yang dimaksudkan dengan kerumitan masa?
Kerumitan masa ialah ukuran masa yang diambil oleh algoritma untuk dijalankan sebagai fungsi saiz inputnya. Ia ialah satu cara untuk menerangkan kecekapan algoritma dan ia digunakan untuk membandingkan algoritma yang berbeza dan menentukan yang mana satu yang paling cekap.
Bagaimana untuk mengira kerumitan masa?
Untuk mengira kerumitan masa, kita perlu mempertimbangkan bilangan operasi yang dilakukan oleh algoritma sebagai fungsi saiz input. Cara paling biasa untuk mengukur bilangan operasi ialah dengan mengira bilangan kali operasi tertentu dilakukan.
Apakah beberapa perangkap biasa apabila mengira kerumitan masa?
1. Tidak mengambil kira saiz input: Jika kami hanya mempertimbangkan bilangan operasi yang dilakukan oleh algoritma, kami mungkin memandang rendah kerumitan masa. Contohnya, jika kita mengira bilangan kali gelung dijalankan, tetapi kita tidak mengambil kira saiz input, maka kerumitan masa mungkin terlalu tinggi.
1. Tidak mengambil kira kecekapan algoritma: Sesetengah algoritma mungkin melakukan banyak operasi walaupun saiz input kecil, yang boleh membawa kepada kerumitan masa yang tinggi. Contohnya, algoritma pengisihan seperti isihan gelembung dan isihan pemilihan mempunyai kerumitan masa kuadratik, walaupun ia mungkin hanya perlu menukar dua elemen dalam tatasusunan kecil.
1. Tidak mengambil kira senario kes terburuk algoritma: Sesetengah algoritma mempunyai senario kes terbaik di mana ia melakukan operasi yang lebih sedikit daripada senario kes terburuk. Sebagai contoh, algoritma carian seperti carian binari mempunyai senario kes terbaik di mana mereka menemui elemen sasaran dalam masa logaritma, tetapi mereka mempunyai senario terburuk di mana mereka perlu memeriksa semua elemen dalam tatasusunan.

Mari lihat beberapa contoh kerumitan masa

Berikut ialah soalan:
Cari 10 integer maksimum dalam senarai.

import random
ls = [random.randint(1, 100) for _ in range(n)]

Salin selepas log masuk

Berikut ialah fungsi ujian:

import time
def benchmark(func, *args) -> float:
    start = time.perf_counter()
    func(*args)
    end = time.perf_counter()
    return end - start

Salin selepas log masuk

Penyelesaian1: Gunakan timbunan

Berikut ialah penyelesaian yang menggunakan modul heapq:

def find_max_n(ls, n):
    import heapq
    return heapq.nlargest(n, ls)

Salin selepas log masuk

Atau kita tulis dengan cara python:

def find_largest_n(nums, n):
    if n <= 0:
        return []

    max_heap = []

    for num in nums:
        if len(max_heap) < n:
            max_heap.append(num)
            # call sift_down
            for i in range((len(max_heap) - 2) // 2, -1, -1):
                _sift_down(max_heap, i)
        elif num > max_heap[0]:
            max_heap[0] = num
            _sift_down(max_heap, 0)

    return max_heap

def _sift_down(heap, index):
    left = 2 * index + 1
    right = 2 * index + 2
    largest = index

    if left < len(heap) and heap[left] > heap[largest]:
        largest = left

    if right < len(heap) and heap[right] > heap[largest]:
        largest = right

    if largest != index:
        heap[index], heap[largest] = heap[largest], heap[index]
        _sift_down(heap, largest)

Salin selepas log masuk

Penyelesaian2: Gunakan jenis

Berikut ialah penyelesaian yang menggunakan fungsi isihan:

def find_max_n(ls, n):
    return sorted(ls, reverse=True)[:n]

Salin selepas log masuk

Hampir semua orang tahu bahawa Kerumitan masa timbunan, ialah O(n log k), dan kerumitan masa bagi fungsi isihan ialah O(n log n).

Nampaknya penyelesaian Pertama lebih baik daripada penyelesaian kedua. Tetapi ia tidak benar dalam python.

Lihat kod akhir:

import time
def benchmark(func, *args) -> float:
    start = time.perf_counter()
    func(*args)
    end = time.perf_counter()
    return end - start

def find_max_n_heapq(ls, n):
    import heapq
    return heapq.nlargest(n, ls)

def find_max_n_python_heap(nums, n):
    if n <= 0:
        return []

    max_heap = []

    for num in nums:
        if len(max_heap) < n:
            max_heap.append(num)
            # call sift_down
            for i in range((len(max_heap) - 2) // 2, -1, -1):
                _sift_down(max_heap, i)
        elif num > max_heap[0]:
            max_heap[0] = num
            _sift_down(max_heap, 0)

    return max_heap

def _sift_down(heap, index):
    left = 2 * index + 1
    right = 2 * index + 2
    largest = index

    if left < len(heap) and heap[left] > heap[largest]:
        largest = left

    if right < len(heap) and heap[right] > heap[largest]:
        largest = right

    if largest != index:
        heap[index], heap[largest] = heap[largest], heap[index]
        _sift_down(heap, largest)


def find_max_n_sorted(ls, n):
    return sorted(ls, reverse=True)[:n]

# test
import random
for n in range(10, 10000, 100):
    ls = [random.randint(1, 100) for _ in range(n)]
    print(f"n = {n}")
    print(f"Use    Heapq: {benchmark(find_max_n_heapq, ls, n)}")
    print(f"Python Heapq: {benchmark(find_max_n_python_heap, ls, n)}")
    print(f"Sorted      : {benchmark(find_max_n_sorted, ls, n)}")

Salin selepas log masuk

Saya menjalankannya dalam Python3.11 VScode, Inilah hasilnya:

n tidak besar

Gunakan Heapq: 0.002430099993944168
Python Heapq: 0.06343129999004304
Diisih : 9.280000813305378e-05
n = 910
Gunakan Heapq: 9.220000356435776e-05
Python Heapq: 0.07715500006452203
Diisih : 9.360001422464848e-05
n = 920
Gunakan Heapq: 9.440002031624317e-05
Python Heapq: 0.06573969998862594
Diisih : 0.00012450001668184996
n = 930
Gunakan Heapq: 9.689992293715477e-05
Python Heapq: 0.06760239996947348
Diisih : 9.66999214142561e-05
n = 940
Gunakan Heapq: 9.600003249943256e-05
Python Heapq: 0.07372559991199523
Diisih : 9.680003859102726e-05
n = 950
Gunakan Heapq: 9.770004544407129e-05
Python Heapq: 0.07306570000946522
Diisih : 0.00011979998089373112
n = 960
Gunakan Heapq: 9.980006143450737e-05
Python Heapq: 0.0771204000338912
Diisih : 0.00022829999215900898
n = 970
Gunakan Heapq: 0.0001601999392732978
Python Heapq: 0.07493270002305508
Diisih : 0.00010840001050382853
n = 980
Gunakan Heapq: 9.949994273483753e-05
Python Heapq: 0.07698320003692061
Diisih : 0.00010300008580088615
n = 990
Gunakan Heapq: 9.979994501918554e-05
Python Heapq: 0.0848745999392122
Diisih : 0.00012620002962648869

jika n besar ?

n = 10000
Gunakan Heapq: 0.003642000025138259
Python Heapq: 9.698883199947886
Diisih : 0.00107999995816499
n = 11000
Gunakan Heapq: 0.0014836000045761466
Python Heapq: 10.537632800056599
Diisih : 0.0012236000038683414
n = 12000
Gunakan Heapq: 0.001384599949233234
Python Heapq: 12.328411899972707
Diisih : 0.0013226999435573816
n = 13000
Gunakan Heapq: 0.0020017001079395413
Python Heapq: 15.637207800056785
Diisih : 0.0015075999544933438
n = 14000
Gunakan Heapq: 0.0017026999266818166
Python Heapq: 17.298848500009626
Diisih : 0.0016967999981716275
n = 15000
Gunakan Heapq: 0.0017773000290617347
Python Heapq: 20.780625900020823
Diisih : 0.0017105999868363142

Perkara yang saya temui & cara untuk memperbaikinya

Apabila n besar, Sorted memerlukan sedikit masa (kadangkala lebih baik daripada menggunakan heapq), tetapi Python Heapq memerlukan banyak masa.

Mengapa Diisih memerlukan sedikit masa, tetapi Python Heapq memerlukan banyak masa?
Oleh kerana sorted() ialah fungsi bulit-in dalam Python, anda boleh menemui dokumen rasmi python mengenainya.

Fungsi bulit-in lebih pantas daripada heapq kerana ia ditulis dalam C, iaitu bahasa yang disusun.

Bagaimana untuk memperbaikinya?
Anda boleh menggunakan fungsi terbina dalam sorted() dan bukannya heapq.sort() untuk meningkatkan prestasi kod anda. Fungsi sorted() ialah fungsi terbina dalam Python, yang dilaksanakan dalam C dan oleh itu jauh lebih pantas daripada heapq.sort()

Gegar otak

Apabila kami berurusan dengan data yang besar, kami harus menggunakan fungsi terbina dalam dan bukannya heapq.sort() untuk meningkatkan prestasi kod kami. Kita mesti berhati-hati dengan masalah kerumitan masa apabila berurusan dengan data yang besar. Kadangkala perangkap kerumitan masa tidak dapat dielakkan, tetapi kita harus cuba mengelaknya sebaik mungkin.

Tentang Saya

Hello, saya mengqinyuan. Saya seorang pelajar. Saya suka belajar perkara baharu.
Anda boleh melihat github saya: [Github MengQinYuan][https://github.com/mengqinyuan]

Atas ialah kandungan terperinci 'Berhati-hati dengan perangkap kerumitan masa\'. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!