> Igaz, hogy rendezett tombben gyorsabban keresel pl. binaris keresessel,
> listaban meg linearisan keresel, de ha megvan az elem, listaban csak
> beszurod es kesz, tombben meg az utana kovetkezo elemeket meg toligalnod
> kell! Foleg, ha az elemek eloszlasarol van nemi fogalmad, akkor egy
> ketiranyu listaban a kereses iranyat egy elozetes vizsgalat utan
> megvalasztva meg gyorsabb lesz.
> Na, meger egy sort? :-)
Az, hogy a masolas vagy az osszehasonlitas a gyorsabb, az attol
fugg, hogy mit kell osszehasonlitani. Ha mondjuk hosszu karakter-
lancokat, akkor nem biztos, hogy mondjuk 1 millio elem eseten
a 20 strcmp() + egy memcpy() 2Mbyte -ra (4byte/ptr, atlagosan a
fele tombot toljuk) lassabb lenne, mint 500,000 strcmp() (atlagosan
a lista felet kell megnezni). Ha a rendezesi kulcsok egesz szamoknal
bonyolultabb objektumok, akkor a sebesseget az osszehasonlitasok
szama fogja meghatarozni. Emellet tekintetbe kell venni, hogy
altalaban adatbazisokon a leggyakoribb muvelet a kereses, ahol
*csak* osszehasonlitasok tortennek, igy ezek szamat kell
minimalizalni.
Termeszetesen a lista egy altalaban sokkal kellemesebb objektum,
mint a tomb. Ha tudnank egy listan binarisan keresni, akkor az
igen szerencses modon osszehazasitana a tomb keresesi sebesseget
a lista kezelesi sebessegevel.
Nos, erre talaltak ki a skiplist-et. A sebessege nagyjabol a binaris
keresesevel egyezik meg(*) elonye viszont, hogy a beszuras,
torles es kereses mind ugyanolyan gyors es soha nem kell toligalni
a memoriat. Az atlagos helyigeny pedig a ketszeresen lancolt listanak
felel meg (azaz 2 ptr per elem). Tovabbi elonye, hogy teljesen
erzeketlen arra, hogy az adatok eleve rendezetten jonnek vagy sem.
Nem igenyel tul sok stack-et (leven nem-rekurziv) es csak minimalis
nyilvantartast vezet, tehat a memoria nem gond. Kicsit bonyolultabb,
mint a ketszeresen lancolt lista, de azert igy is le lehet kodolni
mintegy ketszaz C sorban (megjegyzesek meg ures sorok nelkul).
(*) egy skiplist es egy kiegyensulyozott binaris fa mintegy 1E7
random adaton osszehasonlitva azt az eredmenyt adta, hogy kereses
eseten a skiplist atlagosan 1-el tobb osszehasonlitast csinal,
mint a kiegyensulyozott binaris fa.
Beszuras es torles eseten termeszetesen a skiplist sokkal gyorsabb,
pontosabban ugyanolyan gyors mint keresesre, mig a kiegyensulyozott
binaris fa rossz esetben koztudottan nagyon sokat kell dolgozzon.
Zoltan
|
Ha listakat hasznalsz, es gyakran keresel benne, egyertelmu, hogy nemcsak
az elejet tarolod(ketszeresen lancoltnal a veget is ugye ), hanem hash
szeruen pl minden betunek megadod a kezdopointeret egy tombben, vagy
megtobb szamu adat eseten, a kezdo ketbetukhoz tartozo elso elemeket
tarolod. Es ha nincs olyan elem, akkor ugye NULL, igy elofordulhat, hogy nem is
kell keresni, csak megnezni a kezdetet :) A hatranya az algoritmusnak,
hogy a beszuras es egyeb muveletek bonyolultabbak lettek, mert meg kell
allapitani, hogy hatha az uj elem kerul a bonusztombbe valameylik regi
elem helyett.
Pascal din.lista :
Az hogy gyarilag nincs megvalositva, az nem jelenti azt hogy nincs, CSAK
eppen meg kell irni !
Eggor.
|
