Des moyens efficaces pour trouver un élément dans un tableau Javascript

Question

J'utilise un tableau avec des titres. Chaque index de titres correspond à un identifiant dans une base de données qui contient html pour ce titre donné.

Disons que j'ai une chaîne qui contient l'un des titres.

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

Pour utiliser la chaîne « titre » pour obtenir l'identifiant correspondant que je pouvais faire:

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

Une autre méthode que je pourrais utiliser est de créer un tableau associatif avec le tableau de titres qui est l'exacte opposé des titres. Autrement dit, il utilise la chaîne comme un index et renvoie le nombre.

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

Je pourrais alors accéder à l'ID par:

return titles_id[title]+1; 

Quelle serait la plus efficace compte tenu de CPU, mémoire, etc?

Aussi, s'il vous plaît laissez-moi savoir si ma logique est tout faux.

Merci Willem

Answer 1

L'approche de recherche linéaire a une complexity de O (n), et je pense que le pire des cas pour l'approche de tableau associatif est probablement O (log n), (le meilleur cas peut-être O (1) si le moteur JS utilise des hachages et n'obtient aucune collision). Cela dépendra de la façon dont un moteur JS implémente généralement associative arrays/objects, mais vous pouvez être sûr qu'il va battre O (n). Ainsi, la seconde approche sera plus rapide, mais utilisera bien sûr plus de mémoire. Ceci est un trade off très typique, en gagnant plus de vitesse, mais en utilisant plus de mémoire, et vous seul pouvez décider si vous voulez faire ce commerce.

Answer 2

Les tableaux Javascript peuvent utiliser une valeur telle que le titre "why-birds-fly" pour l'index.

Exmaple: var title = "pourquoi-les-oiseaux-volent";

var TitreArray [] = new Array();

TitleArray [title] = id;

Ensuite, vous avez un accès direct à l'id par titre:

retour TitleArray [titre];

Answer 3

Il est également important de prendre en compte le nombre de paires de valeurs clés que vous devrez stocker. Si elle est inférieure à ~ 50 (en fonction de l'implémentation), alors une recherche linéaire sera aussi efficace qu'une recherche de table de hachage, à cause du coût de calcul de la valeur de hachage et de la résolution des collisions. Une exception est le moteur Google chrome v8 JavaScript conserve une sorte de version en cache de tous les objets qui lui permettent d'effectuer une recherche directe d'une propriété sur un objet, par conséquent, l'utilisation de la classe Object comme table de hachage peut être plus rapide. Je ne sais pas si le coût de création de cette version en cache l'emportera sur les avantages pour les petites listes.

Answer 4

Vous pouvez utiliser la fonction indexOf de Array dans votre première méthode.

est Ci-dessous les informations de Mozilla Developer: https://developer.mozilla.org/En/Core_JavaScript_1.5_Reference:Objects:Array:indexOf

indexOf est une extension JavaScript à la norme ECMA-262; en tant que tel, il peut ne pas être présent dans d'autres implémentations de la norme. Vous pouvez contourner ce problème en insérant le code suivant au début de vos scripts, ce qui permet d'utiliser indexOf dans les implémentations ECMA-262 qui ne le supportent pas nativement. Cet algorithme est exactement celui utilisé dans Firefox et SpiderMonkey.

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