Масив проти ефективності об'єкта в JavaScript

У мене є модель з можливими тисячами об'єктів. Мені було цікаво, що буде найефективнішим способом їх зберігання та вилучення одного об'єкта, як тільки у нього є ідентифікатор. Ідентифікація - це довгі числа.

Отже, це два варіанти, про які я думав. у варіанті 1 це простий масив із зростаючим індексом. у варіанті 2 це асоціативний масив і, можливо, об'єкт, якщо він має значення. Моє запитання, який з них більш ефективний, коли мені в основному потрібно одержувати один об'єкт, але іноді цикл через них і сортування.

Варіант 1 з неасоціативним масивом:

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 це ключ.

а також, чи зміниться відповідь, якщо мені доведеться багато разів сортувати список?

93
@ Джон насправді, я роблю що ви маєте на увазі під "як ви робите зараз"?
додано Автор Moshe Shaham, джерело
Я думаю, цей еталон відповість на першу частину вашого запитання: jsben.ch/#/Y9jDP
додано Автор EscapeNetscape, джерело
Вам завжди потрібна сортована колекція? Якщо так, то інший варіант, крім масиву, не існує (хоча ви не використовуєте індекси, як ви робите зараз).
додано Автор Jon, джерело
@MosheShaham: масиви (повинні) мають постійні індекси, починаючи з 0. Якщо ви використовуєте масиви, не робіть нічого іншого.
додано Автор Jon, джерело
додано Автор Sudhir Bastakoti, джерело

6 Відповіді

Коротка версія: масиви в основному перевершують об'єкти. Але немає 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'});
}

test setup test results

Оригінальне пост - пояснення

У вашому питанні є деякі неправильні уявлення.

У 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";

Ось тест продуктивності трьох можливостей:

Масив з пошуку в порівнянні з темою Holey Array проти тесту на об'єкт

An excellent read about these topics at Smashing Magazine: Writing fast memory efficient JavaScript

