Binäre Suche und sortiertes Einfügen für JavaScript-Arrays

[Rüdiger]

In ABAP gibt es drei Grundtypen (Zugriffsarten) von internen Tabellen:
Die Standardtabellen, die sortierten und die Hashtabellen. Sie
unterscheiden sich durch den Zugriff. Der Zugriff auf Standardtabellen
erfolgt mit linearer, auf sortierte Tabellen mit binärer Suche,
während die Einträge von Hashtabellen mit Hilfe einer auf die
Schlüsselwerte angewandten Hashfunktion verwaltet werden.

Die beste Zugriffsart für eine bestimmte interne Tabelle ergibt sich
daher aus ihrer Verwendung. Wenn gar keine Lesezugriffe erfolgen,
sondern die Tabelle nur in einer Schleife durchlaufen wird, empfiehlt
sich die Standardtabelle. Wenn es vor allem Lesezugriffe mit voll
spezifiziertem Schlüssel gibt, ist meist die Hashtabelle die richtige
Wahl.

Die sortierte Tabelle ist ein Mittelding zwischen beiden: Lesezugriffe
mit gegebenem Schlüssel sind schlechter als die der Hashtabelle, aber
besser als die der Standardtabelle. Dafür erlaubt sie aber auch wie
eine Standardtabelle den Zugriff via Index. Zu einer sortierte Tabelle
ist beispielsweise zu raten, wenn Teile der Tabelle in einer Schleife
durchlaufen werden müssen. So kann eine Tabelle mit Belegpositionen
die Schlüsselfelder Beleg- und Positionsnummer enthalten. Man möchte
nun die Positionen eines bestimmten Belegs der Tabelle bearbeiten.
Dann findet das System mit binärer Suche die erste Position des Belegs
und läuft dann über diese und die nachfolgenden Zeilen, bis die
Belegnummer wechselt.

Wie ist es in JavaScript? JavaScript kennt "Standardtabellen", das
sind die Objekte der Klasse Array, die wie in folgendem Beispiel
gebildet werden:

var x = [1,2,"a",3];
alert( x[2] ); // Gibt a aus


Und natürlich kennt JavaScript Hashs - Hashtabellen sind *die*
zentrale Datenstruktur in JavaScript. Es ist i.w. korrekt, wenn man
sagt: In JavaScript ist alles ein Hash! Auch hierfür ein Beispiel:


var y = { a:1, b:2, c:3 };
alert( y.b ); // Gibt 2 aus alert( y["b"] ); // Ebenso


Sortierte Tabellen aber gibt es nicht. Wohl bietet das Objekt Array
die Funktion sort( cmp ), wobei das optionale Argument cmp die
Referenz auf eine eigene Vergleichsfunktion ist (ist sie nicht
angegeben, werden die Arrayelemente in Strings konvertiert und als
Strings, also lexikographisch verglichen). Aber der *binäre Zugriff*,
der auf einer mit Array.sort() sortierten Tabelle möglich ist, fehlt
im Standardobjekt Array.


Es hat sich mir als sinnvoll gezeigt, den binären Zugriff dem globalen
Array-Objekt hinzuzufügen:


// Binäre Suche, Rückgabewert wie in java.util.Arrays.binarySearch()
Array.prototype.binarySearch = function(v,cmp){
if (this.length === 0) return -1;
var high = this.length, low = -1, m, el;
while(high - low > 1) {
el = this[m = high + low >> 1];
if (cmp ? cmp(el,v) < 0 : el < v) {
low = m;
}
else {
high = m;
}
}
return (high == this.length) ||
(cmp ? cmp(this[high],v) : this[high] != v) ?
-high-1 : high ;
};


Ist der Rückabewert, eine ganze Zahl, nichtnegativ, so wurde das
Element v im Array gefunden, und die Zahl gibt den Index des Elements
an. Ist der Rückgabewert negativ, so wurde das Element nicht gefunden:
-1 bedeutet, dass v "kleiner" als das Arrayelement 0 ist. -2 bedeutet,
dass v zwischen den Elementen 0 und 1 einzuordnen ist, und so weiter.
Das ist genau die in der Methode java.util.Arrays.binarySearch()
verwendete Konvention; sie hat den Vorteil, dass wir nur einen
Rückgabewert benötigen, der die gesamte Information über das
Suchergebnis enthält.


Die Methode setzt natürlich voraus, dass der Array, auf den sie
angewendet wird, im Sinne der Vergleichsfunktion cmp sortiert ist. Ist
er das nicht, so ist das Ergebnis von binarySearch() undefiniert.

Aufbauend auf dieser Methode können wir nun für sortierte Arrays eine
weitere Methode definieren, die ähnlich wie der Open SQL Befehl MODIFY
funktioniert: Ein Wert v (ein Record, ein Objekt,...) ersetzt einen
etwa schon bestehenden Arrayeintrag, der gemäss der Ordnungsrelation
cmp mit v "übereinstimmt" (z.B. den gleichen Key hat). Wenn der Wert
dagegen im Array gemäss der Ordnungsrelation cmp noch nicht existiert,
wird er an der richtigen Stelle eingefügt, nämlich so, dass die
Sortierung erhalten bleibt.


Array.prototype.modifySorted = function( entry, cmp ) {
var i;
if (this.length === 0) {
this.push( entry );
}
else {
i = this.binarySearch( entry, cmp );
if (i>=0) {
// Zeile existiert - überschreiben
this[i] = entry;
}
else if (-i <= this.length) {
// Zeile muss inmitten der bestehenden Zeilen eingefügt werden
this.splice( -i-1, 0, entry );
}
else {
// Zeile muss am Ende angefügt werden
this.push(entry);
}
}
return this;
}


--
Subscription settings: http://groups.google.com/group/bsp-praxis/subscribe?hl=de