Datastrukturer

En tabell slår opp element nummer $i$ på konstant tid, men å sette inn et element forrest krever at alle de andre flyttes. En lenket liste setter inn forrest på konstant tid, men må følge pekere for å finne element nummer $i$. Begge lagrer de samme elementene; det som er billig i den ene, er dyrt i den andre.

Minne, pekere og tabeller

Minnet er én lang rekke celler med hver sin adresse. En peker er en variabel som inneholder en slik adresse, altså bare et heltall som tolkes som en posisjon i minnet.

En endimensjonal tabell ligger som en sammenhengende blokk. Har blokken startadresse $a$, elementbredde $b$ og startindeks $s$, ligger element $s$ på adressen $a$, og hvert steg i indeksen flytter adressen $b$ celler. Element $i$ ligger $i - s$ steg etter element $s$, altså på adressen $a + b(i - s)$. Oppslaget er ett gangestykke og én addisjon uansett hvor stor tabellen er, og derfor koster indeksering konstant tid i RAM-modellen.

En matrise må også ned i det samme endimensjonale minnet. Radvis lagring legger rad 1, så rad 2, og så videre. Foran rad $i$ ligger da $i - 1$ hele rader med $c$ elementer hver, og foran $M[i, j]$ i rad $i$ ligger $j - 1$ elementer, så $M[i, j]$ i en matrise med $c$ kolonner ligger på plass $c(i - 1) + (j - 1) + 1$. Kolonnevis lagring legger kolonnene etter hverandre i stedet. Et tredje alternativ er én tabell per rad, med en tabell av pekere øverst; da kan radene ha ulik lengde, såkalte jagged arrays. Alle strategiene kan utvides til flere dimensjoner.

Stakker og køer

En stakk er sist inn, først ut: alt skjer på toppen. Strukturen er en tabell og en toppindeks, der Push legger et element på toppen og Pop tar av det øverste, begge i konstant tid. Push på en full tabell gir overflyt, Pop på en tom gir underflyt. Kallstakken i et kjørende program er nettopp en slik stakk.

En kø er først inn, først ut, med innsetting bakerst og uttak forrest. Legger du køen rett inn i en tabell, må alt flyttes hver gang noen går ut forrest. Ringbufferen unngår det med to indekser som rykker fremover: head peker på den første i køen og tail på neste ledige plass, og når en av dem passerer enden, går den rundt til starten igjen.

class Queue:
  def __init__(self, m):
      self.A = [None] * m
      self.head = 0  # først i køen
      self.tail = 0  # neste ledige plass

  def enqueue(self, x):
      self.A[self.tail] = x
      self.tail = (self.tail + 1) % len(self.A)  # rundt til 0 etter siste plass

  def dequeue(self):
      x = self.A[self.head]
      self.head = (self.head + 1) % len(self.A)
      return x

Testene for over- og underflyt er sløyfet her, som i læreboka. De trengs i praksis: med bare head og tail ser en helt full kø ellers lik ut som en tom.

1 Q[Q.tail] = x
2 if Q.tail == Q.size
3
4 else Q.tail = Q.tail + 1

Dynamiske mengder

Mange algoritmer trenger bare å holde styr på en samling elementer med nøkler: sett inn, slett og søk, og når nøklene har en ordning, også minste, største, forgjenger og etterfølger. Dette kalles en dynamisk mengde, og det er funksjonalitet, ikke en bestemt datastruktur. Finnes ikke elementet du spør etter, returneres NIL. Problemstørrelsen er vanligvis antallet elementer i mengden.

En vanlig tabell kan levere funksjonaliteten, med priser som avhenger av om tabellen holdes sortert. Usortert er innsetting og sletting konstant tid, mens søk og minimum må gjennom alt. Sortert blir søket logaritmisk med binærsøk og minimum konstant, men innsetting og sletting må flytte elementer og blir lineære. En lenket liste setter inn og sletter midt i en rekkefølge uten å flytte noe, og har ingen fast størrelse. En hashtabell gjør søket forventet konstant. For de ordnede operasjonene er søketrær verktøyet.

