Tableau vs. Objet efficacité en JavaScript

Question

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

Alors voici les 2 options auxquelles je pensais. dans la première option, c'est un simple tableau avec un index croissant. dans la deuxième option, c'est un tableau associatif et peut-être un objet, si ça fait une différence. Ma question est laquelle est la plus efficace, lorsque j'ai principalement besoin de récupérer un seul objet, mais parfois aussi de les parcourir et de les trier.

Option une avec 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 = [];  // peut-être que {} fait une différence ?
a[29938] = {id: 29938, name: 'name1'};
a[32994] = {id: 32994, name: 'name1'};
function getObject(id) {
    return a[id];
}

Mise à jour :

D'accord, je comprends qu'utiliser un tableau dans la deuxième option est hors de question. Donc la ligne de déclaration dans la deuxième option devrait vraiment être : var a = {}; et la seule question est : quel est le plus performant pour récupérer un objet avec un identifiant donné : un tableau ou un objet où l'identifiant est la clé.

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

Answer 1

Cela dépend de l'utilisation. Si le cas est la recherche d'objets, c'est beaucoup plus rapide.

Voici un exemple Plunker pour tester les performances de la recherche dans un tableau et dans un objet.

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

Vous verrez que ; Rechercher 5 000 éléments dans une collection de tableau de longueur 5 000 prend plus de 3000 millisecondes

Cependant, rechercher 5 000 éléments dans un objet ayant 5 000 propriétés prend seulement 2 ou 3 millisecondes

De plus, la création d'un arbre d'objets ne fait pas une énorme différence

Answer 2

J'avais un problème similaire que je rencontre où je dois stocker des chandeliers en direct à partir d'une source d'événements limitée à x éléments. Je pourrais les stocker dans un objet où l'horodatage de chaque chandelier agirait comme clé et le chandelier lui-même agirait comme valeur. Une autre possibilité était de le stocker dans un tableau où chaque élément était le chandelier lui-même. Un problème avec les chandeliers en direct est qu'ils continuent d'envoyer des mises à jour sur le même horodatage où la dernière mise à jour contient les données les plus récentes, vous devez donc soit mettre à jour un élément existant, soit en ajouter un nouveau. Voici donc un bon benchmark qui tente de combiner les 3 possibilités. Les tableaux dans la solution ci-dessous sont au moins 4 fois plus rapides en moyenne. N'hésitez pas à jouer

"use strict";

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

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

setInterval(() => {
    // Prenez l'horodatage actuel et arrondissez-le à la seconde la plus proche
    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();

    // Effacer la console avant d'imprimer de nouvelles valeurs
    console.clear()

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

}, frequency)

// Le test 1 impliquerait de stocker le chandelier dans un objet
candleEmitter.on('candle', storeAsObject)

// Le test 2 impliquerait de stocker le chandelier dans un tableau
candleEmitter.on('candle', storeAsArray)

// Conteneur pour la version objet des chandeliers
let objectOhlc = {}

// Conteneur pour la version tableau des chandeliers
let arrayOhlc = {}

// Stocker un maximum de 30 chandeliers et supprimer les plus anciens
let limit = 30

function storeAsObject(candle) {

    // Mesurer le temps de démarrage en nanosecondes
    const hrtime1 = process.hrtime()
    const start = hrtime1[0] * 1e9 + hrtime1[1]

    const { symbol, time } = candle;

    // Créez la structure d'objet pour stocker le symbole actuel
    if (typeof objectOhlc[symbol] === 'undefined') objectOhlc[symbol] = {}

    // L'horodatage du dernier chandelier est utilisé comme clé avec la paire pour stocker ce symbole
    objectOhlc[symbol][time] = candle;

    // Supprimer les entrées si nous dépassons la limite
    const keys = Object.keys(objectOhlc[symbol]);
    if (keys.length > limit) {
        for (let i = 0; i < (keys.length - limit); i++) {
            delete objectOhlc[symbol][keys[i]];
        }
    }

    // Mesurer le temps de fin en nanosecondes
    const hrtime2 = process.hrtime()
    const end = hrtime2[0] * 1e9 + hrtime2[1]

    console.log("Stockage sous forme d'objets", end - start, Object.keys(objectOhlc[symbol]).length)
}

function storeAsArray(candle) {

    // Mesurer le temps de démarrage en nanosecondes
    const hrtime1 = process.hrtime()
    const start = hrtime1[0] * 1e9 + hrtime1[1]

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

    // Obtenez le tas de chandeliers actuellement stockés
    const candles = arrayOhlc[symbol];

    // Obtenez le dernier chandelier s'il est disponible
    const lastCandle = candles[candles.length - 1] || {};

    // Ajoutez une nouvelle entrée pour le chandelier nouvellement arrivé s'il a un horodatage différent du dernier que nous avons stocké
    if (time !== lastCandle.time) {
        candles.push(candle);
    }

    // Si notre nouveau chandelier a le même horodatage que le dernier chandelier stocké, mettez à jour le dernier chandelier stocké
    else {
        candles[candles.length - 1] = candle
    }

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

    // Mesurer le temps de fin en nanosecondes
    const hrtime2 = process.hrtime()
    const end = hrtime2[0] * 1e9 + hrtime2[1]

    console.log("Stockage sous forme de tableau", end - start, arrayOhlc[symbol].length)
}

Conclusion 10 est la limite ici

Stockage sous forme d'objets 4183 nanosecondes 10
Stockage sous forme de tableau 373 nanosecondes 10

Answer 3

1. Les champs indexés (champs avec des clés numériques) sont stockés comme un tableau intérieur à l'objet. Par conséquent, le temps de recherche est O(1)

2. De même pour un tableau de recherche, c'est O(1)

3. Parcourir un tableau d'objets et tester leurs identifiants par rapport à celui fourni est une opération O(n).