datarakennevalinnat

Datarakennevalinnat ovat prosessi, jossa ohjelmistokehittäjä valitsee sopivat tiedon tallennus- ja käsittelyrakenteet tiettyyn tehtävään. Valinnat vaikuttavat suorituskykyyn, muistijalanjälkeen sekä ohjelmiston monimutkaisuuteen ja ylläpidettävyyteen. Tärkeimpiä harkinnanaiheita ovat käytettävät operatiot (hakea, lisätä, poistaa, järjestäminen), datan pääsymalli (satunnainen haku, peräkkäinen läpikäynti), sekä datasarjan koko ja muistirajat. Myös reaaliaikaisuus, rinnakkaisuus sekä ohjelmointikielen ominaisuudet ja käytettävissä olevat kirjastot vaikuttavat valintaan.

Yleisimmät tiedonrakenteet voidaan jakaa useisiin pääluokkiin. Taulukot ja dynaamiset listat tarjoavat nopean indeksoinnin ja hyvän välimuistisuorituskyvyn, mutta voivat vaatia uudelleenvarastointia. Linkitetyt listat helpottavat lisäyksiä ja poistoja ilman suurta muistinvarastointia, mutta niiden välimuisti-ominaisuudet ovat heikommat. Hajautustaulut eli hash-taulut tarjoavat keskimäärin nopean haun ja tallennuksen, mutta muistikasut ja mahdollinen järjestyksen puute on huomioitava. Puut, kuten tasapainotetut puut (AVL, punamustapuu), tarjoavat järjestetyn tiedon ja hyvät hakualgoritmit. Prioriteettijonot (keko) soveltuvat priorisointiin. Graafeissa käsittely voidaan käyttää naapuriluetteloa tai matriisia riippuen tilanteesta. Pinot ja jonot ovat yksinkertaisia käyttötarkoituksen mukaan.

Valinta tapahtuu analysoimalla käyttötapaukset, vaatimusajat sekä muistitarpeet ja arvioimalla, miten rakenteet vaikuttavat kehitykseen ja ylläpitoon. Prototyypin ja mittaamisen avulla voidaan tarkentaa valintaa.