信息进村入户工程全面实施 信息化与农业现代化融合提速

百度 记者注意到，570舰指的是黄山号导弹护卫舰。

Tietojenk?sittelytieteess? taulukko (engl. array) 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:	1986	1965	1988	1983	1984	1981

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:	1986	2001	1988	1983	1984	1981

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 (Arkistoitu – Internet Archive)
• 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