Nopea haku taulukosta

koodaja

Taulukossa on vaikka merkkijonot:

"Matti", "Jussi","Pekka","Sami","Henri","Heli","Liisa"

Mikä on nopein tapa saada selville, onko taulukossa vaikka "Pekka" ?

Nopeus on erittäin tärkeätä!

Kaikki merkkijonon "nimet" on etukäteen tiedossa, ja myöhemmin suoritetaan vain nämä tarkistukset, onko merkkijono vai ei (true/false).

Vai olisiko esim switch case nopeampi ?

3

331

    Vastaukset

    Anonyymi (Kirjaudu / Rekisteröidy)
    5000
    • Voit vaikka lajitella tiedot järjestykseen, ja lopettaa haun heti, kun mennään yli sen kohdan, mistä lähtien haettavaa elementtiä ei voi tulla enää vastaan lopputaulukossa.

      Kun dataa tulee huomattavasti enemmän, niin voisi esim. luoda taulukon kutakin aakkosta kohti. Tämän taulukon elementteihin tulee myös taulukko, jossa on ko. kirjaimella alkavat sanat. Haettaessa x-kirjaimella alkavaa sanaa riittää selata läpi vain se taulukon kohta (eli siis siitä indeksistä saatava lista), mihin on tallennettu x-kirjaimella alkavat sanat.

      Toisaalta ainakin noin pienillä datamäärillä taulukon läpikäymiseen käytettävä aika suhteessa muuhun on täysin merkityksetön (etenkin silloin, jos teet jotain interaktiivista ohjelmaa).

      Switch-case on tuskin nopeampi, sillä se vastannee listan läpikäymistä for- tai while-loopissa. Lisäksi sen ylläpitäminen käsin on tuskaa.

    • Liksa0

      1a) Jos merkkijono on tiedossa niin järjestä hakutaulukko etukäteen.

      1b) Aloita etsiminen keskimmäisestä indeksistä ja jos haettava asia on suurempi kuin keskimmäinen indeksi jää jäljelle taas puolet pienempi alue josta otat taas keskimmäisen indeksin... tätä jatketaan kunnes löytyy tai indeksi ei muutu (löydettiin lähin mahdollinen).

      2) Jos vaikka 90% hauista tehdään samalla sanalla niin käsittele ne erikseen cachella.

      3) Balancing Tree algoritmi on kaikkein tehokkain mutta se on monimutkainen ja soveltuu lähinnä laajoille datajoukoille.

      4) Datan profiloiminen nopeuttaa jonkin verran suuria ei-heterogeenisiä hakujoukkoja. (Eli siis etukäteen selvitetään missä suhteessa on vaikka A:lla alkavia nimiä muihin kirjaimiin verrattuna jotta haku osataan alkaa oikeasta kohtaa.)

      5) Usein kuitenkin käy niin että nopeuttamiseen tehty logiikka on lähes yhtä raskasta kuin perus puolittava haku.

    • tumpelo

    Ketjusta on poistettu 0 sääntöjenvastaista viestiä.

    Luetuimmat keskustelut

    1. Nurmossa kuoli 2 Lasta..

      Autokolarissa. Näin kertovat iltapäivälehdet juuri nyt. 22.11. Ja aina ennen Joulua näitä tulee. . .
      Seinäjoki
      127
      6758
    2. Maisa on SALAKUVATTU huumepoliisinsa kanssa!

      https://www.seiska.fi/vain-seiskassa/ensimmainen-yhteiskuva-maisa-torpan-ja-poliisikullan-lahiorakkaus-roihuaa/1525663
      Kotimaiset julkkisjuorut
      162
      4214
    3. Vanhalle ukon rähjälle

      Satutit mua niin paljon kun erottiin. Oletko todella niin itsekäs että kuvittelet että huolisin sut kaiken tapahtuneen
      Ikävä
      51
      3399
    4. Mikko Koivu yrittää pestä mustan valkoiseksi

      Ilmeisesti huomannut, että Helenan tukijoukot kasvaa kasvamistaan. Riistakamera paljasti hiljattain kylmän totuuden Mi
      Kotimaiset julkkisjuorut
      490
      3004
    5. Purra hermostui A-studiossa

      Purra huusi ja tärisi A-studiossa 21.11.-24. Ei kykene asialliseen keskusteluun.
      Perussuomalaiset
      285
      1980
    6. Joel Harkimo seuraa Martina Aitolehden jalanjälkiä!

      Oho, aikamoinen yllätys, että Joel Jolle Harkimo on lähtenyt Iholla-ohjelmaan. Tässähän hän seuraa mm. Martina Aitolehde
      Suomalaiset julkkikset
      35
      1669
    7. Kaksi lasta kuoli kolarissa Seinäjoella. Tutkitaan rikoksena

      Henkilöautossa matkustaneet kaksi lasta ovat kuolleet kolarissa Seinäjoella. Kolmas lapsi on vakasti loukkaantunut ja
      Maailman menoa
      15
      1509
    8. Miten meinasit

      Suhtautua minuun kun taas kohdataan?
      Ikävä
      90
      1493
    9. Miksi pankkitunnuksilla kaikkialle

      Miksi rahaliikenteen palveluiden tunnukset vaaditaan miltei kaikkeen yleiseen asiointiin Suomessa? Kenen etu on se, että
      Maailman menoa
      175
      1441
    10. Ensitreffit Hai rehellisenä - Tämä intiimiyden muoto puuttui suhteesta Annan kanssa: "Meillä ei..."

      Hai ja Anna eivät jatkaneet avioliittoaan Ensitreffit-sarjassa. Olisiko mielestäsi tällä parilla ollut mahdollisuus aito
      Ensitreffit alttarilla
      15
      1396
    Aihe