Efficacité des tableaux et des objets en JavaScript

Question

J'ai un modèle avec des milliers d'objets. Je me demandais quelle serait la manière la plus efficace de les stocker et de retrouver un seul objet une fois que j'ai son identifiant. Les identifiants sont des nombres longs.

Dans l'option 1, il s'agit d'un tableau simple avec un index incrémentiel. Dans l'option 2, il s'agit d'un tableau associatif et peut-être d'un objet, si cela fait une différence. Ma question est de savoir laquelle est la plus efficace, lorsque j'ai besoin de récupérer un seul objet, mais aussi parfois de les parcourir en boucle et de les trier.

Option 1 avec un tableau non associatif :

var a = [{id: 29938, name: 'name1'},
         {id: 32994, name: 'name1'}];
function getObject(id) {
    for (var i=0; i < a.length; i++) {
        if (a[i].id == id) 
            return a[i];
    }
}

Option deux avec tableau associatif :

var a = [];  // maybe {} makes a difference?
a[29938] = {id: 29938, name: 'name1'};
a[32994] = {id: 32994, name: 'name1'};
function getObject(id) {
    return a[id];
}

Mise à jour :

OK, je comprends que l'utilisation d'un tableau dans la deuxième option est hors de question. Donc la ligne de déclaration de la deuxième option devrait être : var a = {}; La seule question qui se pose est la suivante : qu'est-ce qui est le plus performant pour récupérer un objet avec un identifiant donné : un tableau ou un objet dont l'identifiant est la clé.

Et aussi, la réponse changera-t-elle si je dois trier la liste plusieurs fois ?

Answer 1

La version courte : Les tableaux sont généralement plus rapides que les objets. Mais il n'y a pas de solution 100% correcte.

Mise à jour 2017 - Test et résultats

var a1 = [{id: 29938, name: 'name1'}, {id: 32994, name: 'name1'}];

var a2 = [];
a2[29938] = {id: 29938, name: 'name1'};
a2[32994] = {id: 32994, name: 'name1'};

var o = {};
o['29938'] = {id: 29938, name: 'name1'};
o['32994'] = {id: 32994, name: 'name1'};

for (var f = 0; f < 2000; f++) {
    var newNo = Math.floor(Math.random()*60000+10000);
    if (!o[newNo.toString()]) o[newNo.toString()] = {id: newNo, name: 'test'};
    if (!a2[newNo]) a2[newNo] = {id: newNo, name: 'test' };
    a1.push({id: newNo, name: 'test'});
}

Poste original - Explication

Il y a quelques idées fausses dans votre question.

Il n'y a pas de tableaux associatifs en Javascript. Seulement des tableaux et des objets.

Ce sont des tableaux :

var a1 = [1, 2, 3];
var a2 = ["a", "b", "c"];
var a3 = [];
a3[0] = "a";
a3[1] = "b";
a3[2] = "c";

C'est aussi un tableau :

var a3 = [];
a3[29938] = "a";
a3[32994] = "b";

Il s'agit en fait d'un tableau avec des trous, car tous les tableaux ont une indexation continue. C'est plus lent que les tableaux sans trous. Mais itérer manuellement dans le tableau est encore plus lent (en général).

C'est un objet :

var a3 = {};
a3[29938] = "a";
a3[32994] = "b";

Voici un test de performance de trois possibilités :

Test de performance entre tableau de consultation et tableau de Holey et objet

Une excellente lecture sur ces sujets à Smashing Magazine : Écriture de JavaScript rapide et efficace en mémoire

Answer 2

Ce n'est pas vraiment une question de performances, puisque les tableaux et les objets fonctionnent de manière très différente (ou sont censés le faire, du moins). Les tableaux ont un index continu 0..n tandis que les objets font correspondre des clés arbitraires à des valeurs arbitraires. Si vous veulent fournir des clés spécifiques, le seul choix est un objet. Si vous ne vous souciez pas des clés, un tableau sera utilisé.

Si vous essayez de définir des clés (numériques) arbitraires sur un tableau, vous avez vraiment un problème de performance. perte puisque, d'un point de vue comportemental, le tableau remplira tous les index entre les deux :

> foo = [];
  []
> foo[100] = 'a';
  "a"
> foo
  [undefined, undefined, undefined, ..., "a"]

_{(Notez que le tableau n'est pas <em>en fait </em>contenir 99 <code>undefined</code> mais il se comportera de cette façon puisque vous êtes [censé être] <em>itératif </em>le tableau à un moment donné).}

Les littéraux de ces deux options doivent indiquer très clairement comment elles peuvent être utilisées :

var arr = ['foo', 'bar', 'baz'];     // no keys, not even the option for it
var obj = { foo : 'bar', baz : 42 }; // associative by its very nature

Answer 3

Avec ES6, le moyen le plus performant serait d'utiliser une carte.

var myMap = new Map();

myMap.set(1, 'myVal');
myMap.set(2, { catName: 'Meow', age: 3 });

myMap.get(1);
myMap.get(2);

Vous pouvez utiliser les fonctionnalités ES6 aujourd'hui en utilisant une shim ( https://github.com/es-shims/es6-shim ).

Les performances varient en fonction du navigateur et du scénario. Mais voici un exemple où Map est le plus performant : https://jsperf.com/es6-map-vs-object-properties/2

---

RÉFÉRENCE https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Map

Answer 4

Sur NodeJS si vous connaissez le ID le bouclage à travers le tableau est très lent comparé à object[ID] .

const uniqueString = require('unique-string');
const obj = {};
const arr = [];
var seeking;

//create data
for(var i=0;i<1000000;i++){
  var getUnique = `${uniqueString()}`;
  if(i===888555) seeking = getUnique;
  arr.push(getUnique);
  obj[getUnique] = true;
}

//retrieve item from array
console.time('arrTimer');
for(var x=0;x<arr.length;x++){
  if(arr[x]===seeking){
    console.log('Array result:');
    console.timeEnd('arrTimer');
    break;
  }
}

//retrieve item from object
console.time('objTimer');
var hasKey = !!obj[seeking];
console.log('Object result:');
console.timeEnd('objTimer');

Et les résultats :

Array result:
arrTimer: 12.857ms
Object result:
objTimer: 0.051ms

Même si l'ID de recherche est le premier dans le tableau/objet :

Array result:
arrTimer: 2.975ms
Object result:
objTimer: 0.068ms

Answer 5

J'ai essayé de passer à la dimension suivante, littéralement.

Étant donné un tableau à deux dimensions, dans lequel les axes x et y sont toujours de la même longueur, est-il plus rapide de :

a) rechercher la cellule en créant un tableau à deux dimensions et en recherchant le premier indice, suivi du second indice, c'est-à-dire

var arr=[][]    
var cell=[x][y]    

ou

b) créer un objet avec une représentation sous forme de chaîne de caractères des coordonnées x et y, puis effectuer une seule recherche sur cet objet, à savoir

var obj={}    
var cell = obj['x,y']    

Résultat :
Il s'avère qu'il est beaucoup plus rapide de faire deux recherches d'index numériques sur les tableaux, qu'une recherche de propriété sur l'objet.

Résultats ici :

http://jsperf.com/arr-vs-obj-lookup-2