Eficiência de array versus object em JavaScript

Eu tenho um modelo com possivelmente milhares de objects. Eu estava me perguntando qual seria a maneira mais eficiente de armazená-los e recuperar um único object, uma vez que eu tenho o id. Os id são números longos.

Então, essas são as duas opções que eu estava pensando. na opção um é um array simples com um índice de incremento. na opção 2 é um array associativo e talvez um object, se faz diferença. Minha pergunta é qual deles é mais eficiente, quando eu mais preciso recuperar um único object, mas também às vezes percorrê-los e classificá-los.

Opção um com array não associativo:

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

Opção dois com array associativo:

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

Atualizar:

OK, eu entendo que usando uma matriz na segunda opção está fora de questão. Então a linha de declaração da segunda opção deveria ser: var a = {}; e a única questão é: o que está funcionando melhor na recuperação de um object com um determinado ID: uma matriz ou um object onde o id é a chave.

e também, a resposta mudará se eu tiver que ordenar a lista muitas vezes?

A versão curta: Arrays são na maioria das vezes mais rápidos que objects. Mas não há 100% de solução correta.

Atualização 2017 – Teste e Resultados

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

configuração de teste Resultado dos testes

Post original - Explicação

Existem alguns equívocos na sua pergunta.

Não há matrizes associativas em Javascript. Apenas matrizes e objects.

Estas são matrizes:

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

Esta é uma matriz também:

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

É basicamente uma matriz com buracos, porque cada array tem uma indexação contínua. É mais lento que matrizes sem buracos. Mas iterar manualmente pelo array é ainda mais lento (principalmente).

Este é um object:

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

Aqui está um teste de desempenho de três possibilidades:

Matriz de pesquisa vs Holey Array vs Teste de desempenho de object

Uma excelente leitura sobre esses tópicos na Smashing Magazine: Escrevendo JavaScript eficiente em memory rápida

Não é realmente uma questão de desempenho, uma vez que matrizes e objects funcionam de forma muito diferente (ou deveriam, pelo menos). Os arrays têm um índice contínuo 0..n , enquanto os objects mapeiam chaves arbitrárias para valores arbitrários. Se você quiser fornecer chaves específicas, a única opção é um object. Se você não se importa com as chaves, é uma matriz.

Se você tentar definir chaves (numéricas) arbitrárias em uma matriz, você realmente terá uma perda de desempenho, já que comportamentalmente a matriz preencherá todos os índices intermediários:

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

(Observe que a matriz não contém 99 valores undefined , mas se comportará dessa maneira, já que você deveria estar interagindo com a matriz em algum momento.)

Os literais para ambas as opções devem deixar bem claro como eles podem ser usados:

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

Com o ES6, o caminho mais eficaz seria usar um mapa.

 var myMap = new Map(); myMap.set(1, 'myVal'); myMap.set(2, { catName: 'Meow', age: 3 }); myMap.get(1); myMap.get(2); 

Você pode usar os resources do ES6 hoje usando um shim ( https://github.com/es-shims/es6-shim ).

O desempenho irá variar dependendo do navegador e do cenário. Mas aqui está um exemplo em que o Map é mais eficiente: https://jsperf.com/es6-map-vs-object-properties/2


REFERÊNCIA https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Map

Eu tentei levar isso para a próxima dimensão, literalmente.

Dado um array bidimensional, no qual os eixos xey são sempre do mesmo tamanho, é mais rápido:

a) procure a célula criando uma matriz bidimensional e procurando o primeiro índice, seguido pelo segundo índice, ou seja:

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

ou

b) crie um object com uma representação de string das coordenadas x e y e, em seguida, faça uma única pesquisa nesse obj, ou seja:

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

Resultado:
Acontece que é muito mais rápido fazer duas pesquisas de índice numérico nos arrays do que uma pesquisa de propriedade no object.

Resultados aqui:

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

Depende do uso. Se o caso for lookup, os objects são muito mais rápidos.

Aqui está um exemplo de Plunker para testar o desempenho de pesquisas de matriz e object.

https://plnkr.co/edit/n2expPWVmsdR3zmXvX4C?p=preview

Você vai ver isso; Procurando por 5.000 itens em coleção de array de 5.000 de comprimento, assuma 3000 milissegundos

No entanto, procurar 5.000 itens no object tem 5.000 propriedades, levar apenas 2 ou 3 milissegundos

Também fazendo tree de objects não faz grande diferença

No NodeJS, se você conhece o ID , o loop através do array é muito lento comparado ao 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 

E os resultados:

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

Mesmo se o ID de busca for o primeiro na matriz / object:

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