Lenkede lister

En lenket liste består av noder som peker på neste node, og i en dobbeltlenket liste også på forrige. Lista selv er bare en peker til hodet.

Søk følger pekerne fra hodet til nøkkelen dukker opp eller lista tar slutt, og koster $\Theta(n)$ i verste fall. Til gjengjeld er innsetting og sletting konstant tid, for nodene blir liggende der de er, og bare pekerne endres. Å sette inn en node etter en annen er fire pekertilordninger; å slette en node er to, der naboene settes til å peke på hverandre og noden hoppes over. Konstant tid forutsetter at du allerede står ved noden. Skal den først finnes, betaler du det lineære søket i tillegg.

def insert_after(a, x):
  x.prev = a
  x.next = a.next
  a.next.prev = x
  a.next = x

def delete(x):
  x.prev.next = x.next
  x.next.prev = x.prev

Grensetilfellene er sløyfet her også: står noden først eller sist i lista, finnes bare den ene naboen.

Hashtabeller

Den enkleste formen for oppslag er direkte adressering: bruk nøkkelen selv som indeks, slik at $T[k]$ inneholder elementet med nøkkel $k$. Søk, innsetting og sletting er én tabelloperasjon hver. Prisen er at tabellen må være like stor som mengden av mulige nøkler, ikke antallet du faktisk lagrer.

En hashtabell beholder ideen, men kjører nøkkelen gjennom en hashfunksjon $h$ som krymper den til en gyldig indeks $0, \ldots, m-1$. Den enkleste er $h(k) = k \bmod m$. I praksis brukes gjerne funksjoner som blander bitene bedre, som multipliser-og-skift, og strenger hashes ved å kombinere tegnene aritmetisk. En god hashfunksjon gir alltid samme indeks for samme nøkkel, sprer nøklene så indeksene ser tilfeldig fordelt ut og regnes ut i konstant tid.

Med flere mulige nøkler enn plasser må to nøkler før eller siden dele indeks, en kollisjon. Kjeding løser det ved å la hver plass i tabellen holde en lenket liste. Innsetting setter elementet forrest i lista på plass $h(k)$ og koster $\Theta(1)$; søk hasher nøkkelen og leter lineært gjennom lista på plassen.

Å regne ut $h(k)$ og slå opp plassen tar konstant tid, så resten av søket er letingen gjennom lista på plassen. Fordeler hashfunksjonen nøklene jevnt og uavhengig, får hver av de $m$ listene i snitt $n/m$ elementer. Det tallet er belastningsfaktoren $\alpha = n/m$. Et søk som ikke finner nøkkelen, går gjennom en hel liste, forventet $\alpha$ elementer, så søket tar forventet $\Theta(1 + \alpha)$ tid. Et søk som finner nøkkelen, stopper i snitt omtrent halvveis i lista og har samme grense.

Forventningen er ingen garanti. Ingenting hindrer at alle $n$ nøklene havner på samme plass, og da er søket et lineært søk i én liste, $\Theta(n)$.

Regneeksempel Kjeding med $h(k) = k \bmod 7$

Sett inn nøklene 19, 36, 5, 21 og 12, i den rekkefølgen, i en tom hashtabell med $m = 7$ plasser og kjeding. Hvor havner nøklene, og hvor mange nøkler må et søk etter 19 sammenligne?

Vis løsning Skjul løsning

$19 \bmod 7 = 5$, $36 \bmod 7 = 1$, $5 \bmod 7 = 5$, $21 \bmod 7 = 0$ og $12 \bmod 7 = 5$. Plass 0 får 21 og plass 1 får 36, mens 19, 5 og 12 alle havner på plass 5. Innsetting skjer forrest i lista, så kjeden på plass 5 blir $12 \to 5 \to 19$, med den sist innsatte nøkkelen først. Et søk etter 19 hasher til plass 5 og må gjennom hele kjeden: først 12, så 5, så 19.

