Peräkkäishaku
Tietojenkäsittelytieteessä peräkkäishaku eli lineaarihaku on yksinkertainen hakualgoritmi, joka etsii arvoa taulukosta käymällä sen läpi alkio alkiolta. Toisin kuin puolitushaku tai interpolaatiohaku, peräkkäishaku ei vaadi, että alkiot ovat suuruusjärjestyksessä.
Peräkkäishaku yleistyy jokaiselle tietorakenteelle, jonka alkiot voidaan luetella yksi kerrallaan (iteroituva tietorakenne) ja jonka alkioille on määritelty yhtäsuuruus.
Algoritmi[muokkaa | muokkaa wikitekstiä]
Peräkkäishaun periaate voidaan muotoilla seuraavasti:
- Jos taulukon ensimmäinen alkio on etsitty arvo, palautetaan sen indeksi eli 0.
- Jos taulukon toinen alkio on etsitty arvo, palautetaan sen indeksi eli 1.
- Toistetaan vastaavasti kolmannelle alkiolle, neljännelle alkiolle...
- Jos viimeinenkään alkio ei ole etsitty arvo, palautetaan ”ei löytynyt” eli –1.
Seuraava on pseudokoodina toteutettu peräkkäishakualgoritmi, joka kertoo arvon x indeksin taulukossa T:
T: taulukko [0 ... n – 1]
n: taulukon pituus eli alkioiden lukumäärä
x: etsittävä arvo
Palauttaa:
* indeksin i ensimmäiseen alkioon, joka on yhtä suuri kuin x (eli jos x = T[i])
* –1, jos arvoa ei löydy
function peräkkäishaku(T, n, x)
for i := 0 to n – 1 do
if T[i] = x then
return i
end if
end for
return –1
end function
Suorituskyky[muokkaa | muokkaa wikitekstiä]
Peräkkäishaun asymptoottinen suoritusaika on kertaluokkaa O(n). Jos oletetaan että haettava alkio esiintyy taulukossa, niin sen etsimiseen satunnaisesti järjestetystä n:n pituisesta taulukosta tarvitaan keskimäärin n / 2 vertailua. Parhaimmassa tapauksessa, jossa etsitty alkio on taulukon ensimmäinen alkio, tarvitaan yksi vertailu. Pahimmassa tapauksessa, jolloin etsitty alkio ei esiinny taulukossa lainkaan, algoritmi tekee syötteen pituuden verran eli n kappaletta vertailuja.
Samat luvut pätevät jokaiselle tietorakenteelle, jossa seuraavaan alkioon siirtyminen vie aina saman verran aikaa.
Erityissovelluksia[muokkaa | muokkaa wikitekstiä]
Peräkkäishaku yhdistettynä tietuealkioihin mahdollistaa ajassa O(n) toimivan hakurakenteen eli assosiaatiotaulun toteuttamisen lähes minkä tietorakenteen avulla tahansa. Esimerkkitoteutus taulukkona:
record Alkio
key: avain, jonka perusteella arvoja noudetaan ja jolle on määritelty yhtäsuuruus
value: arvo, varsinainen tietoalkio
end record
T: taulukko, jonka alkiot ovat tyyppiä Alkio
n: taulukon pituus
k: haettava avain
function lookup(T, n, k)
for i := 0 to n – 1 do
if T[i].key = k then
return T[i].value
end if
end for
return ei löytynyt
end function
Tehokkaampia hakurakennetoteutuksia ovat hajautustaulu ja tasapainoinen hakupuu.