6. Omat tietorakenteet

Tietorakenteen toiminta voidaan esittää joukkona metodeita, joilla on tietyt parametrit ja joiden kutsuminen antaa tietyn tuloksen. Esimerkiksi Pythonin listassa on metodit append, count ja index, joiden avulla pystyy lisäämään alkion listaan, laskemaan alkion esiintymiskerrat sekä etsimään alkion indeksin.

Luokkien avulla voimme toteuttaa itse tietorakenteita, jotka sisältävät haluttuja metodeja. Usein tällaisen luokan sisällä on jokin Pythonin tietorakenne, kuten lista tai sanakirja. Luokan etuna on, että se tarjoaa tietorakenteelle siistin rajapinnan, jonka takana on tietorakenteen sisäinen toteutus.

Esimerkki: Pino

Tehtävä

Luokka Stack on helppoa toteuttaa Pythonin listan avulla, koska alkion lisääminen listan loppuun ja poistaminen listan lopusta toimivat ajassa \(O(1)\). Voimme toteuttaa luokan seuraavasti:

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, x):
        self.stack.append(x)

    def top(self):
        return self.stack[-1]

    def pop(self):
        self.stack.pop()

Ideana on, että luokan sisällä määritellään lista stack, johon tallennetaan pinon alkiot. Metodit push ja pop toteutetaan listan metodien append ja pop avulla ja metodi top toteutetaan hakemalla listan viimeinen alkio.

Seuraava koodi testaa luokan toimintaa:

s = Stack()
s.push(1)
s.push(2)
s.push(3)
print(s.top()) # 3
print(s.top()) # 3
s.pop()
print(s.top()) # 2

Tässä tapauksessa luokka Stack rajoittaa listan toimintaa, koska luokan metodeilla on mahdollista käsitellä vain listan viimeistä alkiota. Luokan käyttäjän ei tarvitse tietää, miten luokka on toteutettu sisäisesti, vaan hän voi luottaa siihen, että saatavilla on metodit push, top ja pop.

Huomaa, että voimme kuitenkin käsitellä luokan sisäistä tietoa, jos tiedämme, miten luokka on toteutettu. Seuraava koodi havainnollistaa asiaa:

s = Stack()
s.push(1)
s.push(2)
s.push(3)
print(s.stack) # [1, 2, 3]

Luokka tallentaa sisäisesti pinon sisällön listaan stack, jonka sisältöön pääsee käsiksi, vaikka luokan metodeilla voi käsitellä vain pinon ylintä alkiota.

Älä tee luokkaa näin

Seuraava tapa luokan toteuttamiseen ei ole toimiva:

class Stack:
    stack = []

    def push(self, x):
        self.stack.append(x)

    def top(self):
        return self.stack[-1]

    def pop(self):
        self.stack.pop()

Erona aiempaan luokkaan tässä luokassa ei ole alustusmetodia __init__ vaan lista stack luodaan luokan päätasolla. Päältä päin luokka vaikuttaa toimivalta:

s = Stack()
s.push(1)
s.push(2)
s.push(3)
print(s.top()) # 3

Ongelmana tässä toteutuksessa on kuitenkin, että lista stack on yhteinen kaikille luokasta luoduille olioille. Seuraava koodi havainnollistaa ongelmaa:

a = Stack()
b = Stack()
a.push(1)
b.push(2)
print(a.top()) # 2

Koodi lisää pinoon a luvun 1 ja pinoon b luvun 2. Tämän jälkeen koodi hakee pinon a ylimmän alkion. Tuloksen pitäisi olla 1, mutta se onkin 2, koska pinoilla on yhteinen lista stack. Tämän seurauksena alkion lisääminen toiseen pinoon lisää sen kumpaankin pinoon eikä luokka toimi halutulla tavalla.

Lisää ominaisuuksia luokkaan

Aiempi luokka Stack toimii sinänsä, mutta siinä on vielä joitakin puutteita. Ensinnäkään pinon sisällön tulostaminen ei anna hyödyllistä tietoa:

s = Stack()
s.push(1)
s.push(2)
s.push(3)
print(s) # <__main__.Stack object at 0x7fd6c4e23ee0>

Voimme korjata tämän lisäämällä luokkaan metodin __repr__, jonka tehtävänä on palauttaa tekstimuotoinen esitys luokan sisällöstä. Voimme toteuttaa metodin niin, että se palauttaa suoraan listan stack sisällön tekstinä:

    def __repr__(self):
        return str(self.stack)

Tämän muutoksen jälkeen pinon sisältö tulostuu näin:

s = Stack()
s.push(1)
s.push(2)
s.push(3)
print(s) # [1, 2, 3]

Toinen puute on, että pinon kokoa ei pysty selvittämään funktiolla len, vaan tämä aiheuttaa virheilmoituksen. Voimme korjata tämän lisäämällä luokkaan seuraavan metodin __len__:

    def __len__(self):
        return len(self.stack)

Metodia __len__ kutsutaan silloin, kun luokasta tehty olio annetaan funktion len parametriksi. Tässä tapauksessa metodin riittää palauttaa listan stack koko. Nyt seuraava koodi toimii järkevällä tavalla:

s = Stack()
s.push(1)
s.push(2)
s.push(3)
print(len(s)) # 3

Metodeissa pop ja top on vielä puutteena, että ne eivät ota huomioon tilannetta, jossa pino on tyhjä. Tässä tilanteessa ei ole mahdollista poistaa tai hakea pinon ylintä alkiota. Voimme lisätä metodeihin virheenkäsittelyn seuraavasti:

    def pop(self):
        if len(self.stack) == 0:
            raise IndexError("pop from empty stack")
        return self.stack.pop()

    def top(self):
        if len(self.stack) == 0:
            raise IndexError("top from empty stack")
        return self.stack[-1]

