Taulukko (tietorakenne)

Tietojenkäsittelytieteessä taulukko () on alkeellinen tietorakenne, jota käytetään lähes kaikissa muutamaa riviä pidemmissä tietokoneohjelmissa. Sitä voi verrata numeroituun lokerikkoon, jonka jokaisessa lokerossa on yksi arvo.

Taulukko koostuu peräkkäisistä tallennuspaikoista, ”alimuuttujista”. Niiden arvoja kutsutaan taulukon alkioiksi. Alkioiden tallennuspaikat on numeroitu yleensä nollasta alkaen, ja tätä järjestysnumeroa kutsutaan indeksiksi. Taulukon pituus eli alkioiden lukumäärä valitaan, kun taulukko luodaan. Pituus on kiinteä, tai sen muuttaminen on hidasta. Alkioiden täytyy olla samaa tyyppiä.

Esimerkiksi kuuden alkion pituinen taulukko, jossa on kirjainmerkit ’q’, ’w’, ’e’, ’r’, ’t’ ja ’y’, näyttää seuraavalta:
 Indeksi:  0  1  2  3  4  5 Alkio: ’q’’w’’e’’r’’t’’y’

Taulukon matemaattinen malli on äärellinen lukujono, ja sen avulla voidaan toteuttaa vektori ja matriisi.

 Suorituskyky 

Taulukon yleisimpien operaatioiden asymptoottinen suoritusaika:
 operaatio  järjestämätön taulukko  järjestetty taulukko indeksointi  O(1)  O(1) lisäys  O(n)  O(n) haku  O(n)  O(log n) suurin tai pienin arvo  O(n)  O(1) läpikäyminen järjestyksessä  O(n log n)  O(n)

Lisäys on O(n), koska taulukon kokoa ei voi kasvattaa muuten kuin kopioimalla kaikki alkiot uuteen taulukkoon. Välimuisti kykenee nopeuttamaan taulukko-operaatioita huomattavasti, jolloin teoriassa taulukkoa nopeampi tietorakenne saattaa olla käytännössä hitaampi.

Taulukkoon voidaan tallentaa tietoa hyvin tiiviisti, koska ylimääräisiä osoittimia ei tarvita toisin kuin linkitetyissä tietorakenteissa. Kun taulukossa n alkiota ja yksi alkio vie tilaa k tavua, taulukko vaatii n · k tavua muistia. Lisäksi yleensä täytyy säilyttää myös taulukon koko ja viite taulukkoon.

 Ohjelmointi taulukolla 
Olkoon taulukko T alustettu seuraavaksi:
 Indeksi:  0  1  2  3  4  5 Alkio: 198619651988198319841981

Kun T on alustettu, sen alkioita voidaan käyttää laskutoimituksissa. Alkioihin viitataan indeksoimalla, mikä useimmissa kielissä näyttää seuraavalta:
 T[3] - 1
Yllä olevan laskutoimituksen tulos on 1983 – 1 = 1982.

Kuten muuttujaan, myös taulukkoon voidaan sijoittaa uusi arvo vanhan tilalle. Indeksissä 1 olevan luvun (1965) muuttaminen luvuksi 2001 onnistuu yleensä seuraavaan tapaan:
 T[1] := 2001
Yllä oleva luetaan: ”Taulukon T alkio indeksissä 1 saa arvokseen 2001.” Tämän operaation jälkeen taulukko T on muuttunut:
 Indeksi:  0  1  2  3  4  5 Alkio: 198620011988198319841981

 Läpikäynti 

Usein taulukon jokaiselle alkiolle halutaan tehdä jotakin. Jos taulukon koko on 6, täytyy käydä läpi indeksit 0..5. Tähän käytetään ohjelmointikielen for-lausetta seuraavaan tapaan:
 (i käy läpi arvot 0..5, ja joka arvolla
  toistetaan sisennettyä lausetta)
 for i := 0 to 5 do
     tee jotain T[i]:n kanssa
 end for
Yleisesti:
 T: taulukko
 n: taulukon koko
 f: funktio, joka tekee jotain alkiolle
 for i := 0 to n-1 do
     f(T[i])
 end for
