Mam model z prawdopodobnie tysiącami obiektów. Zastanawiałem się, jaki byłby najskuteczniejszy sposób przechowywania ich i pobierania pojedynczego obiektu, gdy mam jego identyfikator. Identyfikatory to długie liczby.

Więc to są 2 opcje, o których myślałem. w opcji pierwszej jest to prosta tablica z rosnącym indeksem. w opcji 2 jest to tablica asocjacyjna i być może obiekt, jeśli ma znaczenie. Moje pytanie brzmi, który z nich jest bardziej wydajny, gdy najczęściej potrzebuję pobrać pojedynczy obiekt, ale czasami też przechodzę przez niego w pętli i sortuję.

Opcja pierwsza z tablicą nieasocjacyjną:

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

Opcja druga z tablicą asocjacyjną:

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

Aktualizacja:

OK, rozumiem, że użycie tablicy w drugiej opcji jest wykluczone. Zatem w linii deklaracji druga opcja naprawdę powinna brzmieć: var a = {};a jedyne pytanie brzmi: co działa lepiej w pobieraniu obiektu o podanym identyfikatorze: tablica lub obiekt, w którym id jest kluczem.

a także, czy odpowiedź ulegnie zmianie, jeśli będę musiał wielokrotnie sortować listę?

Krótka wersja: tablice są przeważnie szybsze niż obiekty. Ale nie ma 100% poprawnego rozwiązania.

Aktualizacja 2017 - Test i wyniki

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

Oryginalny post - wyjaśnienie

Twoje pytanie zawiera nieporozumienia.

W JavaScript nie ma tablic asocjacyjnych. Tylko tablice i obiekty.

Oto tablice:

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

To też jest tablica:

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

Zasadniczo jest to tablica z dziurami, ponieważ każda tablica ma ciągłe indeksowanie. Jest wolniejszy niż tablice bez otworów. Ale ręczne iterowanie po tablicy jest jeszcze wolniejsze (głównie).

To jest obiekt:

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

Oto test wydajności obejmujący trzy możliwości:

Tablica odnośników a tablica dziurawych vs test wydajności obiektu

Doskonała lektura na te tematy w Smashing Magazine: Pisanie szybko wydajnego pamięciowo JavaScript

To wcale nie jest kwestia wydajności, ponieważ tablice i obiekty działają bardzo różnie (lub przynajmniej powinny). Tablice mają ciągły indeks 0..n, podczas gdy obiekty odwzorowują dowolne klucze na dowolne wartości. Jeżeli Państwo chcą dostarczyć konkretne klawisze, jedynym wyborem jest obiektem. Jeśli nie dbasz o klucze, to jest to tablica.

Jeśli spróbujesz ustawić dowolne (numeryczne) klucze w tablicy, naprawdę masz utratę wydajności , ponieważ behawioralnie tablica wypełni wszystkie indeksy pomiędzy:

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

_{(Zauważ, że tablica w rzeczywistości nie zawiera 99 undefinedwartości, ale będzie się zachowywać w ten sposób, ponieważ w pewnym momencie [powinieneś] iterować tablicę.)}

Literały obu opcji powinny bardzo jasno określać, w jaki sposób można ich używać:

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

W ES6 najbardziej wydajnym sposobem byłoby użycie mapy.

var myMap = new Map();

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

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

Możesz korzystać z funkcji ES6 już dziś, używając podkładki ( https://github.com/es-shims/es6-shim ).

Wydajność będzie się różnić w zależności od przeglądarki i scenariusza. Ale oto jeden przykład, gdzie Mapjest najbardziej wydajny: https://jsperf.com/es6-map-vs-object-properties/2

ODNIESIENIE https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Map

W NodeJS, jeśli znasz ID, pętla w tablicy jest bardzo powolna w porównaniu z 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');

A wyniki:

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

Nawet jeśli szukany identyfikator jest pierwszym w tablicy / obiekcie:

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

Próbowałem dosłownie przenieść to do następnego wymiaru.

Biorąc pod uwagę dwuwymiarową tablicę, w której osie x i y mają zawsze tę samą długość, czy szybciej:

a) wyszukaj komórkę, tworząc dwuwymiarową tablicę i wyszukując pierwszy indeks, po którym następuje drugi indeks, tj .:

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

lub

b) utwórz obiekt z ciągiem reprezentującym współrzędne x i y, a następnie wykonaj pojedyncze wyszukiwanie na tym obiekcie, tj .:

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

Wynik:
okazuje się, że wykonanie dwóch wyszukiwań indeksów numerycznych w tablicach jest znacznie szybsze niż jedno wyszukiwanie właściwości obiektu.

Wyniki tutaj:

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

To zależy od użytkowania. Jeśli sprawa dotyczy obiektów wyszukiwania jest bardzo szybsza.

Oto przykład Plunkera do testowania wydajności wyszukiwania tablic i obiektów.

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