Nyt jos metodeita kutsutaan pinon ollessa tyhjä, metodit tuottavat IndexError-virheen, jossa on tekstimuotoinen kuvaus virheen syystä. Seuraava koodi havainnollistaa asiaa:

s = Stack()
s.push(1)
s.pop()
s.pop() # IndexError: pop from empty stack

Esimerkki: Tehokas lisäys

Tehtävä

Tämä luokka vasta muuten aiempaa luokkaa Stack, mutta siinä on uusi metodi push_many, jonka avulla voi lisätä saman alkion useita kertoja pinoon. Luokan toteutuksessa on haasteena, että myös metodin push_many tulee toimia ajassa \(O(1)\) riippumatta siitä, miten monta kertaa alkio lisätään.

Seuraava tapa toteuttaa metodi push_many ei ole riittävä:

    def push_many(self, x, k):
        for i in range(k):
            self.push(x)

Tässä ongelmana on, että metodissa on silmukka, joka vie aikaa \(O(k)\), eli metodin suoritusaika riippuu siitä, montako kertaa alkio lisätään. Kuitenkin aikavaativuuden tulisi olla \(O(1)\) eli metodissa ei saa olla silmukkaa.

Hyödyllinen näkökulma luokan suunnittelussa on, että luokan ainoa vaatimus on toteuttaa halutut operaatiot ajassa \(O(1)\). Muilta osin voimme päättää vapaasti, millainen on luokan sisäinen toteutus. Erityisesti luokan ei ole pakko tallentaa jokaista alkiota erikseen pinoon, vaan sen riittää antaa vaikutelma tällaisesta pinosta.

Tehokas tapa toteuttaa luokka on tallentaa pinoon sisäisesti pareja muotoa \((k,x)\): alkio \(x\) esiintyy \(k\) kertaa. Esimerkiksi koodi

s = SuperStack()
s.push_many(3, 8)
s.push(4)
s.push_many(2, 5)

luo pinon \([(3,8),(1,4),(2,5)]\), joka esittää tiivistetyssä muodossa pinon \([8,8,8,4,5,5]\) sisällön. Tämän ansiosta jokainen metodin push tai push_many kutsu lisää vain yhden alkion pinoon. Vastaavasti metodit top ja pop täytyy toteuttaa niin, että ne käsittelevät oikealla tavalla pinossa olevia pareja. Luokka voidaan toteuttaa seuraavasti:

class SuperStack:
    def __init__(self):
        self.stack = []

    def push(self, x):
        self.stack.append((1, x))

    def push_many(self, k, x):
        self.stack.append((k, x))

    def top(self):
        return self.stack[-1][1]

    def pop(self):
        last = self.stack[-1]
        if last[0] == 1:
            self.stack.pop()
        else
            self.stack[-1] = (last[0] - 1, last[1])

Metodi top palauttaa pinon ylimmän parin toisen jäsenen, koska jokaisen parin toinen jäsen vastaa pinossa olevaa alkiota. Metodi pop puolestaan tarkastelee pinon ylimmän parin ensimmäistä jäsentä eli toistokertojen määrää. Jos alkio toistuu kerran, metodi poistaa parin pinosta. Jos taas alkio toistuu useamman kerran, metodi vähentää toistokertojen määrää yhdellä.

Tämän toteutuksen ansiosta jokainen luokan metodi toimii ajassa \(O(1)\), koska jokaisessa metodissa on kiinteä määrä komentoja eikä silmukoita.

Esimerkki: Moodi

Tehtävä

Tämä on muunnelma aiemmasta tehtävästä, jossa laskettavana oli annetun listan lukujen moodi. Erona on, että luokan Mode avulla voi vuorotellen lisätä lukuja listalle sekä kysyä, mikä on tähän mennessä lisättyjen lukujen moodi. Esimerkiksi luokkaa voidaan käyttää näin:

m = Mode()
m.add(1)
m.add(1)
m.add(2)
print(m.mode()) # 1
m.add(2)
m.add(2)
print(m.mode()) # 2

Koska ainoa luokalta kysyttävä asia on listan lukujen moodi, meidän ei tarvitse tallentaa muistiin listaa vaan vain tarvittavat tiedot moodin laskemiseen. Voimme toteuttaa luokan käyttäen sanakirjaa, johon on tallennettu jokaisen luvun esiintymiskertojen määrä. Lisäksi luokassa on muistissa tämänhetkinen moodi.

class Mode:
    def __init__(self):
        self.count = {}
        self.status = (0, 0)

    def add(self, x):
        if x not in self.count:
            self.count[x] = 0
        self.count[x] += 1
        self.status = max(self.status, (self.count[x], x))

    def mode(self):
        return self.status[1]

Sanakirja count sisältää kunkin luvun esiintymiskerran, ja parissa status on tieto moodista muodossa \((k,x)\): moodi on luku \(x\), joka esiintyy listassa \(k\) kertaa. Kun listalle lisätään luku \(x\), moodia päivitetään, jos luku \(x\) on lisäämisen jälkeen listan moodi. Tämä onnistuu kätevästi max-funktion avulla, joka vertaa ensisijaisesti parin ensimmäistä jäsentä ja toissijaisesti toista jäsentä.

Luokan kummassakin metodissa on vain yksittäisiä komentoja, joten ne toimivat vaatimusten mukaisesti ajassa \(O(1)\).