Index balra, index jobbra
2009. január 20.Egyik hozzászólónk bölcsen megállapította, hogy kínai szótáramnak hatalmas indexekre van szüksége, s ez eszembe juttatott pár dolgot az indexekről.
Itt a blogban még nem meséltem az indexekkel volt legérdekesebb kalandomról. Nézze el az olvasó, ha esetleg a spanyolviaszt találtam föl újra – mindig távol éltem a modern programozói módszerek főfolyamától, egyedül kellett rájönnöm mindenre.
Tizenegynéhány évvel ezelőtt az akkor még csak bimbajazó IMDb nemcsak online, hanem offline is használható volt, amit jobban szerettem, mert nem kellett minden egyes adatért becsatlakoznom a netre drága pénzért, csak egyszer letöltöttem a hatalmas adatbázisokat és bármikor használhattam. Később lett hozzá speciális kezelőszoftver is, Clipperben írták és nagyon aranyos volt. Úgy működött, hogy először is leindexelte az adatbázist, ha jól emlékszem, a filmcímekkel kezdte. Jó darabig (már nem emlékszem, mondjuk félóráig) dolgozott, aztán közölte, hogy elfogyott a memória. Ezalatt létrehozott egy kétmegás indexfile-t, és nem jutott el az A betűs filmek végéig.
Ahhoz képest, hogy én ugye egy amatőr vagyok, aki a lenézett BASIC-ben programozgat, meg kellett állapítanom, hogy az én módszerem jobb. A filmcímeknél jóval nagyobb színészlistáról is pár perc alatt elkészítette az indexet, ami nem egészen egy kilobyte-ot nyomott, és onnantól kevesebb mint egy másodperc alatt megtalált bármit az adatbázisban.
Persze ez nem lett egyből ilyen. Én is azzal kezdtem, hogy akkor most olvassuk végig a file-t, és amikor a rekord új betűvel kezdődik (A, B, C, D stb.), akkor jegyezzük be a címet az indexbe. Nem volt rossz, de messze nem volt jó se. A színészeknek már akkor is megvolt az a tulajdonságuk, hogy bár a legkülönbözőbb betűkkel kezdődtek a neveik, ez nem volt statisztikailag egyenletesen elosztva. S-sel és M-mel jóval többen voltak, mint X-szel vagy Y-nal. Ezért Youngot vagy a betűje elején levő Mackenzie-t sokkal gyorsabban meg lehetett találni, mint mondjuk Sykest.
Akkor megpróbáltam fölosztani a hosszabb betűket, Ma és Mo, Sa és Sm, ilyesformán. Ez némi macerációval járt, és az eredmény még mindig nem volt kielégítő. Ekkor jöttem rá, hogy mi a teendő.
Semmi szükség rá, hogy az X és Y kezdetű nevek két külön bejegyzést kapjanak az indexben, ha egyszer olyan kevesen vannak. Ez a telefonregiszter-szerű megközelítés rossz. Fordítva kell csinálni!
Az új algoritmusom a következőt tette. Végigolvasta az adatbázist rekordonként, egyetlenegyszer, és közben mérte az időt. Amikor a beállított időtartam (mondjuk egy másodperc) letelt, akkor feljegyezte a következő rekordból a nevet és kezdetének byte-pozícióját (mivelhogy pozicionálni a BASIC SEEK utasításával lehetett). Nullázta az időmérőt és ment tovább, egy másodpercenként bejegyzést csinálva. Így ha a teljes adatbázis végigolvasása mondjuk négy percbe telt, akkor kétszáznegyven bejegyzés került az indexbe. Helytakarékosságból a neveknek csak akkora részét írta föl, hogy mindegyik kulcs különböző legyen (például ha volt bejegyzés Vlagyimirovics és Vlagyimirovna szöveggel, akkor Vlagyimirovi és Vlagyimirovn került az indexbe).
Keresni innentől úgy lehetett, hogy végigolvastuk az indexet és minden kulcsot összehasonlítottunk a keresendő szöveggel. Az első esetnél, amikor a kulcs ASCII szerint nagyobb volt, mint a szöveg, fogtuk az előző bejegyzéshez mellékelt pozíciót, odaugrottunk az adatfile-ban és elkezdtünk keresni. A legrosszabb esetben is egy másodpercen belül megvolt a találat – hiszen ha egy másodpercnél messzebb van, akkor már a következő bejegyzés illetékességi körébe tartozik.
Ez persze csak név szerinti keresésre jó, névrésszel nem működik, de az nem is volt cél.
Ez volt régen. Ma sokkal egyszerűbb a dolgunk. Az ember csinál egy tömböt, beinclude-olja és úgy dolgozik vele, ahogy akar, mindegy, hogy mekkora. Persze célszerű, ha a kulcs az az adat, amire keresünk. A PHP-nek viszont megvan az tulajdonsága, hogy gigantikus adatmennyiségeket tud kezelni, ezért azt is meg lehet tenni, hogy ugyanarról az adatbázisról több tömböt készítünk, más-más kulcsokkal.