Mer om tupler och dictionaries

För dig som är nyfiken på att lära dig mer om tupler och dictionaries kommer här lite extramaterial.

1. Intern lagring av dictionaries

Hur ska en dictionary lagras? Man skulle kunna tänka sig att ha en lista av par:

tabell = [("x", 12), ("c", 34), ("b", 56)]

För att söka upp ett värde skulle vi då behöva söka igenom hela listan från början till slut. Och det skulle vi behöva göra varje gång. Med 100 eller 10000 olika nycklar i listan kan det ta lång tid.

Dictionaries implementeras i stället som så kallade hashtabeller. Grundtanken är att det finns en algoritm som beräknar ett hashvärde för varje nyckel. Python har en inbyggd sådan som finns via en intern metod:

>>> "x".__hash__()
8116367903174400156
>>> "c".__hash__()
-9064716270301218589
>>> "b".__hash__()
-330292164206847844

De här hashvärdena kan dock bli rätt stora. För att få dem till lite mer hanterbar storlek kan vi skära ner dem. Exakt hur mycket vi behöver skära ner dem beror förstås på hur stor tabell vi har, men det skulle kunna funka så här:

>>> "x".__hash__() % 7
0
>>> "c".__hash__() % 7
1
>>> "b".__hash__() % 7
6

Detta mer hanterbara värde kan sedan användas som ett sorts internt index för att snabbt veta var man ska placera ett värde i en intern tabell. Det finns en del mer komplikationer att ta hand om, bland annat eftersom det kan hända att flera olika nycklar får samma hashvärde, men det kommer att diskuteras i en senare kurs om datastrukturer. Just nu räcker det att veta att ett hashvärde behöver kunna beräknas.

I andra språk kan strukturer som liknar dictionaries även kallas för hash map, map och associativa arrayer.

Läs mer om hur Python beräkar hashvärden i Python-dokumentationen.

2. Namngivna tupler

Python har också en typ namedtuple som kan användas för att skapa en form av tupler med namngivna fält (som fortfarande är icke ändringsbara). Här kommer man på ett relativt enkelt sätt närmare många andra språks record-typer där man också skriver person.name och inte person["name"] för att komma åt information.

from collections import namedtuple

# Vi skapar en ny sorts tupel med namnet "Person"
# och plats för värden med namn "name", "born" och "city"
Person = namedtuple('Person', 'name born city')

# Skapa en ny person
person = Person(name="Jonas", born=1973, city=Linköping)
print(person.name)

Läs mer i Python-dokumentationen.