110
додано
@Моше Це дуже залежить від браузера. Перегляньте порівняння браузера в кінці сторінки.
додано Автор deceze, джерело
@Moshe І тим самим, все обговорення продуктивності в Javascript має бути зроблено. : П.
додано Автор deceze, джерело
у вашому тесті він розповідає мені, що Holey Array - це найшвидший (120K проти 92K для об'єкта). Чи має це сенс?
додано Автор Moshe Shaham, джерело
насправді, в Firefox ручний масив пошуку є найшвидшим ...
додано Автор Moshe Shaham, джерело
@ Аліп ОК, я чую тебе. Я думав, що запитаю перед кодом, тому що, якщо я виберу масив, це буде серйозним болем, щоб змінити його ...
додано Автор Moshe Shaham, джерело
Ця відповідь може бути покращена шляхом узагальнення висновків jsPerf тут у цьому положенні - особливо тому, що результати jsPerf є справжньою відповіддю на запитання. Решта додаткова. Це більш актуально в тих випадках, коли jsPerf вимикається (як зараз). meta.stackexchange.com/questions/8231/…
додано Автор Jeff, джерело
Є масиви? var a = [1,2,3], b = {'1': 1, '2': 2}; typeof a == 'об'єкт' typeof b == 'об'єкт'?
додано Автор Guntram, джерело
Коли я використовую find() в масиві, я отримую ту саму продуктивність, що й у Holey Array або Object (принаймні з Chrome) jsben.ch/#/05cmA
додано Автор Supersharp, джерело
Ті пошукові масиви, про які я говорив, це ручний підхід до пошуку правильного індексу. Крім того, дякую за ваш коментар, ви маєте рацію про ці моменти!
додано Автор Alp, джерело
Ви маєте рацію @ Гунтрам, внутрішні обидва мають однаковий тип. Але синтаксично вони мають різні прототипи та функціональні можливості. Тому різниця в продуктивності.
додано Автор Alp, джерело
додано оновлення з скріншотами для налаштування тесту та результатів
додано Автор Alp, джерело
Якщо між результатами немає величезної різниці, просто дотримуйтесь самого ремонтопридатного та eleganz рішення. Якщо ви відчуваєте значні відмінності продуктивності, дотримуйтесь найшвидшого способу пошуку. Це стосується майже кожного аспекту вашого сценарію.
додано Автор Alp, джерело
Див http://jsperf.com/array-vs-object-performance/71. Має меншу підмножину даних (я мав би петлі для створення даних, але я хотів дірки в масиві) приблизно з 93 об'єктами у порівнянні з 5000. Зовнішня петля - це Ідентифікатори для пошуку розсіяних в масиві об'єктів (починаючи з середнього та кінця) і Я також додав відсутній ідентифікатор, тому масив повинен мати перехід по всіх елементах. Holey Array, Object by Key, потім Manual Array. Так як f1v стверджував, що це насправді залежить від розміру даних і де дані для ручного пошуку масивів.
додано Автор Charles Byrne, джерело
Погодьтеся з f1v, проте в редакції 35 є помилка в тесті: if (a1 [i] .id = id) result = a1 [i]; Має бути: if (a1 [i ] .id === id) result = a1 [i]; Перевірте http://jsperf.com/array-vs-object-performance/37 виправляє це
додано Автор Charles Byrne, джерело
Спочатку ви кажете, що не існує таких речей, як асоціативні масиви, і тоді ви кажете, що у нього є "масивів пошуку", які, на мою думку, фактично однакові. Будь ласка, повторно прочитайте Написання швидкого, ефективного використання пам'яті JavaScript Адді Османі . Сама стаття, яку ви зв'язали, суперечить цій першій важкій точці. Об'єкт має дві загальні цілі: 1. Екземпляр hidden class і 2. «словник», «асоціативний масив» або як ви його називаєте.
додано Автор Domi, джерело
Тест є недоліком. Масовий підхід насправді не так повільний. Спочатку при створенні елементів o та a2 одержати новий елемент , лише якщо вони ще не мають його , а новий - в a1 завжди . Якщо воно генерує однакове число двічі, воно не буде додано до o і a2 , але буде вставлено в a1 . Навряд чи, але все-таки ... По-друге , в тестуванні a1 будь-яка нормальна людина розбила цикл, коли знайдуть елемент ... це значно змінює результати. Перевірте себе .
додано Автор Hristiyan Dodov, джерело
jsperf.com/array-vs-object-performance/182 показує, як Очікується, що продуктивність лінійного пошуку незмірно мала порівняно з індексованим/ключем-пошуком на наборах даних, де в будь-якому разі важливість продуктивності (тобто не тестовий розмір з 2-х записів). У цьому випадку різниця між Holey Array і Object by Key виглядає незначною. Мені цікаво лише розмір пам'яті, тому що кожен об'єкт, імовірно, містить властивість рядка, яка не може бути gc'able.
додано Автор aaron, джерело
Це дійсно залежить від даних та розміру даних, з якими ви працюєте. Дуже малі набори даних і маленькі об'єкти будуть працювати набагато краще з масивами. Якщо ви говорите про пошук у великому наборі даних, де ви використовуєте об'єкт як карту, то об'єкт є більш ефективним. jsperf.com/array-vs-object-performance/35
додано Автор f1v, джерело
Зміни результатів залежать від браузера. Помилка поля між асоціативним масивом та об'єктом занадто мала в chrome 61.0.3163.100. У Firefox 56.0 масив близький до швидкості асоційованого масиву, і об'єкт явно найшвидший. На грані об'єкт явно найшвидший. Я виявив, що метод array.find незрівнянно повільний у Firefox, але відповідає продуктивності масиву в інших браузерах.
додано Автор SILENT, джерело
Це невелике покращення, додавши find() до масиву jsben.ch/Bjbf9 Зазначте, чи шуканий елемент є першим тим самим, що і об'єкт, якщо ні, до тих пір, поки це далеко.
додано Автор pikilon, джерело

Це взагалі не є питанням продуктивності, оскільки масиви та об'єкти працюють зовсім по-іншому (або принаймні). Масиви мають безперервний індекс 0..n , а об'єкти показують довільні ключі до довільних значень. Якщо ви хочете надати певні ключі, єдиним вибором є об'єкт. Якщо ви не дбаєте про ключі, це масив.

Якщо ви намагаєтесь встановити довільні (числові) клавіші на масиві, ви дійсно маєте втрату , оскільки поведінкова маса заповнить всі індекси між собою:

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

(Зверніть увагу, що масив насправді не містить 99 значень undefined , але він буде поводитися таким чином, оскільки ви [повинні бути] повторювати масив у певний момент.)

Літерали для обох варіантів повинні чітко визначити, як вони можуть бути використані:

var arr = ['foo', 'bar', 'baz'];    //no keys, not even the option for it
var obj = { foo : 'bar', baz : 42 };//associative by its very nature
18
додано
@Moshe У Javascript не існує такої речі, як неасоціативний масив. Якщо вам потрібні ключі (цифри або рядки), використовуйте об'єкт. Якщо вам просто потрібний (упорядкований) список, використовуйте масиви. Період. Продуктивність не входить до обговорення. Якщо продуктивність має вирішальне значення, і ви можете жити за допомогою клавіш в будь-якому випадку, спробуйте, який з них працює для вас краще.
додано Автор deceze, джерело
@Moshe Якщо ви отримуєте доступ до щось за допомогою клавіші, в об'єкті чи масиві, це завжди буде нескінченно швидше, ніж цикл через контейнер, намагаючись знайти те, що ви хочете. Різниця доступу до елемента за допомогою клавіші в масиві або в об'єкті, ймовірно, незначна. Цикл, очевидно, гірший у будь-якому випадку.
додано Автор deceze, джерело
Я не хочу надавати певні ключі. Я хочу знати, що працює краще, і я буду працювати з цим. Гаразд, так що у другому варіанті масив не підходить. але як щодо об'єкта проти неасоціативного масиву?
додано Автор Moshe Shaham, джерело
Але я хочу знати, що працює краще: витягувати об'єкт з масиву (шляхом циклу через нього) або з "асоціативного" об'єкта, де ідентифікатор є ключовим. Мені шкода, якщо моє запитання було незрозуміло ...
додано Автор Moshe Shaham, джерело
@deceze - як "щодо масивів, що тримають об'єкти користувача, і для отримання об'єкта користувача, потрібен цикл, щоб отримати користувацький об'єкт на основі об'єкта user_id " проти ", що має ключі як user_id , отже користувацький об'єкт може бути доступний за допомогою user_id як ключ "? Який з них краще з точки зору продуктивності? Будь-які пропозиції щодо цього оцінені :)
додано Автор Rayon, джерело

