file met "elementen" en ge-indexeerde zoeklijst

[MicroWhale]

Het lijkt een beetje op een database wat ik wil, maar ik zie de oplossing niet echt.

Er is een file met structuur (deze file bestaat uit een oneindig aantal elementen):
data-id,element

waar:
- data-id is uniek en een 4- of 8-byte nummer
- element is (vooralsnog) integer, float, string (van variabele lengte (1..x))

Dit bovenstaande is op zich niet echt spectaculair.

maar ik heb nodig:
- gegeven de inhoud van een element x, vind snel het bijbehorende data-id.

hoe krijg ik dat snel voor elkaar (zonder seek door de hele file)?
ik heb op internet lopen zoeken en ik kom veel algoritmes tegen, maar niet dat wat ik nodig heb.

Er zal dus een index moeten komen, maar ik kom er niet uit hoe... een omgekeerde lijst is dubbele info. Misschien een of andere tree?

Wie kan me een voorzetje geven?

[joepP]

Als je twee kanten op wilt zoeken heb je hoe dan ook twee datastructuren nodig.

Het eenvoudigste in dit geval lijkt me 3 losse lijsten, eentje per type (int, float, string), gesorteerd op waarde. Dan kan je met binair zoeken binnen de relevante lijst in O(log n) het juiste element vinden. In de praktijk betekent dit ongeveer 20 opzoekacties voor een lijst van lengte 1.000.000. Snel genoeg dus

Een alternatief is een hash gebruiken, daar moet je ook genoeg over kunnen vinden op internet.

[MicroWhale]

ik heb inderdaad al iets gevonden over hashes.

de gesorteerde lijst lijkt me niet echt handig, vooral omdat je dan een file moet bij gaan houden die gesorteerd moet blijven. (alles in het geheugen laden is geen optie, helaas) Dmv slimme hash-lijsten kun je binnen een paar stappen vinden wat je nodig hebt.

Die worden het dus ook.

Ik besef wel dat het daardoor allemaal best opblaast qua datastructuur, maar het komt in dit geval wel het doel ten goede.

[ Voor 6% gewijzigd door MicroWhale op 11-03-2006 09:04 ]

[Soultaker]

De de-facto standaard datastructuur hiervoor is de B-tree. Daarin kun je elementen effecient gesorteerd opslaan. (Omdat jij wil zoeken op de data in plaats van de id, is die data eigenlijk je id. In je B-tree sla je dus paren data,id op.)

Je kunt dit zelf programmeren, want het is niet ontzettend ingewikkeld, maar de implementatiedetails zijn toch wel tricky. Voor optimale performance wil je je B-tree entries bijvoorbeeld afstemmen op de clustergrootte van het bestandssysteem. De variabele groottes van de elementen die je opslaat maken het ook bepaald niet makkelijker.

Persoonlijk zou ik je dus aanraden om de database te implementeren met een daarvoor bedoelde library zoals Berkeley DB of GDBM. (Van Berkeley DB is een oudere versie (1.85) beschikbaar in de FreeBSD source code; die is gelicenseerd onder de BSD-licentie die minder restricties oplegt dan de GPL of Sleepycat's license).

Als je overigens geen updates hoeft te doen in je database dan is Bernstein's CDB ook een goede keuze. (Die database moet je geheel herschrijven als je 'm wil wijzigen, maar look-ups zijn snel.)

[ Voor 14% gewijzigd door Soultaker op 11-03-2006 16:47 ]