Effektive Möglichkeiten, ein Element in einem Javascript-Array zu finden

Question

Ich verwende ein Array mit Titeln. Jeder Titelindex entspricht einer ID in einer Datenbank, die HTML für diesen gegebenen Titel enthält.

Sagen wir, ich habe eine Zeichenfolge, die einen der Titel enthält.

title = "why-birds-fly"; 
titles[] // an array which contains all the titles 

Um die Zeichenfolge „title“ zu verwenden, um die entsprechende ID zu bekommen was ich tun konnte:

for (i = 0; i < titles.length-1; i++) { 
    if (titles[i] == title) 
    return i+1; 
} 

Eine andere Methode, die ich ist verwenden könnte ein assoziatives Array mit dem Titel-Array, das die genaue ist zu schaffen Gegenteil von Titeln. Das heißt, es verwendet die Zeichenfolge als Index und gibt die Zahl zurück.

titles_id {blah:0,why-birds-fly:1,blah2:2} 

ich dann die ID zugreifen konnte:

return titles_id[title]+1; 

Was am effektivsten wäre, CPU, Speicher bedenkt, etc?

Bitte lassen Sie mich auch wissen, wenn meine Logik falsch ist. vielleicht

Dank Willem

Answer 1

Die lineare Suche Ansatz hat eine complexity von O (n), und ich denke, der schlimmste Fall für den Ansatz assoziatives Array ist wahrscheinlich O (log n), (die besten Fall O (1) wenn die JS-Engine Hashes verwendet und keine Kollisionen erhält). Es hängt davon ab, wie eine JS-Engine normalerweise associative arrays/objects implementiert, aber Sie können sicher sein, dass es O (n) übertrifft.

Also, der zweite Ansatz wird schneller sein, wird aber natürlich mehr Speicher verwenden. Dies ist eine sehr typische trade off, gewinnt mehr Geschwindigkeit, aber mit mehr Speicher, und nur Sie können entscheiden, ob Sie diesen Handel machen wollen.

Answer 2

Javascript-Arrays können einen Wert wie den Titel "why-birds-fly" für den Index verwenden.

Beispiel: var title = "why-birds-fly";

var TitelArray [] = new Array();

TitelArray [title] = id;

Dann haben Sie direkten Zugriff auf die ID nach Titel:

Rückkehr TitleArray [title];

Answer 3

Es ist auch wichtig, die Anzahl der Schlüsselwertpaare zu berücksichtigen, die Sie speichern müssen. Wenn es weniger als 50 ist (abhängig von der Implementierung), dann ist das Ausführen einer linearen Suche genauso effizient wie das Durchführen einer Hashtabellensuche, aufgrund der Kosten zum Berechnen des Hash-Werts und zum Auflösen von Kollisionen. Eine Ausnahme ist, dass die Google Chrome v8 JavaScript-Engine eine Art zwischengespeicherte Version aller Objekte speichert, die es ermöglichen, eine Eigenschaft auf einem Objekt direkt nachzuschlagen, daher kann die Verwendung der Object-Klasse als Hash-Tabelle schneller sein, obwohl ich bin mir nicht sicher, ob die Kosten für das Erstellen dieser zwischengespeicherten Version den Vorteil für kleinere Listen überwiegen.

Answer 4

Sie können die indexOf-Funktion von Array in Ihrer ersten Methode verwenden.

Im Folgenden finden Sie die Informationen von Mozilla Developer: https://developer.mozilla.org/En/Core_JavaScript_1.5_Reference:Objects:Array:indexOf

indexOf ist eine JavaScript-Erweiterung des ECMA-262-Standard; als solche kann es in anderen Implementierungen des Standards nicht vorhanden sein. Sie können dies umgehen, indem Sie den folgenden Code am Anfang Ihrer Skripte einfügen, sodass indexOf in ECMA-262-Implementierungen verwendet werden kann, die diese nicht nativ unterstützen. Dieser Algorithmus ist genau der, der in Firefox und SpiderMonkey verwendet wird.

if (!Array.prototype.indexOf) 
{ 
    Array.prototype.indexOf = function(elt /*, from*/) 
    { 
    var len = this.length >>> 0; 

    var from = Number(arguments[1]) || 0; 
    from = (from < 0) 
     ? Math.ceil(from) 
     : Math.floor(from); 
    if (from < 0) 
     from += len; 

    for (; from < len; from++) 
    { 
     if (from in this && 
      this[from] === elt) 
     return from; 
    } 
    return -1; 
    }; 
}