Snel zoeken van namen

[Schwartz]

Ik heb een snel zoek systeem gemaakt voor namen van verschillende software onderdelen.

Alles staat gewoon door elkaar.

Het werkt met een xor methode dat uit de naam wordt afgeleidt.

Het schrijven kan ook snel gebeuren met dit systeem.

Als een naam wordt opgezocht dan wordt er een adres berekend met de xor methode.

Dit geheugen met adres wordt doorlopen, het bestaat uit elementen met codering en een adres

De elementen worden getest op de codering van het onderdeel waaronder de naam valt.

Indien overeenkomend zal een procedure, behorend bij de codering, worden opgeroepen die met het adres test of de naam overeenkomend is.

(er is de mogelijkheid om eerst de opgeslagen naam te converteren)

Momenteel heb ik voor mijn compiler een ruimte voor 2048 adressen genomen.

Ik wil dit verhogen zodat een groot software programma (rond de 200.000 regels) met alle poespas erom heen ongeveer gemiddeld maar 4 elementen per adres nodig heeft.

Hoeveel adressen moet ik instellen?

Hoeveel namen komt gemiddeld in een 200.00 regels programma voor?

Als dit N is komen we uit op ongeveer:

adressen=(N/4)*1.2

En we hebben het liefst een antwoord dat voldoet aan 2^X.

Met een 6 gigabyte computer is deze vraag eigenlijk irrelevant maar ik vind het onnodig om geheugen te verbruiken als het niet nodig is, andere software heeft ook geheugen nodig.

Ik zit zelf te denken aan 16384 adressen.

[virtlink]

Niet echt een antwoord op je vraag, maar:

Wat men meestal doet is de array vergroten indien nodig. Op die manier heb je niet zo'n harde limiet op het aantal namen in een programma.

Bijvoorbeeld, halverwege een klein programma zijn 10 namen bekend en is er een array van 10 elementen in gebruik. Komt er nu nog een naam bij dan zal de array vergroot moeten worden. Vaak wordt de array meer vergroot (capaciteit) dan de benodigde ruimte, omdat het vergroten een beetje tijd (milliseconden) kost. Het meest efficient in veel scenario's is om de capaciteit steeds twee maal te vergroten. Dus de nieuwe capaciteit wordt 20, met een lengte van 11. Dit vergroten doe je simpelweg met realloc in C en C++, of door de array te kopieren naar een grotere array (in java, c# en om het even welke andere programmeertaal).