Datastrukturer: listor, stackar, köer, hashtabeller

En datastruktur är ett sätt att lägga saker så att just de operationer du behöver blir snabba. Det finns ingen som är bäst på allt.

Den viktigaste insikten: att leta i en lista med en miljon element tar en miljon jämförelser. Att slå upp i en dictionary med en miljon nycklar tar ungefär en. Skillnaden är inte «lite snabbare» — den är hela skillnaden mellan att koden går att köra och inte.

Komplexitet för de vanliga operationerna:

* amorterat: listan växer ibland om, men kostnaden fördelas.

Hur en hashtabell fungerar. En hashfunktion räknar om nyckeln till ett tal, och talet pekar ut en plats i en array. Att slå upp blir alltså «räkna ut talet, gå direkt dit» — oberoende av hur många element som finns.

Två nycklar kan hamna på samma plats (kollision). Det löses med kedjor eller omprövning, och därför är O(1) ett genomsnitt, inte en garanti. I värsta fall blir det O(n), men med en bra hashfunktion händer det praktiskt taget aldrig.

Priset: nycklarna måste vara hashbara, alltså oföränderliga. Därför kan en lista inte vara nyckel i en dict — men en tupel kan.

Det vanligaste prestandafelet i Python-kod är att söka i en lista inne i en loop:

for x in stora_listan:          # n gånger
    if x in annan_lista:        # n jämförelser var gång  → O(n²)

En rad räcker för att fixa det: annan_mangd = set(annan_lista) före loopen. Med n = 10 000 går det från cirka 50 miljoner jämförelser till 10 000.

import time
from collections import deque, Counter, defaultdict

n = 200_000
lista = list(range(n))
mangd = set(lista)

def tid(f):
    t = time.perf_counter(); f(); return (time.perf_counter() - t) * 1000

print(f"lista: {tid(lambda: [n - 1 in lista for _ in range(100)]):.1f} ms")
print(f"set:   {tid(lambda: [n - 1 in mangd for _ in range(100)]):.1f} ms")
# lista: 210.4 ms
# set:     0.0 ms      ← samma fråga, ~10 000 gånger snabbare

# Stack: sist in, först ut
stack = []
stack.append("a"); stack.append("b")
print(stack.pop())                      # b

# Kö: använd deque, inte lista — list.pop(0) är O(n)
ko = deque(["a", "b"])
ko.append("c")
print(ko.popleft())                     # a

# Två dict-verktyg som sparar mycket kod
ord_ = "ett två ett tre två ett".split()
print(Counter(ord_).most_common(2))     # [('ett', 3), ('två', 2)]

grupper = defaultdict(list)
for namn, klass in [("Ada", "7A"), ("Bo", "7B"), ("Cim", "7A")]:
    grupper[klass].append(namn)
print(dict(grupper))                    # {'7A': ['Ada', 'Cim'], '7B': ['Bo']}

# Nycklar måste vara hashbara
d = {("rad", 1): "värde"}               # tupel går bra
try:
    d[["rad", 1]] = "värde"             # lista går inte
except TypeError as e:
    print(e)                            # unhashable type: 'list'