4. Hajautus

Hajautus (hashing) on tekniikka, jota käytetään usein tehokkaiden tietorakenteiden toteuttamisessa. Pythonissa tietorakenteet joukko (set) ja sanakirja (dict) perustuvat hajautukseen.

Tutustumme tässä luvussa hajautukseen perustuviin tietorakenteisiin ja niiden käyttämiseen algoritmien suunnittelussa. Lisäksi tutustumme tietorakenteiden taustalla olevaan teoriaan.

Joukko

Pythonin tietorakenne set eli joukko on hajautukseen perustuva tietorakenne, joka pitää yllä alkioiden joukkoa. Tietorakenne tarjoaa seuraavat operaatiot:

• metodi add lisää alkion joukkoon
• operaattori in tarkastaa, onko alkio joukossa
• metodi remove poistaa alkion joukosta

Joukko on toteutettu niin, että kaikki yllä olevat operaatiot tapahtuvat tehokkaasti ajassa \(O(1)\).

Esimerkki

Seuraava koodi luo joukon numbers ja lisää sinne alkioita metodilla add:

numbers = set()

numbers.add(1)
numbers.add(2)
numbers.add(3)

print(numbers) # {1, 2, 3}

Joukko voidaan myös luoda suoraan listan perusteella:

numbers = set([1, 2, 3])

print(numbers) # {1, 2, 3}

Operaattori in tarkastaa, kuuluuko tietty alkio joukkoon:

print(3 in numbers) # True
print(4 in numbers) # False

Metodi remove puolestaan poistaa alkion joukosta:

print(numbers) # {1, 2, 3}
numbers.remove(2)
print(numbers) # {1, 3}

Lista vs. joukko

Lista ja joukko ovat tietyllä tavalla samantapaisia tietorakenteita, koska molemmissa voi lisätä, etsiä ja poistaa alkioita. Kuitenkin tietorakenteiden tehokkuudessa ja ominaisuuksissa on suuria eroja.

Tehokkuus

Listassa alkion lisääminen on tehokasta, mutta on hidasta etsiä alkiota listasta sekä poistaa alkio listasta.

Joukossa on tehokasta lisätä alkio joukkoon, etsiä alkiota joukosta sekä poistaa alkio joukosta.

Indeksointi

Listassa alkioita voidaan käsitellä indeksien perusteella:

numbers = [1, 2, 3]
print(numbers[1]) # 2

Joukon alkioihin sen sijaan ei voida viitata indekseillä:

numbers = set([1, 2, 3])
print(numbers[1]) # TypeError: 'set' object is not subscriptable

Toistuvat alkiot

Listassa sama alkio voi esiintyä useita kertoja:

numbers = []

numbers.append(5)
numbers.append(5)
numbers.append(5)

print(numbers) # [5, 5, 5]

Joukossa sama alkio voi esiintyä enintään kerran. Jos alkio lisätään monta kertaa joukkoon, tällä ei ole vaikutusta:

numbers = set()

numbers.add(5)
numbers.add(5)
numbers.add(5)

print(numbers) # {5}

Esimerkki: Montako eri lukua?

Tehtävä

Hidas ratkaisu (lista)

Voisimme ratkaista tehtävän listan avulla seuraavasti:

def count_distinct(numbers):
    seen = []
    for x in numbers:
        if x not in seen:
            seen.append(x)
    return len(seen)

Algoritmi käy läpi luvut ja lisää luvun listaan seen, jos lukua ei ole vielä listassa. Lopuksi listan seen koko on yhtä suuri kuin eri lukujen määrä.

Tämä algoritmi on toimiva mutta ei tehokas, koska jokaisella silmukan kierroksella vie aikaa \(O(n)\) tarkastaa operaattorilla in, onko luku listassa. Tämän vuoksi algoritmin aikavaativuus on \(O(n^2)\). Algoritmia on kuitenkin helppoa parantaa käyttämällä listan sijasta joukkoa.

Tehokas ratkaisu (joukko)

Voimme ratkaista tehtävän tehokkaasti joukon avulla seuraavasti:

def count_distinct(numbers):
    seen = set()
    for x in numbers:
        if x not in seen:
            seen.add(x)
    return len(seen)

Funktio on muuten samanlainen kuin aiemmassa listaratkaisussa, mutta seen on nyt joukko ja alkiot lisätään metodilla add. Tällä muutoksella on suuri vaikutus algoritmin tehokkuuteen. Muutoksen jälkeen operaattori in vie aikaa \(O(1)\) ja algoritmin aikavaativuus on vain \(O(n)\).