Monissa ohjelmointikielissä on myös for each -lause, joka helpottaa taulukon ja muiden säiliöiden läpikäyntiä. Tämä on kuitenkin rajoittuneempaa kuin indeksoiminen: jokainen alkio täytyy käydä läpi, alkion indeksiä ei ole saatavilla ja joissakin ohjelmointikielissä taulukkoon ei voi sijoittaa tällä tavalla.
 for each a in T do
     f(a)
 end for
Funktionaalista ohjelmointia tukevissa kielissä for each voi olla toteutettu korkeamman kertaluvun funktiona eli funktiona, joka saa parametrikseen funktion.
 for_each(f, T)

 Alkion etsiminen 

Yksinkertainen hakualgoritmi on peräkkäishaku, jossa taulukosta etsitään arvo käymällä alkiot yksi kerrallaan läpi. Pseudokoodina:
 function peräkkäishaku(T, k, n)
     T: taulukko
     k: haettava arvo
     n: taulukon koko
     jos arvo löytyy, palauttaa etsityn arvon indeksin (ensimmäisen vastaan tulevan)
     jos arvoa ei löydy, palauttaa -1

     for i := 0 to n-1 do
         if T[i] = k then return i
     end for

     (ei löytynyt)

     return -1
 end function

Jos taulukko on järjestetty, voidaan käyttää tehokkaampaa puolitushakua.

 Koon kasvattaminen 

Taulukon kokoa ei varsinaisesti voi kasvattaa, mutta vanhan taulukon alkiot voi kopioida uuteen, suurempaan taulukkoon. Yleisimmissä ohjelmointikielissä on välineitä, jotka tekevät tämän automaattisesti, esimerkiksi C++:n std::vector ja Javan Vector tai ArrayList.

 T: vanha taulukko
 S: uusi taulukko
 n: vanhan taulukon koko

 S := new table(n * 2)
 for i := 0 to n - 1 do
     S[i] := T[i]
 end for

C-kielessä voidaan yrittää kasvattaa taulukon kokoa, mikä onnistuu vain, jos keskusmuistia on riittävästi vapaana. Jos alkioita joudutaan jatkuvasti lisäämään ja poistamaan, linkitetty lista voi olla parempi tietorakenne.

 Alkion poistaminen 

Alkion poistamiseen on useita ratkaisuja. Yksi on kopioida kaikki alkiot poistettavaa lukuun ottamatta uuteen taulukkoon. Yleinen tapa on myös poistettavan alkion jälkeen tulevien alkioiden vetäminen yksi indeksi eteenpäin:

 T: taulukko
 n: taulukon koko
 d: poistettavan alkion indeksi

 for i := d to n – 2 do
     T[i] := T[i + 1]
 end for

Tämän jälkeen voidaan:
 pienentää taulukkoa, jos ohjelmointikieli sallii sen (C-kielessä realloc)
 huijata pienentämällä pituutta esittävää muuttujaa yhdellä

Taulukon pienentäminen jokaisen poiston yhteydessä on nopeusrasite, joten yleensä kannattaa huijata: mikäli taulukon koko vaikkapa puolittuu, kannattaa harkita sen pienentämistä oikeasti.

 Alkion lisääminen taulukon alkioiden väliin 

Uuden alkion lisääminen taulukon alkioiden väliin (esimerkiksi suuruusjärjestyksen säilyttämistä varten) muistuttaa yllä esitettyä poistoalgoritmia: Alkioita täytyy työntää eteenpäin taulukon loppupäästä alkaen lisäyskohtaan asti. Jos työntämisen aloittaa lisäyskohdasta ja etenee loppua kohden, syntyy virhe: lisäyskohdan alkio kopioituu jokaiseen sitä seuraavaan taulukon paikkaan!

 T: taulukko
 a: indeksi, johon lisättävä alkio sijoitetaan

 kasvata T:n kokoa yhdellä
 n := T:n uusi koko

 for i := n – 2 down to a do
     T[i + 1] := T[i]
 end for

Lisäyslajittelu käyttää hyväkseen yllä esitettyä lisäysalgoritmia.

 Lajitteleminen suuruusjärjestykseen 

