Effektive Möglichkeiten zur Herstellung eines Elements in einer Javascript-Array zu finden,

Question

Ich verwende ein Array mit Titeln. Jeder Titel Index entspricht eine ID in einer Datenbank, die HTML-Code für den gegebenen Titel enthält.

Lassen Sie uns sagen ich eine Zeichenfolge haben, die einen der Titel enthält.

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

die Zeichenfolge „title“ So verwenden Sie 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 verwenden könnte, ist ein assoziatives Array zusammen mit dem Titel Array zu erstellen, die das genaue Gegenteil von Titeln. Das heißt, die Zeichenfolge als Index verwendet und gibt die Nummer ein.

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

Ich konnte dann die ID zugreifen:

return titles_id[title]+1;

Was am wirksamsten wäre angesichts CPU, Speicher, etc?

Auch, lassen Sie es mich wissen, wenn meine Logik ist alles falsch.

Danke Willem

Answer 1

Der lineare Suchansatz hat ein Komplexität von O (n), und ich denke, das Schlimmste Fall für den assoziativen Array Ansatz ist wahrscheinlich O (lügen n), (die am besten Fall vielleicht O (1), wenn die JS Motor-Hashes und bekommen keine Kollisionen verwendet). Es wird davon abhängen, wie eine JS-Engine implementiert typischerweise assoziative Arrays / Objekte , aber Sie können sein sicher, dass es schlagen O (n).

So wird der zweite Ansatz schneller sein, aber natürlich mehr Speicherplatz. Dies ist eine sehr typische Trade-off , mehr Geschwindigkeit zu gewinnen, aber mit mehr Speicher, und nur Sie können entscheiden, ob Sie, dass der Handel machen wollen.

Answer 2

Es ist auch wichtig, die Anzahl der Schlüssel-Wert-Paare betrachten Sie speichern benötigen. Wenn es weniger als ~ 50 (je nach Ausführung) dann eine lineare Suche tun wird so effizient sein wie eine Hash-Lookup-Tabelle zu tun, wegen der Kosten für den Hash-Wert zu berechnen und zu lösen Kollisionen. Eine Ausnahme ist die Google Chrome v8 JavaScript-Engine eine Art Cache-Version aller Objekte hält, dass es einen direkten Nachschlagen einer Eigenschaft auf einem Objekt ausführen können, also die Verwendung der Object-Klasse als eine Hash-Tabelle schneller sein kann, obwohl ich ist nicht sicher, ob die Kosten für diese Cache-Version schaffen werden den Nutzen für kleinere Listen aufwiegen.

Answer 3

Sie können die indexOf verwenden Funktion von Array in Ihrem ersten Verfahren.

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

indexOf ist eine JavaScript-Erweiterung des ECMA-262-Standard; als solche in anderen Implementierungen des Standards dürfen nicht vorhanden sein. Sie können durch Einfügen des folgenden Code am Anfang Ihres Skripts dieses Problem umgehen, so dass die Verwendung von indexOf in ECMA-262-Implementierungen, die nativ es nicht unterstützen. Dieser Algorithmus ist genau derjenige verwendet in Firefox und Spider.

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;
   };
}

Answer 4

Javascript-Arrays kann einen Wert wie der Titel verwenden "warum Vögel-fly" für den Index.

Exmaple:   var title = "warum Vögel-fly";

var TitleArray [] = new Array ();

TitleArray [title] = id;

Dann haben Sie direkten Zugriff auf die ID nach Titel:

zurückkehren TitleArray [title];