Koodia on mahdollista vielä tiivistää käyttämällä hyväksi sitä, että sama alkio ei mene useita kertoja joukkoon. Tämän ansiosta koodista voi poistaa tarkastuksen, onko alkio valmiiksi joukossa:

def count_distinct(numbers):
    seen = set()
    for x in numbers:
        seen.add(x)
    return len(seen)

Itse asiassa koodia voi tiivistää vielä lisää luomalla joukon suoraan listan pohjalta. Funktion toteutukseen riittää loppujen lopuksi yksi rivi koodia:

def count_distinct(numbers):
    return len(set(numbers))

Sanakirja

Pythonin tietorakenne dict eli sanakirja on hajautukseen perustuva tietorakenne, johon voidaan tallentaa avain-arvo-pareja. Ideana on, että avaimen perusteella voidaan hakea siihen liittyvä arvo.

Sanakirjaa voi ajatella listan yleistyksenä: listassa avaimet ovat indeksit \(0 \dots n-1\), kun taas sanakirjassa avaimet voivat olla mitä tahansa alkioita. Tietoa voi lisätä, hakea ja poistaa tehokkaasti ajassa \(O(1)\) avaimen perusteella.

Esimerkki

Seuraava koodi luo sanakirjan weights, jossa avaimet ovat merkkijonoja ja arvot ovat lukuja.

weights = {}

weights["apina"] = 100
weights["banaani"] = 1
weights["cembalo"] = 500

Yllä olevan sanakirjan voi luoda myös näin:

weights = {"apina": 100, "banaani": 1, "cembalo": 500}

Sanakirjan arvoja voi käsitellä samaan tapaan kuin listan arvoja:

print(weights["apina"]) # 100
weights["apina"] = 150
print(weights["apina"]) # 150

Operaattori in tarkastaa, onko sanakirjassa tiettyä avainta:

print("apina" in weights) # True
print("ananas" in weights) # False

Komento del poistaa avaimen ja siihen liittyvän arvon sanakirjasta:

print(weights) # {'apina': 100, 'banaani': 1, 'cembalo': 500}
del weights["banaani"]
print(weights) # {'apina': 100, 'cembalo': 500}

Sanakirjan käyttäminen

Seuraavassa on kolme tavallista sanakirjan käyttötarkoitusta algoritmien suunnittelussa:

Onko alkio esiintynyt

Sanakirjaa voi käyttää joukon kaltaisesti pitämään kirjaa esiintyneistä alkioista:

seen = {}
for x in items:
    seen[x] = True

Tämä koodi on toiminnaltaan suunnilleen sama kuin seuraava koodi:

seen = set()
for x in items:
    seen.add(x)

Voikin ajatella, että joukko vastaa sanakirjaa, jossa avaimet ovat joukon alkioita ja jokainen arvo on True.

Alkion esiintymiskerrat

Tavallinen sanakirjan käyttötarkoitus on laskea, montako kertaa mikäkin alkio on esiintynyt.

count = {}
for x in items:
    if x not in count:
        count[x] = 0
    count[x] += 1

Koodi laskee esiintymiskerrat sanakirjan count avulla. Jos alkiota x ei ole vielä sanakirjassa, koodi asettaa sen esiintymiskertojen määräksi 0. Tämän jälkeen koodi kasvattaa alkion x esiintymiskertoja yhdellä.

Alkion esiintymiskohta

Joissakin algoritmeissa on hyödyllistä pitää yllä tietoa siitä, missä kohdassa mikäkin alkio on esiintynyt.

pos = {}
for i, x in enumerate(items):
    pos[x] = i

Tässä sanakirjassa pos on kunkin alkion viimeisin esiintymiskohta listassa. Funktion enumerate avulla lista voidaan käydä läpi niin, että joka kierroksella i sisältää alkion indeksin ja x itse alkion.

Esimerkki: Moodi

Tehtävä

Voimme ratkaista tehtävän tehokkaasti hajautuksen avulla luomalla sanakirjan, johon lasketaan jokaisen alkion esiintymiskertojen määrä:

def find_mode(numbers):
    count = {}
    mode = numbers[0]

    for x in numbers:
        if x not in count:
            count[x] = 0
        count[x] += 1

        if count[x] > count[mode]:
            mode = x

    return mode