Taulukon lajittelemiseksi suuruusjärjestykseen on kehitetty lukuisia lajittelualgoritmeja, joiden tehokkuus vaihtelee huomattavasti. Tehoton mutta yksinkertainen keino on valintalajittelu:

 Etsitään väliltä T[first]...T[last] pienin alkio ja vaihdetaan se paikkaan T[first].
 Etsitään väliltä T[first + 1]...T[last] pienin arvo ja vaihdetaan se paikkaan T[first + 1].
 Tehdään sama kolmannelle alkiolle, neljännelle alkiolle...
 Kun toiseksi viimeinen alkio on saatu käsiteltyä, koko taulukon väli last...first on järjestyksessä.
 for i := 0 to n – 2 do
     min := pienin alkio väliltä T[i]...T[n – 1]
     vaihda T[i] <–> min
 end for

 Muunnelmia 

Ohjelmoinnissa taulukoita on kaikkialla, joten niistä on tehty lukuisia muunnelmia.

 Moniulotteiset taulukot 

Taulukot voivat olla moniulotteisia. Kaksiulotteisuus voidaan toteuttaa taulukolla, jonka alkiot ovat taulukoita:

 T := new Table(korkeus)
 for i := 0 to korkeus – 1 do
     T[i] := new Table(leveys)
 end for

Tämä toteutustapa luonnollisesti mahdollistaa kuinka moniulotteiset taulukot tahansa. Läpikäyntiin voidaan käyttää sisäkkäisiä for-lauseita:

 for y := 0 to korkeus – 1
     for x := 0 to leveys – 1
         T[y][x] := 0
     end for
 end for

Sisäkkäiset taulukot mahdollistavat myös vaikkapa kolmionmuotoisen taulukon, josta voi olla hyötyä esimerkiksi toteutettaessa suuria symmetrisiä matriiseja. Linkitetty lista on yksinkertainen tietorakenne, joka ketjuttaa arvoja toisiinsa hitusen sisäkkäisten taulukoiden tapaan.

Kaksiulotteista taulukkoa voidaan jäljitellä käyttämällä yksiulotteista taulukkoa:
 T := new Table(leveys * korkeus)

 seuraava vastaa ilmausta T[x][y] := 999
 T[y * leveys + x] := 999

Tästä on se etu, että taulukko sijaitsee keskusmuistissa yhtenäisenä nauhana, jolloin välimuistitus saattaa parantua ja taulukon jokaiselle alkiolle on helpompi ja hitusen nopeampi tehdä operaatioita. Usein esimerkiksi bittikarttakuvat ladataan tähän muotoon keskusmuistiin.

 Indeksiväli 

Nollalla alkavat indeksit ovat käytössä kaikissa yleisimmissä ohjelmointikielissä. Edsger Dijkstra puolusti nollalla alkavia indeksejä kirjoitelmassa Why numbering should start at zero. Kuitenkin joissakin ohjelmointikielissä ensimmäiseksi indeksiksi on valittu luku 1 eikä 0. Tässä lähestymistavassa on puolensa:
1 on arkikäytössä yleisempi ensimmäinen järjestysluku kuin 0 (”nollas”), joten se on intuitiivisempi.
Voidaan kirjoittaa for i := 1 to taulukon_koko eikä for i := 0 to taulukon_koko – 1.
Toisaalta 0 on luonnollisempi ensimmäinen indeksi:
Lauseke taulukon_koko – ensimmäinen_indeksi antaa tulokseksi taulukon koon.
Laitteistotasolla taulukon indeksit alkavat nollasta.
Arvoalueen ylitys voidaan tarkistaa yksinkertaisesti: i < taulukon koko.
For-lause voidaan kirjoittaa for i := 0; i < taulukon_koko; i := i + 1, joka kertoo suoraan, mitä silmukassa laitteistotasolla tapahtuu.
Euroopassa nolla kuuluu yleensä luonnollisiin lukuihin matematiikassa ja siten myös lukujonot alkavat nollasta.
Käytännössä nolla ensimmäisenä indeksinä on huomattavasti yleisempi, koska C-pohjaiset kielet kuten C++, Java ja C# sekä monet uutta tyyliä edustavat kielet kuten JavaScript, Perl, PHP, Python ja Ruby käyttävät sitä.