Svar

21 på plass 0, 36 på plass 1 og kjeden $12 \to 5 \to 19$ på plass 5. Søket etter 19 sammenligner tre nøkler.

Er nøkkelmengden statisk, kjent på forhånd og uforanderlig, kan du bygge en tabell der ingen nøkler kolliderer. Det kalles perfekt hashing og gir søk i garantert konstant tid, ikke bare forventet. Et typisk bruksområde er de reserverte ordene i en kompilator.

Tabellen har to nivåer. Først hashes de $n$ nøklene inn i $m = n$ plasser, med kollisjoner som vanlig. Plass $j$, som fikk $n_j$ nøkler, får så sin egen sekundærtabell med $n_j^2$ plasser og sin egen hashfunksjon, valgt slik at ingen av de $n_j$ nøklene kolliderer der. En slik funksjon er lett å finne. De $n_j$ nøklene danner færre enn $n_j^2/2$ par. Trekkes funksjonen tilfeldig fra en familie der hvert par kolliderer med sannsynlighet høyst $1/n_j^2$, er forventet antall kollisjoner derfor under $\tfrac12$. Da er sannsynligheten for minst én kollisjon også under $\tfrac12$, siden hver trekning med kollisjon bidrar med minst 1 til forventningen. Du trekker på nytt til funksjonen er kollisjonsfri, i snitt færre enn to ganger.

Et søk regner ut to hashverdier og sammenligner med én nøkkel, så det tar konstant tid uansett input. Sekundærtabeller på $n_j^2$ plasser ser dyre ut, men med en jevn fordeling på første nivå er summen av alle $n_j^2$ forventet under $2n$, så tabellene tar $O(n)$ plass til sammen.

Kostnadene så langt, samlet:

Dynamiske tabeller

Blir en stakk eller en kø full, må den få mer plass: alloker en større tabell, kopier alt over, og fortsett der. En hashtabell med kjeding blir aldri full, men $\alpha = n/m$ vokser med $n$, så den trenger også en større tabell for at søket skal holde seg forventet konstant. Ved utvidelsen hashes hver nøkkel på nytt med en funksjon for den nye størrelsen, i konstant tid per nøkkel, så den koster like mye som en kopiering. Kopieringen tar lineær tid, så den bør skje sjelden. Med tabelldobling allokeres dobbelt så stor plass hver gang tabellen er full, eller for hashtabellen hver gang $\alpha$ når en fast grense.

Én enkelt innsetting kan da koste lineær tid, men de dyre innsettingene blir sjeldnere jo større tabellen blir. Tell derfor det totale arbeidet over mange innsettinger.

For $n$ innsettinger skjer kopieringen ved størrelsene $1, 2, 4, \ldots, 2^j$, der $2^j$ er den største toerpotensen under $n$. Kopieringsarbeidet er da $1 + 2 + \cdots + 2^j = 2^{j+1} - 1$, og det er mindre enn $2n$, ettersom $2^j < n$. Med de $n$ skrivingene i tillegg blir totalen under $3n$, så hver innsetting koster i snitt færre enn 3 operasjoner. For $n = 16$ gir grensen $48$, og tellingen over ga $31$.

Å regne ut det totale arbeidet for en hel operasjonsfølge og dele på antallet operasjoner heter aggregert analyse. Det er den enkleste formen for amortisert analyse, og den viser at tabelldobling koster amortisert konstant tid per innsetting. Analysen antok ingen sannsynlighet og ingen snill input: amortisert kjøretid er et snitt over operasjonene i én følge, i verste fall. Gjennomsnittstilfellet er noe annet, et snitt over instanser med en sannsynlighetsfordeling.

Sjekk deg selv