[JAVA] efficiente translatie map

[tweakerbee]

Op het moment zoek ik een efficiente manier om een soort van vertaal tabel te maken (in Java). De bedoeling is dat er entries in komen waarbij karakteroffsets vertaald worden van het ene systeem naar het andere.

De gegevensstructuur is ongeveer als volgt:

code:

0, 0
10, 8
15, 12

Nu moet op het moment dat de waarde 11 vertaald moet worden daar het getal 9 uitkomen. Op 10 waren er namelijk 8 echte characters weggeschreven, plus het verschil tussen de 10 en 11.

Elke keer als er een verschil geintroduceerd wordt kan er namelijk een waardepaar toegevoegd worden. Ik zat zelf te denken aan het maken van een simpele twee dimensionale array of Vector en die elke keer maar te doorlopen. Hij gaat dan op zoek naar de hoogst mogelijke waarde die de gezochte waarde nog niet overschrijdt en telt dan het verschil erbij op.

Dat lijkt me echter niet zo'n efficiente implementatie. Bij vrijwel alle datastructuren loop ik tegen het probleem aan dat de waarde die ik zoek niet persé direct in de vertaaltabel hoeft te staan.

Alternatief zou zijn om voor elk teken een offset waarde in te voegen. Dit zorgt wel voor een hele snelle lookup, maar het geheugenverbruik schiet waarschijnlijk wel de pan uit. Het gaat om teksten van enkele honderden KB's tot wel enkele MB's. Geheugengebruik van enkele MB's is in ieder geval niet de bedoeling.

Zijn er betere ideeën, of een goede voor of tegen van een van de twee aanpakken?

[DaCoTa]

Kijk eens naar TreeMap en TreeMap.tailMap(T key).

[tweakerbee]

Dat ziet er inderdaad erg handig uit. Of het performance-wise uitmaakt op een goede array/loop implementatie betwijfel ik, maar het scheelt in ieder geval een hoop code.
Ook handig is dat die dingen in een keer te Serializen zijn als ik ze zou willen cachen.

edit:

Hmm.. Janoz heeft natuurlijk hartstikke gelijk.

[ Voor 13% gewijzigd door tweakerbee op 17-01-2007 17:39 ]

[Janoz]

In een tree zoek je met Log(N). In een Array/loop implementatie met N. Zeker weten dat het verschil uitmaakt.

[Soultaker]

In een gesorteerde array zoek je ook met in O(log N). Als je je tabel niet vaak updatet, is het zelfs aan te raden een array te gebruiken omdat die veel minder geheugen gebruikt.

Voorbeeld:

Java:

int pos = 11;
int[] a = new int[] {  0, 10, 15 };
int[] b = new int[] {  0,  8, 12 };

int lo = 0, hi = a.length - 1;
while(lo < hi) {
    int mid = lo + (hi - lo + 1)/2;
    if(a[mid] > pos)
        hi = mid - 1;
    else
        lo = mid;
}
// a[lo] is nu het grootste getal kleiner dan of gelijk aan pos
pos = pos - a[lo] + b[lo];

Een gedetailleerde uitleg kun je bijvoorbeeld hier vinden: Binary Search
Van belang is dus dat de array waarin je zoekt gesorteerd is.

[ Voor 4% gewijzigd door Soultaker op 17-01-2007 19:48 ]