Tässä count on sanakirja, johon lasketaan lukujen esiintymiskerrat, ja muuttuja mode sisältää moodin. Alussa mode on listan ensimmäinen luku ja muuttujaa päivitetään aina, kun viimeksi käsitelty luku on esiintynyt useammin kuin muuttujassa oleva luku. Koska sanakirjan operaatiot toimivat ajassa \(O(1)\), algoritmin aikavaativuus on \(O(n)\).

Tässä on vielä toinen tapa toteuttaa algoritmi:

def find_mode(numbers):
    count = {}
    mode = (0, 0)

    for x in numbers:
        if x not in count:
            count[x] = 0
        count[x] += 1

        mode = max(mode, (count[x], x))

    return mode[1]

Nyt muuttuja mode on pari, jonka ensimmäinen alkio on moodin esiintymiskerrat ja toinen alkio on itse moodi. Esimerkiksi jos muuttujan arvona on (5, 2), tämä tarkoittaa, että alkio 2 on esiintynyt 5 kertaa.

Tämän toteutuksen etuna on, että moodia pystyy päivittämään max-funktion avulla. Tässä max-funktio vertailee ensisijaisesti parin ensimmäistä alkiota ja toissijaisesti parin toista alkiota. Koska parin ensimmäinen alkio on esiintymiskertojen määrä, parin arvo on sitä suurempi mitä useammin luku on esiintynyt.

Huomaa, että yllä olevat kaksi funktiota toimivat vähän eri tavalla tilanteessa, jossa on useita mahdollisia vaihtoehtoja moodiksi. Ensimmäinen funktio valitsee moodin, jonka viimeinen esiintymiskerta tulee vastaan ensimmäisenä. Toinen funktio puolestaan valitsee moodin, joka on arvoltaan suurin, koska pareissa vertaillaan toissijaisesti luvun suuruutta.

Esimerkki: Kierrokset

Tehtävä

Oleellinen havainto on, että uusi kierros täytyy aloittaa aina silloin, kun kerättävä luku on edellisen kerätyn luvun vasemmalla puolella. Esimerkiksi yllä olevassa listassa luku \(3\) aloittaa uuden kierroksen, koska se on luvun \(2\) vasemmalla puolella.

Hidas ratkaisu (lista)

Seuraava algoritmi ratkaisee tehtävän käyttäen vain listaa:

def count_rounds(numbers):
    n = len(numbers)

    rounds = 1
    for i in range(1, n):
        if numbers.index(i + 1) < numbers.index(i):
            rounds += 1

    return rounds

Ideana on laskea muuttujaan rounds tarvittava kierrosten määrä. Alussa kierrosten määrä on yksi. Sitten silmukka käy läpi luvut \(1 \dots n-1\) ja lisää kierrosten määrää yhdellä aina, kun luku \(i+1\) esiintyy listassa ennen lukua \(i\).

Tässä toteutuksessa on käytössä listan metodi index, joka antaa luvun sijainnin listassa. Tämän takia algoritmi on kuitenkin hidas, koska metodi index vie aikaa \(O(n)\) ja koko algoritmin aikavaativuus on \(O(n^2)\).

Tehokas ratkaisu (sanakirja)

Voimme toteuttaa saman idean tehokkaasti ottamalla käyttöön sanakirjan, joka sisältää kunkin luvun kohdan listassa:

def count_rounds(numbers):
    n = len(numbers)

    pos = {}
    for i, x in enumerate(numbers):
        pos[x] = i

    rounds = 1
    for i in range(1, n):
        if pos[i + 1] < pos[i]:
            rounds += 1

    return rounds

Tämän jälkeen ei tarvitse käyttää metodia index vaan luvun sijainnin listasta saa haettua tehokkaasti sanakirjasta. Algoritmissa on kaksi silmukkaa, jotka toimivat molemmat ajassa \(O(n)\), joten koko algoritmin aikavaativuus on \(O(n)\).

Esimerkki: Soittolista

Tehtävä

Hyvä lähestymistapa tähän tehtävään on laskea jokaiseen soittolistan kohtaan, kuinka pitkä on pisin kyseiseen kohtaan päättyvä soittolistan osa, jossa ei esiinny kahta samaa laulua. Näistä pituuksista suurin on tehtävän haluttu vastaus. Äskeisessä esimerkissä nämä pituudet ovat:

Kun olemme tietyssä soittolistan kohdassa ja vastaan tulee aiemmin listalla esiintynyt laulu, tämä rajoittaa soittolistan osan pituutta, koska kyseinen laulu ei saa esiintyä kahta kertaa. Niinpä soittolistan osan tulee alkaa laulun edellisen esiintymän jälkeen. Tämän avulla voimme päätellä, mistä kohdasta soittolistan osa voi alkaa.

