grosse arrays schnell durchsuchen

[Manuel]

Hallo,

wenn ich in einem großen Array prüfen will, ob ein Element bereits enthalten ist, muss ich ja zb mit einer for-schleife drüber jagen und zeile für zeile vergleichen.
also im prinzip:
for (blabla mit i und i++ ) {
  if (arr[i] == suchwert) alert('vorhanden');
}

Daher die Frage: ist es schneller, wenn ich das ganze als assoziativarray baue und dann eben nur ein:

if (arr[0][suchwert] != null) alert('vorhanden');

mache? Ich denke, bei großen Arrays dürfte das deutlich schneller sein, aber ich weiss halt nicht, wie javascript das im Hintergrund arangiert. Weiss das jemand? ;)

Dank und Gruß,
Manu

[Struppi]

Daher die Frage: ist es schneller, wenn ich das ganze als assoziativarray baue und dann eben nur ein:

if (arr[0][suchwert] != null) alert('vorhanden');

Warum probierst du es nicht aus?

mache? Ich denke, bei großen Arrays dürfte das deutlich schneller sein, aber ich weiss halt nicht, wie javascript das im Hintergrund arangiert. Weiss das jemand? ;)

Nein, In der Regel sind Array immer schneller.

Struppi.

[yetanotheruser]

Wenn es ein Array mit sortierbaren Werten ist, dann kannst du es schon etwas schneller machen.

Zunächst einmal das Array sortieren, dann Einfügen von Elementen nur noch über Funktionen, die das Element an die richtige Stelle im Array packen. Und wenn du dann schauen willst, ob ein Element im Array enthalten ist, dann wendest du eine binäre Suche auf das Element an, somit sparst du dir einige Vergleiche.

Gruß Ben

[Struppi]

Zunächst einmal das Array sortieren, dann Einfügen von Elementen nur noch über Funktionen, die das Element an die richtige Stelle im Array packen. Und wenn du dann schauen willst, ob ein Element im Array enthalten ist, dann wendest du eine binäre Suche auf das Element an, somit sparst du dir einige Vergleiche.

Wie sieht denn eine binäre Suche mit Javascript aus?

Struppi.

[molily]

Hallo,

Wie sieht denn eine binäre Suche mit Javascript aus?

Ich habe keine Informatikausbildung, aber ich denke einmal, in etwa so:

var array = new Array();  
for (var i = 0, random; i < 1000; i++) {  
 random = Math.random()  
 array.push(random);  
}  
array.sort();  
//document.write("<p>" + array.join("<br>") + "</p>");  
  
suchwert = random;  
document.write("<p>suchwert: " + suchwert + "</p>");  
  
function suche (array, suchwert, index_start, index_end) {  
 index_start = index_start || 0;  
 index_end = index_end || array.length;  
  
 document.write("<p>suche " + index_start + "-" + index_end + "<br>");  
  
 index_mitte = Math.floor(index_start + ((index_end - index_start) / 2));  
 document.write("mitte: " + index_mitte + " : " +  array[index_mitte] + "<br>");  
 if (array[index_mitte] == suchwert) {  
  document.write("gefunden");  
  return true;  
 }  
 if (suchwert < array[index_mitte]) {  
  document.write("suchwert kleiner<br>");  
  return suche(array, suchwert, index_start, index_mitte);  
 } else {  
  document.write("suchwert größer<br>");  
  return suche(array, suchwert, index_mitte, index_end);  
 }  
 return false;  
}  
  
document.write("<p>" + suche(array, suchwert) + "</p>");

Das ist natürlich, wenn man einen geordneten Array hat, viel schneller als das bloße Durchlaufen mit einer for-Schleife.

Mathias

[molily]

Hallo,

wenn ich in einem großen Array prüfen will, ob ein Element bereits enthalten ist, muss ich ja zb mit einer for-schleife drüber jagen und zeile für zeile vergleichen.
also im prinzip:
for (blabla mit i und i++ ) {
  if (arr[i] == suchwert) alert('vorhanden');
}

Hier suchst du nach einem Wert eines Array-Elements mit einer bestimmten Nummer.

Daher die Frage: ist es schneller, wenn ich das ganze als assoziativarray baue und dann eben nur ein:

if (arr[0][suchwert] != null) alert('vorhanden');

mache?

So kannst du überprüfen, ob arr[0] ein Unterobjekt mit dem in suchwert gespeicherten Namen hat.

Ich verstehe den Vergleich nicht.

Vorab, »Assoziative Arrays« gibt es in JavaScript nicht, das sind bloße Object-Strukturen ohne die spezifischen Array-Eigenschaften.

Speicherst du bloß Werte oder Namen-Werte-Paare bzw. Nummern-Werte-Paare? Suchst du nach Namen oder nach Werten?

Wenn du bloß Werte speicherst und überprüfen willst, ob ein Werte schon gespeichert wurde, dann ein nimm ein Object.

var object = new Object();
object["name1"] = true;
object["name2"] = true;

Dann kannst du schnell mit if (object["name1"]) abfragen, ob dieser Wert gespeichert wurde. In dem Fall ist ein Object natürlich besser als ein Array, denn einen Array müsstest du durchlaufen.

Wenn du Name-Werte-Paare bzw. Nummer-Werte-Paare speichern willst, dann ist es entscheidend, ob du nach einem Namen oder nach einem Wert suchst.

Wenn der Name oder eine Nummer gegeben und der zugehörige Wert gesucht ist (bzw. geprüft werden soll, ob ein Eintrag unter dem Namen vorliegt), so geben sich Array und Object wahrscheinlich nichts. Hast du einen Array, so kannst du mit if (array[1234]) oder if (typeof a[1234] != "undefined") überprüfen, ob ein Wert unter der Nummer gespeichert ist und auf dieselbe Art den Wert abfragen. Hast du ein Object, so geht es mit if (object["1234"]) bzw. object["1234"] zum Abfragen des Wertes wahrscheinlich genauso schnell. Intern werden sowieso binäre Bäume verwendet.

Wenn der Wert gegeben ist und der zugehörige Name bzw. die Nummer gesucht ist (bzw. geprüft werden soll, ob ein Eintrag mit dem Wert vorliegt), so geben sich Array und Object wahrscheinlich auch nichts. Wenn du ein Object benutzt und nach einem Unterobjekt mit einem bestimmten Wert suchst, musst du die Unterobjekte des Objects genauso durchlaufen wie die Elemente des Arrays (for-in-Schleife). Ich wüsste auch nich, wie man in dem Fall mit binären Bäumen weiterkäme. Eher wäre ein zusätzliches Object denkbar, in den die Werte eingetragen werden, sozusagen ein Index. Also dieselbe Datenstruktur, nur Namen/Nummern und Werte sind vertauscht. Dann ist das einfache Nachschlagen über object["wert"] möglich. Der Wert müsste dann natürlich als String ausdrückbar sein.

Ich verstehe nicht ganz, in welchem Fall es einen Sinn hätte, selbst einen binären Baum in Javascript zu implementieren.

Mathias