З ES6 найбільш ефективним способом було б використовувати Карту.

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 ).

Performance will vary depending on the browser and scenario. But here is one example where Map is most performant: https://jsperf.com/es6-map-vs-object-properties/2


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

10
додано
@ AlexG впевнений, що заголовок чітко визначає efficiency .
додано Автор Qix, джерело
Це більше "семантичний", не більш продуктивний, що було питанням.
додано Автор AlexG, джерело
@Qix Так, мій поганий: о
додано Автор AlexG, джерело
Ви отримали будь-який ресурс, щоб підтримати це? З моїх спостережень на сьогодні ES6 набори є швидшими, ніж масиви, але ES6 Maps повільніше, ніж обидва об'єкти та масиви
додано Автор Steel Brain, джерело

Я намагався це зробити до наступного виміру, буквально.

З огляду на 2-мірний масив, в якому осі x і y завжди однакова довжина, чим вона швидше:

а) шукати комірку, створивши двомірний масив і шукаючи перший індекс, а потім другий індекс, тобто:

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

або

b) create an object with a string representation of the x and y coабоdinates, and then do a single lookup on that obj, i.e:

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

Результат:
Виявляється, що набагато швидше виконувати два числове пошуку індексу на масивах, ніж один пошук властивостей об'єкта.

Результати тут:

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

2
додано

У NodeJS , якщо ви знаєте код ID , цикл через масив дуже повільний порівняно з 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

І результати:

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

Навіть якщо ідентифікатор шукає перший в масиві/об'єкті:

Array result:
arrTimer: 2.975ms
Object result:
objTimer: 0.068ms
1
додано

Це залежить від використання. Якщо справа є пошуковими об'єктами, то це швидше.

Ось приклад Plunker для перевірки продуктивності масивів і пошуку об'єктів.

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

Ви побачите це; Знаходьте елементи 5,000 у колекції масивів довжини 5,000 , візьміть 3000 мілісекунди

Однак, якщо в об'єкті 5.000 шукати об'єкти має властивості 5.000 , візьміть лише 2 або 3 мілісекунди

Також дерево об'єктів не має величезної різниці

1
додано
ІТ КПІ - JavaScript
ІТ КПІ - JavaScript
504 учасників

співтовариство javascript розробників в Telegram