Seuraava tehokas algoritmi perustuu yllä oleviin ideoihin:

def max_length(songs):
    n = len(songs)

    pos = {}
    start = 0
    length = 0

    for i, song in enumerate(songs):
        if song in pos:
            start = max(start, pos[song] + 1)
        length = max(length, i - start + 1)
        pos[song] = i

    return length

Sanakirja pos kertoo kustakin laulusta, missä kohtaa soittolistaa laulu on esiintynyt viimeksi. Muuttujassa start on kohta, josta soittolistan osa voi alkaa, ja muuttujassa length on pisin soittolistan osan pituus.

Algoritmi käy läpi soittolistan ja päivittää muuttujaa start aina, kun vastaan tulee laulu, joka on esiintynyt aiemmin soittolistalla. Tässä tilanteessa muuttujan start arvo kasvaa, jos laulun edellisen esiintymän kohta on aiempaa suurempi.

Tuloksena oleva algoritmi toimii ajassa \(O(n)\) hajautuksen ansiosta.

Esimerkki: Listan summat

Tehtävä

Hyödyllinen tekniikka tällaisessa tehtävässä on tarkastella listan alkuosien lukujen summia eli laskea jokaiseen kohtaan lukujen summa listan alusta kyseiseen kohtaan. Esimerkissä alkuosien summat ovat seuraavat:

Esimerkiksi kohdassa \(4\) alkuosan summa on \(11\), koska listan lukujen summa kohdasta \(0\) kohtaan \(4\) on \(2+3+5-3+4=11\).

Alkuosien summien hyötynä on, että minkä tahansa osalistan lukujen summa saadaan laskettua kahden alkuosan summan perusteella. Kun osalista alkaa kohdasta \(a\) ja päättyy kohtaan \(b\), sen lukujen summa saadaan laskemalla alkuosan summa kohtaan \(b\) ja vähentämällä siitä alkuosan summa kohtaan \(a-1\).

Esimerkiksi kun osalista alkaa kohdasta \(2\) ja päättyy kohtaan \(4\), sen lukujen summa on \(5-3+4=6\). Tämä on yhtä suuri kuin alkuosan summa kohtaan \(4\), josta on vähennetty alkuosan summa kohtaan \(1\), eli \(11-5=6\).

Oletetaan nyt, että olemme listan kohdassa \(i\) ja haluamme laskea, monessako kohtaan \(i\) päättyvässä osalistassa lukujen summa on \(x\). Kun alkuosan summa kohdassa \(i\) on \(p\), alkuosan summan tulee olla \(p-x\) aiemmassa kohdassa, jotta osalistan summaksi tulee \(p-(p-x)=x\). Niinpä haluttuja osalistoja on yhtä monta kun aiempia kohtia, joissa alkuosan summa on \(p-x\).

Seuraava algoritmi perustuu yllä olevaan ideaan:

def count_sublists(numbers, x):
    count = {0: 1}
    prefix_sum = 0
    result = 0

    for i in range(len(numbers)):
        prefix_sum += numbers[i]
        if prefix_sum - x in count:
            result += count[prefix_sum - x]

        if prefix_sum not in count:
            count[prefix_sum] = 0
        count[prefix_sum] += 1

    return result

Tässä sanakirjaan count lasketaan, montako kertaa mikäkin summa on esiintynyt listan alkuosien summissa. Sanakirjan avulla voidaan laskea tehokkaasti jokaiseen listaan kohtaan, monessako kyseiseen kohtaan päättyvässä osalistassa summa on \(x\). Sanakirjassa on valmiina tyhjää listaa tarkoittava summa \(0\), jotta algoritmi laskee oikein myös tapaukset, joissa osalista alkaa listan alusta.

Tuloksena oleva algoritmi toimii ajassa \(O(n)\) hajautuksen ansiosta.

Miten hajautus toimii?

Tässä luvussa esitellyt Pythonin tietorakenteet set ja dict perustuvat hajautukseen ja niiden taustalla on tietorakenne hajautustaulu. Pythonissa hajautustaulu on toteuttu avointa hajautusta käyttäen.

Pythonissa on sisäänrakennettu funktio hash, jolla voidaan laskea alkion hajautusarvo. Python kutsuu tätä funktiota, kun se määrittää alkion sijainnin hajautustaulussa. Funktion toimintaa voi testata näin:

