Algoritmen die op tijd klaar zijn: een controle op complexiteit

Je schrijft een functie, test deze met je testdata, en het werkt prima. Dan gaat het naar productie — 500.000 rijen in plaats van 500 — en het verzoek loopt uit. Dit gebeurt voortdurend, en het is bijna altijd een complexiteitsprobleem verstopt achter code die op kleine schaal redelijk leek.

Waarom je laptop je belazerde

Een O(n²)-algoritme dat op 100 items loopt, voert 10.000 operaties uit. Dat is instant op elke machine. Voer hetzelfde algoritme op 100.000 items uit en je hebt 10 miljard operaties — minuten of uren in plaats van milliseconden. De sprong van n naar n² voelt niet gevaarlijk totdat n groot wordt, wat precies de reden is waarom het door code review en lokale testing glipt.

Een klassiek voorbeeld: duplicaten controleren met een geneste loop.

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

Dit is O(n²). Vervang het door een set:

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

Nu is het O(n). Set-lookups zijn gemiddeld O(1), dus de hele functie schaalt lineair in plaats van kwadratisch. Op 10.000 items is dat het verschil tussen ongeveer 100 miljoen vergelijkingen en 10.000.

Meet voor je optimaliseert

Gooi niet naar het raam. Gebruik timeit voor microbenchmarks:

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

Voor grotere functies, profile met cProfile:

python -m cProfile -s cumulative myscript.py

Kijk naar de cumtime-kolom. Als één functie 90% van de runtime opeet, dat is je doel. Code optimaliseren die niet het bottleneck is, verspilt je tijd en voegt complexiteit toe zonder baat.

Veelvoorkomende patronen die stilletjes langzaam worden

Herhaalde lidmaatschapscontroles in een lijst. if x in my_list is O(n) voor een lijst, maar O(1) gemiddeld voor een set of dict. Als je lidmaatschap controleert in een loop, geeft die O(n)-controle in een O(n)-loop je O(n²) totaal. Vervang de lijst door een set en je bent terug op O(n).

Stringconcatenatie in een loop. In Python is result += chunk in een loop over strings O(n²) in het slechtste geval omdat strings onveranderlijk zijn en elke concatenatie het geheel kopieert. Gebruik in plaats daarvan ''.join(chunks) — het bouwt de string één keer op.

Sorteren als je dat niet nodig hebt. sorted() is O(n log n). Als je het in een loop aanroept om alleen de max of min elke iteratie te vinden, gebruik max()/min() (O(n)) of beter, een heap (heapq) als je het lopende uiterste herhaaldelijk nodig hebt. heapq.nlargest(k, data) is O(n log k), veel goedkoper dan de hele lijst sorteren als k klein is.

Recursieve functies zonder memoization. Naïeve recursieve Fibonacci is O(2ⁿ) omdat het dezelfde subproblemen steeds opnieuw berekent. Voeg functools.lru_cache toe en het daalt naar O(n):

from functools import lru_cache

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

Big O snel aflezen uit echte code

Tel geneste loops over dezelfde invoer — dat is meestal je exponent. Een enkele loop is O(n). Een loop in een loop is O(n²) tenzij het bereik van de binnenloop krimpt (zoals in bubble sort's geoptimaliseerde vorm, nog steeds O(n²) slechtste geval maar minder vergelijkingen). Recursieve oproepen die het probleem in tweeën splitsen, zoals binair zoeken of merge sort, wijzen op O(log n) of O(n log n). Recursieve oproepen die zich in meerdere oproepen per niveau vertakken, zoals naïeve Fibonacci, wijzen op exponentiële tijd — een sterk signaal dat je memoization of een iteratief herschrift nodig hebt.

Een goed gebruik: voordat je geneste loops of recursie over gebruikersdata schrijft, vraag jezelf af wat n in productie realistisch zou kunnen zijn, niet in je testbestand. Als n zes cijfers kan bereiken, moet een O(n²)-oplossing een tweede blik krijgen voordat het live gaat.

Voor meer over complexiteitsanalyse, sorteeralgoritmen en profileringsprogramma's, kijk in de Python- en Computer Science-secties op Korra Studio.