Эффективность использования массивов и объектов в JavaScript

У меня есть модель, содержащая, возможно, тысячи объектов. Я хотел бы узнать, какой способ хранения и извлечения одного объекта после получения его идентификатора будет наиболее эффективным. Идентификаторы представляют собой длинные числа.

В первом варианте это простой массив с увеличивающимся индексом. Во втором варианте это ассоциативный массив и, возможно, объект, если это имеет значение. Мой вопрос заключается в том, какой из вариантов более эффективен, если мне нужно получить в основном один объект, но также иногда перебирать их и сортировать.

Первый вариант с не ассоциативным массивом:

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

Второй вариант с ассоциативным массивом:

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

Обновление:

Хорошо, я понял, что об использовании массива во втором варианте не может быть и речи. Поэтому строка объявления во втором варианте действительно должна быть: var a = {}; и вопрос только в том, что лучше работает при получении объекта с заданным id: массив или объект, где id является ключом.

и еще, изменится ли ответ, если мне придется сортировать список много раз?

clemens
Редактировал вопрос 21-го ноября 2017 в 5:50
Программирование
javascript performance
25-го июня 2013 в 10:34
15 просмотров
Комментарии к вопросу (5)
Решение

Краткая версия: Массивы в основном быстрее объектов. Но 100% правильного решения не существует.

Обновление 2017 - Тест и результаты

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

Original Post - Explanation

В вашем вопросе есть несколько неверных формулировок.

В Javascript не существует ассоциативных массивов. Только массивы и объекты.

Это массивы:.

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

Это тоже массив:

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

По сути, это массив с дырками, потому что каждый массив имеет непрерывную индексацию. Это медленнее, чем массивы без дыр. Но итерация вручную по массиву еще медленнее (в основном).

Это объект:.

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

Вот тест производительности трех возможностей:

Lookup Array vs Holey Array vs Object Performance Test

Отличная статья на эту тему в Smashing Magazine: Writing fast memory efficient JavaScript

aleclarson
Редактировал ответ 16-го июля 2018 в 11:47
Комментарии (25)

Это не совсем вопрос производительности, поскольку массивы и объекты работают совершенно по-разному (или, по крайней мере, должны работать). Массивы имеют непрерывный индекс 0...n, в то время как объекты отображают произвольные ключи на произвольные значения. Если вы хотите предоставить конкретные ключи, то единственным выбором будет объект. Если же ключи вам не важны, то это массив.

Если попытаться задать массиву произвольные (числовые) ключи, то это действительно приведет к потере производительности, поскольку поведенчески массив будет заполнять все промежуточные индексы:

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

(Обратите внимание, что массив не фактически содержит 99 неопределенных значений, но он будет вести себя так, поскольку вы [предположительно] итерируете массив в какой-то момент.)

Литералы для обеих опций должны наглядно показать, как их можно использовать:

var arr = ['foo', 'bar', 'baz'];     // no keys, not even the option for it
var obj = { foo : 'bar', baz : 42 }; // associative by its very nature
deceze
Редактировал ответ 21-го декабря 2015 в 11:33
Комментарии (5)

С ЕС6 наиболее производительный способ заключается в использовании карта.

var myMap = new Map();

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

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

Вы можете использовать сегодня возможности ES6 с помощью ШИМ (https://github.com/es-shims/es6-shim).

Производительность может изменяться в зависимости от браузера и сценарий. Но вот один из примеров, где "карта" является самым производительным: https://jsperf.com/es6-map-vs-object-properties/2

Ссылка https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Map

sandstrom
Редактировал ответ 31-го мая 2017 в 8:29
Комментарии (5)

В NodeJS если вы знаете идентификатор, цикл через массив идет очень медленно по сравнению с объекта[идентификатор].


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

//create data
for(var i=0;i
Комментарии (1)

Я попытался перейти в следующее измерение, в буквальном смысле этого слова.

Если задан двумерный массив, в котором оси x и y всегда имеют одинаковую длину, то быстрее ли будет:

a) найти ячейку, создав двумерный массив и найдя первый индекс, а затем второй индекс, т.е:

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

или

б) создать объект со строковым представлением координат x и y, а затем выполнить единственный поиск по этому obj, т.е:

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

Результат: Оказалось, что гораздо быстрее выполнить два поиска числовых индексов в массивах, чем один поиск свойств в объекте.

Результаты здесь:

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

AVI
Редактировал ответ 21-го апреля 2016 в 11:38
Комментарии (0)

Это зависит от использования. Если дело объекты поиска-это очень быстрее.

Вот пример Plunker для тестирования производительности массива и объекта поиска.

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

Вы увидите, что; Глядя на 5.000 элементы 5.000 длина массива коллекции, захватить 3000 milisecons

Однако, глядя на 5.000 элементы в объект 5.000 свойства, берут только 2 или 3 milisecons

Также делает объект "Дерево" Дон'т сделать огромную разницу

Комментарии (0)

У меня была похожая проблема, что я столкнулся, когда мне нужно сохранить видео подсвечники из источника событий ограничивается х предметов. Я мог бы их положить в объект, где время каждая свеча будет действовать в качестве ключа, а сама свеча будет действовать в качестве значения. Другая возможность заключается в том, что я могу хранить его в массив, где каждый элемент был сам свечи. Одна проблема о прямых свечей заключается в том, что они продолжают присылать обновления на ту же отметку времени, где последнее обновление содержит самые последние данные, поэтому вы либо обновить существующий элемент или добавить новый. Так вот это хороший ориентир, который пытается объединить все 3 возможности. Массивы в растворе ниже приведены хотяб 4 раза быстрее в среднем. Не стесняйтесь играть

"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)
}

Заключение 10 это предел здесь

Storing as objects 4183 nanoseconds 10
Storing as array 373 nanoseconds 10
Комментарии (0)

Если у вас есть отсортированный массив, то вы можете сделать бинарный поиск, и это намного быстрее, чем поиск объекта, вы можете посмотреть мой ответ здесь: https://stackoverflow.com/questions/57422718/how-to-search-faster-in-a-sorted-array-using-javascript

Комментарии (0)