> hash(42)
42
> hash(10**100)
910685213754167845
> hash("apina")
4992529190565255982

Kuten yllä olevasta testistä voi havaita, Pythonissa pienen kokonaisluvun hajautusarvo on suoraan kyseinen luku. Muuten hajautusarvot ovat yleensä satunnaisen näköisiä lukuja.

Pythonissa hajautusta käyttävät tietorakenteet toimivat yleensä aina tehokkaasti ja voidaan olettaa, että lisäykset, haut ja poistot vievät aikaa \(O(1)\). Silti on mahdollista, että Pythonin hajautus toimii hitaasti, jos syöte on valittu sopivalla tavalla.

Mitä voi hajauttaa?

Seuraava koodi ei toimi Pythonissa:

lists = set()
lists.add([1, 2, 3]) # TypeError: unhashable type: 'list'

Ongelmana on, että listalle ei voi laskea hajautusarvoa:

print(hash([1, 2, 3])) # TypeError: unhashable type: 'list'

Pythonissa on periaatteena, että hajautusarvon voi laskea vain oliolle, jonka sisältö on muuttumaton (immutable). Listan sisältö ei ole muuttumaton, koska listassa on esimerkiksi metodi append, joka lisää siihen uuden alkion. Tämän vuoksi listalle ei voi laskea hajautusarvoa.

Muuttumattomia olioita ovat esimerkiksi luvut, merkkijonot ja näitä sisältävät tuplet. Esimerkiksi seuraava koodi toimii, koska lukuja sisältävä tuple on muuttumaton ja sille voidaan laskea hajautusarvo:

lists = set()
lists.add((1, 2, 3))

Huomaa, että sanakirjassa vain avaimelle lasketaan hajautusarvo. Tämän takia myös seuraava koodi toimii, jossa avain on merkkijono ja arvo on lista:

lists = {}
lists["apina"] = [1, 2, 3]

Oma luokka hajautuksessa

Omaa luokkaa voi käyttää hajautuksessa määrittelemällä sille seuraavat metodit:

• __hash__: palauttaa olion hajautusarvon (funktio hash kutsuu sitä)
• __eq__: vertailee, onko olion sisältö sama kuin toisen olion sisältö (operaattori == kutsuu sitä)

Seuraavassa on esimerkki metodien määrittelystä. Tässä metodi __hash__ palauttaa olion sisältöä vastaavan tuplen hajautusarvon.

class Location:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __hash__(self):
        return hash((self.x, self.y))

    def __eq__(self, other):
        return (self.x, self.y) == (other.x, other.y)

Tämän jälkeen esimerkiksi seuraava koodi toimii tarkoitetulla tavalla:

locations = set()
locations.add(Location(1, 2))
locations.add(Location(3, -5))
locations.add(Location(1, 4))

Hajautus muissa kielissä

Hajautusta käyttävät tietorakenteet ovat yleisiä eri ohjelmointikielissä. Monissa kielissä Pythonin sanakirjaa vastaa tietorakenne nimeltä map, josta voidaan käyttää suomeksi nimeä hakemisto.

C++:ssa tietorakenteet std::unordered_set ja std::unordered_map toteuttavat hajautusta käyttävän joukon ja hakemiston.

std::unordered_set<int> numbers;

numbers.add(1);
numbers.add(2);
numbers.add(3);

std::unordered_map<std::string, int> weights;

weights["apina"] = 100;
weights["banaani"] = 1;
weights["cembalo"] = 500;

Javassa vastaavat tietorakenteet ovat HashSet ja HashMap:

HashSet<Integer> numbers = new HashSet<Integer>();

numbers.add(1);
numbers.add(2);
numbers.add(3);

HashMap<String, Integer> weights = new HashMap<String, Integer>();

weights.put("apina", 100);
weights.put("banaani", 1);
weights.put("cembalo", 500);

JavaScriptissä tietorakenne Set toteuttaa joukon:

let numbers = new Set();

numbers.add(1);
numbers.add(2);
numbers.add(3);

JavaScriptin perinteinen tapa luoda hakemisto on määritellä olio:

let weights = {};

weights["apina"] = 100;
weights["banaani"] = 1;
weights["cembalo"] = 500;

Uudempi tapa on käyttää erillistä tietorakennetta Map:

let weights = new Map();

weights.set("apina", 100);
weights.set("banaani", 1);
weights.set("cembalo", 500);