Zamanında Biten Algoritmalar: Karmaşıklık Kontrolü

Bir fonksiyon yazarsınız, test verileriniz üzerinde çalıştırırsınız ve iyi çalışır. Sonra production verilerine ulaşır — 500 yerine 500.000 satır — ve istek zaman aşımına uğrar. Bu sürekli olur ve neredeyse her zaman küçük ölçekte makul görünen kodun arkasında saklı bir karmaşıklık problemidir.

Neden dizüstü bilgisayarınız sizi aldattı

Bir O(n²) algoritması 100 öğe üzerinde çalışırsa 10.000 işlem yapar. Bu herhangi bir makinede anında gerçekleşir. Aynı algoritmayı 100.000 öğe üzerinde çalıştırırsanız 10 milyar işleme ulaşırsınız — milisaniye yerine dakika veya saat. n'den n²'ye sıçrama n büyük olana kadar tehlikeli hissettirilmez; bu tam olarak neden kod incelemesi ve yerel testlerin arasından sıvışıp gider.

Klasik örnek: iç içe döngü ile mükerrer kontrol etmek.

def has_duplicates(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

Bu O(n²). Bunu bir set ile değiştirin:

def has_duplicates(items):
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False

Şimdi O(n). Set aramaları ortalama O(1) olduğu için, bütün fonksiyon doğrusal olarak ölçeklenir, ikinci dereceden değil. 10.000 öğe üzerinde bu, kabaca 100 milyon karşılaştırma ile 10.000 arasındaki farktır.

Optimize etmeden önce ölçün

Tahmin yapmayın. Mikro kıyaslamalar için timeit kullanın:

import timeit
timeit.timeit(lambda: has_duplicates(list(range(5000))), number=10)

Daha büyük fonksiyonlar için cProfile ile profil oluşturun:

python -m cProfile -s cumulative myscript.py

cumtime sütununa bakın. Bir fonksiyon çalışma zamanının %90'ını yiyorsa, bu sizin hedefiniztir. Darboğaz olmayan kodları optimize etmek zamanınızı boşa harcar ve hiçbir kazanç için karmaşıklık ekler.

Sessizce yavaş hale gelen yaygın desenler

Tekrarlanan liste üyelik kontrolleri. if x in my_list bir list için O(n) ancak bir set veya dict için ortalama O(1) olur. Eğer bir döngü içinde üyeliği kontrol ediyorsanız, O(n) döngü içindeki O(n) kontrol sizi O(n²) verir. Listeyi bir set ile değiştirin ve geri O(n) olursunuz.

Döngü içinde string birleştirme. Python'da, result += chunk string döngüsü içinde en kötü durumda O(n²) olduğu için stringler değişmez ve her birleştirme bütün şeyi kopyalar. Bunun yerine ''.join(chunks) kullanın — stringi bir kez oluşturur.

Gerekmediğinde sıralamak. sorted() O(n log n) olur. Eğer her iterasyon için sadece maksimum veya minimumu bulmak için bunu bir döngü içinde çağırıyorsanız, max()/min() (O(n)) veya daha iyi, çalışan ekstrem için tekrar tekrar ihtiyaç duyarsanız heap (heapq) kullanın. heapq.nlargest(k, data) O(n log k) olur, k küçük olduğunda bütün listeyi sıralamaktan çok daha ucuzdur.

Memoization olmayan recursive fonksiyonlar. Naive recursive Fibonacci O(2ⁿ) olur çünkü aynı alt-problemleri tekrar tekrar hesaplar. functools.lru_cache ekleyin ve O(n) olur:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Gerçek koddan Big O'yu hızlı okumak

Aynı girdiye ait iç içe döngüleri sayın — bu genellikle üslerinizdir. Tek bir döngü O(n) olur. Bir döngü içinde bir döngü O(n²) olur, eğer iç döngünün aralığı küçülmezse (bubble sort'un optimize edilmiş formunda olduğu gibi, en kötü durumda yine O(n²) ancak daha az karşılaştırma). Sorunu yarıya ayıran recursive çağrılar, binary search veya merge sort gibi, O(log n) veya O(n log n) işaret eder. Seviye başına birden çok çağrıya dallanan recursive çağrılar, naive Fibonacci gibi, eksponensiyel zamana işaret eder — memoization veya iteratif yazma ihtiyacının kuvvetli bir sinyalidir.

İyi bir alışkanlık: iç içe döngüler veya recursion yazmazdan önce, n'nin test dosyanızda değil, production'da gerçekçi olarak ne kadar büyük olabileceğini sorun. n altı rakama ulaşabilirse, O(n²) çözüm sevk edilmeden önce ikinci bir bakış gerektirir.

Karmaşıklık analizi, sıralama algoritmaları ve profil oluşturma araçları hakkında daha fazla bilgi için Korra Studio'daki Python ve Computer Science bölümlerini kontrol edin.