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 contenant du code HTML pour ce titre donné.

Disons que j'ai une chaîne de caractères contenant 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, je pourrais le faire:

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

Une autre méthode que je pourrais utiliser consiste à créer un tableau associatif avec le tableau Titres, qui est exactement le contraire de titres. Autrement dit, il utilise la chaîne en tant qu’index et renvoie le nombre.

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

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

return titles_id[title]+1;

Qu'est-ce qui serait le plus efficace compte tenu du processeur, de la mémoire, etc.?

Faites-moi également savoir si ma logique est entièrement fausse.

Merci Willem

Answer 1

La méthode de recherche linéaire a une complexité de O (n), et je pense que le pire Le 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'entraîne aucune collision). Cela dépendra de la façon dont un moteur JS implémentera généralement tableaux / objets associatifs , mais vous pouvez le faire. bien sûr, il battra O (n).

Ainsi, la deuxième approche sera plus rapide, mais utilisera bien sûr plus de mémoire. Ceci est un compromis très typique, gagnant plus de vitesse, mais utilisant plus de mémoire, et seulement vous pouvez décider si vous voulez faire ce commerce.

Answer 2

Il est également important de prendre en compte le nombre de paires clé-valeur que vous devrez stocker. Si sa valeur est inférieure à ~ 50 (selon l'implémentation), effectuer une recherche linéaire sera aussi efficace qu'une recherche de table de hachage, en raison du coût de calcul de la valeur de hachage et de résolution des collisions. Le moteur JavaScript de Google Chrome v8 constitue une exception. Il conserve une sorte de version en cache de tous les objets, ce qui lui permet de rechercher directement une propriété sur un objet. Par conséquent, l'utilisation de la classe Object comme table de hachage peut être plus rapide. ne sais pas si le coût de la création de cette version en cache compensera les avantages des listes plus petites.

Answer 3

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

Vous trouverez ci-dessous les informations provenant du développeur Mozilla: https://developer.mozilla.org/En/Core_JavaScript_1.5_Reference: Objets: Tableau: indexOf

indexOf est une extension JavaScript de 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 prennent pas en charge de manière native. 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;
   };
}

Answer 4

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

Exemple:   var title = "Pourquoi-oiseaux-mouches";

var TitleArray [] = new Array ();

TitleArray [title] = id;

Vous avez alors un accès direct à l'id par titre:

Renvoyer TitleArray [title];