「時間の複雑さの落とし穴に注意してください」-Python チュートリアル-php.cn

“Be wary of time complexity pitfalls

時間の複雑さの落とし穴に注意してください

ここに書いてください

bilibili vedio にもこれが表示されます: [Bilibili Video][https://www.bilibili.com/video/BV16u4m1c7cU/?spm_id_from=333.999.0.0] これは良い vedio だと思いますが、言語は中国語です。

時間の複雑さ

時間計算量とは何を意味しますか?
時間計算量は、入力サイズの関数としてアルゴリズムの実行にかかる時間を測定します。これはアルゴリズムの効率を記述する方法であり、さまざまなアルゴリズムを比較し、どれが最も効率的であるかを判断するために使用されます。
時間計算量の計算方法
時間計算量を計算するには、アルゴリズムによって実行される演算の数を入力のサイズの関数として考慮する必要があります。操作の数を測定する最も一般的な方法は、特定の操作が実行された回数をカウントすることです。
時間計算量を計算する際によくある落とし穴は何ですか?
1. 入力サイズを考慮しない: アルゴリズムによって実行される操作の数だけを考慮すると、時間の複雑さを過小評価する可能性があります。たとえば、ループの実行回数を数えても、入力のサイズを考慮しない場合、時間計算量が高すぎる可能性があります。
1. アルゴリズムの効率を考慮していない: 一部のアルゴリズムは、入力サイズが小さい場合でも多くの演算を実行する可能性があり、これにより時間の複雑さが高くなる可能性があります。たとえば、バブルソートや選択ソートなどのソートアルゴリズムは、小さな配列内の 2 つの要素を交換するだけで済む場合でも、二次時間計算量を持ちます。
1. アルゴリズムの最悪のシナリオを考慮していない: 一部のアルゴリズムには、最悪のシナリオよりも少ない操作を実行する最良のシナリオがあります。たとえば、二分探索のような検索アルゴリズムには、対数時間でターゲット要素を見つけるという最良のシナリオがありますが、配列内のすべての要素を調べる必要があるという最悪のシナリオもあります。

時間計算量の例をいくつか見てみましょう

ここに質問があります:
リスト内の最大 10 個の整数を見つけます。

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

ログイン後にコピー

テスト関数は次のとおりです:

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

ログイン後にコピー

解決策 1: ヒープを使用する

heapq モジュールを使用するソリューションは次のとおりです:

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

ログイン後にコピー

または、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)

ログイン後にコピー

解決策 2: 並べ替えを使用する

sort 関数を使用するソリューションは次のとおりです:

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

ログイン後にコピー

ヒープの時間計算量は O(n log k) であり、ソート関数の時間計算量は O(n log n) であることはほとんどの人が知っています。

最初の解決策は 2 番目の解決策よりも優れているようです。しかし、Python ではそうではありません。

最終的なコードを見てください:

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)}")

ログイン後にコピー

Python3.11 VScode で実行しました。結果は次のとおりです。

nは大きくない

ヒープクを使用: 0.002430099993944168
Python ヒープq: 0.06343129999004304
ソート済み : 9.280000813305378e-05
n = 910
ヒープクを使用: 9.220000356435776e-05
Python ヒープq: 0.07715500006452203
ソート済み : 9.360001422464848e-05
n = 920
ヒープクを使用: 9.440002031624317e-05
Python ヒープq: 0.06573969998862594
ソート済み: 0.00012450001668184996
n = 930
ヒープクを使用: 9.689992293715477e-05
Python ヒープq: 0.06760239996947348
ソート済み : 9.66999214142561e-05
n = 940
ヒープクを使用: 9.600003249943256e-05
Python ヒープq: 0.07372559991199523
ソート済み : 9.680003859102726e-05
n = 950
ヒープクを使用: 9.770004544407129e-05
Python ヒープq: 0.07306570000946522
ソート済み: 0.00011979998089373112
n = 960
ヒープクを使用: 9.980006143450737e-05
Python ヒープq: 0.0771204000338912
ソート済み: 0.00022829999215900898
n = 970
ヒープクを使用: 0.0001601999392732978
Python ヒープq: 0.07493270002305508
ソート済み: 0.00010840001050382853
n = 980
ヒープクを使用: 9.949994273483753e-05
Python ヒープq: 0.07698320003692061
ソート済み : 0.00010300008580088615
n = 990
ヒープクを使用: 9.979994501918554e-05
Python ヒープq: 0.0848745999392122
ソート済み: 0.00012620002962648869

n が大きい場合は?

n = 10000
ヒープクを使用: 0.003642000025138259
Python ヒープq: 9.698883199947886
ソート済み: 0.00107999995816499
n = 11000
ヒープクを使用: 0.0014836000045761466
Python ヒープq: 10.537632800056599
ソート済み: 0.0012236000038683414
n = 12000
ヒープクを使用: 0.001384599949233234
Python ヒープq: 12.328411899972707
ソート済み: 0.0013226999435573816
n = 13000
ヒープクを使用: 0.0020017001079395413
Python ヒープq: 15.637207800056785
ソート済み: 0.0015075999544933438
n = 14000
ヒープクを使用: 0.0017026999266818166
Python ヒープq: 17.298848500009626
ソート済み: 0.0016967999981716275
n = 15000
ヒープクを使用: 0.0017773000290617347
Python ヒープq: 20.780625900020823
ソート済み: 0.0017105999868363142

気づいたこととそれを改善する方法

n が大きい場合、Sorted には少し時間がかかります (場合によっては heapq を使用するよりも良い場合もあります) が、Python Heapq には多くの時間がかかります。

Sorted には少し時間がかかるのに、Python Heapq には時間がかかるのはなぜですか?
sorted() は Python の組み込み関数であるため、それに関する Python 公式ドキュメントを見つけることができます。

組み込み関数はコンパイル言語である C で記述されているため、heapq よりも高速です。

それを改善するにはどうすればよいですか?
heapq.sort() の代わりに組み込み関数sorted() を使用すると、コードのパフォーマンスを向上させることができます。 sorted() 関数は Python の組み込み関数であり、C で実装されているため、heapq.sort()

脳震盪

大規模なデータを扱う場合は、コードのパフォーマンスを向上させるために heapq.sort() の代わりに組み込み関数を使用する必要があります。大規模なデータを扱うときは、時間の複雑さの落とし穴に注意する必要があります。場合によっては、時間計算量の落とし穴が避けられないことがありますが、可能な限り回避するように努めるべきです。