Zobaczysz to; Wyszukując 5000 elementów w kolekcji tablic o długości 5000 , przejmij 3000milisekony

Jednak wyszukiwanie 5.000 elementów w obiekcie ma 5.000 właściwości, bierze tylko 2lub 3milisekony

Również tworzenie drzewa obiektów nie robi dużej różnicy

Miałem podobny problem, z którym mam do czynienia, gdy muszę przechowywać świece na żywo ze źródła zdarzeń ograniczonego do x elementów. Mógłbym przechowywać je w obiekcie, w którym znacznik czasu każdej świecy działałby jako klucz, a sama świeca byłaby wartością. Inną możliwością było to, że mógłbym przechowywać go w tablicy, w której każdy element był samą świecą. Jednym z problemów związanych ze świecami na żywo jest to, że wysyłają aktualizacje z tym samym znacznikiem czasu, w którym najnowsza aktualizacja zawiera najnowsze dane, dlatego albo aktualizujesz istniejący element, albo dodajesz nowy. Oto dobry punkt odniesienia, który próbuje połączyć wszystkie 3 możliwości. Tablice w poniższym rozwiązaniu są średnio co najmniej 4x szybsze. Zapraszam do gry

"use strict";

const EventEmitter = require("events");
let candleEmitter = new EventEmitter();

//Change this to set how fast the setInterval should run
const frequency = 1;

setInterval(() => {
    // Take the current timestamp and round it down to the nearest second
    let time = Math.floor(Date.now() / 1000) * 1000;
    let open = Math.random();
    let high = Math.random();
    let low = Math.random();
    let close = Math.random();
    let baseVolume = Math.random();
    let quoteVolume = Math.random();

    //Clear the console everytime before printing fresh values
    console.clear()

    candleEmitter.emit("candle", {
        symbol: "ABC:DEF",
        time: time,
        open: open,
        high: high,
        low: low,
        close: close,
        baseVolume: baseVolume,
        quoteVolume: quoteVolume
    });



}, frequency)

// Test 1 would involve storing the candle in an object
candleEmitter.on('candle', storeAsObject)

// Test 2 would involve storing the candle in an array
candleEmitter.on('candle', storeAsArray)

//Container for the object version of candles
let objectOhlc = {}

//Container for the array version of candles
let arrayOhlc = {}

//Store a max 30 candles and delete older ones
let limit = 30

function storeAsObject(candle) {

    //measure the start time in nanoseconds
    const hrtime1 = process.hrtime()
    const start = hrtime1[0] * 1e9 + hrtime1[1]

    const { symbol, time } = candle;

    // Create the object structure to store the current symbol
    if (typeof objectOhlc[symbol] === 'undefined') objectOhlc[symbol] = {}

    // The timestamp of the latest candle is used as key with the pair to store this symbol
    objectOhlc[symbol][time] = candle;

    // Remove entries if we exceed the limit
    const keys = Object.keys(objectOhlc[symbol]);
    if (keys.length > limit) {
        for (let i = 0; i < (keys.length - limit); i++) {
            delete objectOhlc[symbol][keys[i]];
        }
    }

    //measure the end time in nano seocnds
    const hrtime2 = process.hrtime()
    const end = hrtime2[0] * 1e9 + hrtime2[1]

    console.log("Storing as objects", end - start, Object.keys(objectOhlc[symbol]).length)
}

function storeAsArray(candle) {

    //measure the start time in nanoseconds
    const hrtime1 = process.hrtime()
    const start = hrtime1[0] * 1e9 + hrtime1[1]

    const { symbol, time } = candle;
    if (typeof arrayOhlc[symbol] === 'undefined') arrayOhlc[symbol] = []

    //Get the bunch of candles currently stored
    const candles = arrayOhlc[symbol];

    //Get the last candle if available
    const lastCandle = candles[candles.length - 1] || {};

    // Add a new entry for the newly arrived candle if it has a different timestamp from the latest one we storeds
    if (time !== lastCandle.time) {
        candles.push(candle);
    }

    //If our newly arrived candle has the same timestamp as the last stored candle, update the last stored candle
    else {
        candles[candles.length - 1] = candle
    }

    if (candles.length > limit) {
        candles.splice(0, candles.length - limit);
    }

    //measure the end time in nano seocnds
    const hrtime2 = process.hrtime()
    const end = hrtime2[0] * 1e9 + hrtime2[1]


    console.log("Storing as array", end - start, arrayOhlc[symbol].length)
}

Wniosek 10 jest tutaj granicą

Storing as objects 4183 nanoseconds 10
Storing as array 373 nanoseconds 10

Jeśli masz posortowaną tablicę, możesz przeprowadzić wyszukiwanie binarne i jest to znacznie szybsze niż wyszukiwanie obiektów, możesz zobaczyć moją odpowiedź tutaj:
Jak szybciej wyszukiwać w posortowanej tablicy przy użyciu JavaScript