Suchen in unsortiertem Array of Integer beschleunigen.

[Satty67]

Ich hoffe, dass ich bis zum Wochenende das System fertig hab'. Auf der ToDo Liste ist nicht mehr viel und auch fast nur noch Kosmetik.

Dann poste ich das komplette Paket samt Demo-Programm. Da seht Ihr dann besser, wie man das am besten lösen könnte.

[Satty67]

Ok, das ganze Paket dauert noch eine Weile, hab' mich entschlossen noch ein paar Funktionen zuzufügen, bevor ich es freigebe. Aber zum Problem habe ich eben eine Lösung gefunden:

Der Index enthält jetzt zwei Werte: Offset (in der Datei) und UnsortedAnc (Vorfahre in der unsortierten Liste). Sind bei 1 Mio. Einträgen nur 4 MByte. Nach dem Sortieren wird UnsortedAnc einmal angepasst (das optimiere ich noch, damit es während dem Sortieren passiert). Sortieren dauert ein paar ms. länger, aber da nur einmal, fällt das nicht wirklich ins Gewicht.

Da ich immer nur den Index-Eintrag mit dem höchsten Offset-Eintrag brauche und nicht einen beliebigen Offset suchen muss, reicht das. Eine private Variable der Index-Klasse merkt sich den Index mit dem höchsten Offset. Soll der gelöscht werden, wir die Variable zuvor mit UnsortedAnc aus diesem Index aktualisiert. Somit hab' ich keine n-Zugriffe mehr, sondern nur noch einen + neue Zuweisung. Zudem ist es der gleiche Code, egal ob der Index sortiert oder unsortiert vorliegt.

Tree's verstehe ich, aber strengen mich an. Skiplisten verstehe ich (noch) nicht... auf jeden Fall ist mir im Moment die klassische Lösung am liebsten ;)