Joissakin ohjelmointikielissä voidaan valita taulukon indeksiväli itse (eli ne tukevat n-pohjaisia taulukoita); tällaisia ovat esimerkiksi Visual Basic, Pascal, Ada ja Lua. Ei ole selvää, onko tästä enemmän hyötyä vai haittaa: Ohjelmoijan täytyy tarkistaa taulukon indeksiväli erikseen, ja taulukkomuuttujan vastaanottaminen aliohjelman parametrina aiheuttaa omat hankaluutensa. Indeksialueen määriteltävyys auttaa eniten silloin, kun ohjelmoidaan tarkasti matemaattisten määritelmien mukaan.

 Taulukko laitteistoläheisesti 

Taulukko on helpoimpia tietorakenteita toteuttaa konekielen tasolla. Itse asiassa keskusmuistia voi ajatella nauhamaisena taulukkona, jota indeksoidaan muistiosoitteilla. Taulukko on vain yhtenäinen pätkä keskusmuistia.

 Taulukon luominen 
Taulukko luodaan pyytämällä käyttöjärjestelmää varaamaan vapaalta muistialueelta n · k tavua muistia, missä n on taulukon pituus ja k yhden alkion vaatima tila tavuina. Käyttöjärjestelmä vastaa antamalla osoittimen varatun muistialueen alkuun.

Jos taulukon säilyy muistissa koko suorituksen ajan, tarvittava muistialue voidaan sisällyttää ohjelman binääriin. Paikallisena muuttujana käytettävä pieni taulukko voidaan myös luoda ajonaikaiseen pinoon.

 Taulukon indeksoiminen 
Käyttöjärjestelmän antama osoitin on arvo, joka sisältää taulukon ensimmäisen alkion muistiosoitteen – eli indeksin taulukkoon nimeltä keskusmuisti. Olkoon tuo osoite p. Jos halutaan käyttää taulukon ensimmäistä alkiota johonkin, prosessoria voidaan yksinkertaisesti käskeä noutamaan k tavua pitkä arvo muistiosoitteesta p. Jos halutaan noutaa arvo taulukon indeksistä 3, prosessoria käsketään noutamaan k tavua pitkä arvo osoitteesta p + 3 · k. Tällaista osoitteiden summausta kutsutaan osoitinaritmetiikaksi.

 Ohjelmointi ilman taulukoita 

Useimmat ohjelmoijat ovat tottuneet käyttämään taulukoita jokapäiväisesti. Kuitenkin monissa funktio-ohjelmointikielissä, kuten LISPissä ja Haskellissa, alkeellisimpana tietorakenteena taulukon tilalla on linkitetty lista. Se sopii kieliin, joissa for-lauseen korvaa rekursio. Jos puhtaassa funktio-ohjelmointikielessä on taulukko, sen muuttaminen voi olla toteutettu käyttäen alkuperäisen taulukon päälle lisättyä hakurakennetta, jolloin indeksointi ei toimikaan vakioajassa.

Lua perustuu assosiaatiotauluun, joka toimii myös taulukkona.

 Katso myös 
 Muita primitiivisiä tietorakenteita 
 Pino
 Tietue
 Vaihtoehtoja 
 Assosiaatiotaulu, taulukon yleistys muille kuin kokonaislukuindekseille
 Hajautustaulu, assosiaatiotaulun tehokas toteutus
 Linkitetty lista, helposti kasvatettava tietorakenne
 Taulukko-algoritmeja 
 Lajittelualgoritmi
 Hakualgoritmi
 Puolitushaku

 Aiheesta muualla 

 Taulukosta yleisesti 
 Malmi, Korhonen ja Karavirta: TRAKLA2: Elektroninen oppikirja / Opetusmoniste: Taulukko 
 Edsger Dijkstra: Why numbering should start at zero

 Taulukko ohjelmointikielissä 
 Arto Wikla: Ohjelmoinnin perusteita Java-kielellä: 2.8 Taulukko-olioista
 Wikibooks: C: ohjelmointiopas ja vakiokirjastot: Taulukot
 Steve Summit: C Programming Class Notes: 4.1 Arrays
 Ohjelmointiputka: Pascal-ohjelmointi: Osa 2 - Vakiot, muuttujat ja tietueet: Taulukot

Luokka:Tietorakenteet