Что быстрее массив или объект?

Question

[WebDev]

Пишу чат на nodejs. Храню данные в виде объекта.

const companies = {
    2: {
        id: 2,
        company_name: 'My company',
        users: {
            1: {
                id: 1,
                name: 'John',
                messages: [...]
            }
        }
    }
}

Примерно так. Храню я данные в объекте, а не в массиве по двум причинам:
1) Так удобнее обращаться. Например, я могу прямо в разметке (я использую Vue) вывести имя пользователя.

<span>{{ companies[company_id].users[user_id].name }}</span>

2) Так быстрее, потому что мы сразу обращаемся к конкретному свойству.

Затем я решил посмотреть на разницу. Написал небольшой скрипт, который запустил в браузере.
Суть скрипта в том, что он миллион раз ищет данные в массиве и в объекте. Упрощенно он выглядит так:

const objResult = obj[key];
//VS
const arrResult = arr.find(el => el.id === key);

К моему ужасу поиск по массиву на порядки быстрее.
Наверное браузер что-нибудь кэширует и вообще в браузере такие замеры проводить неправильно. Тогда я пошел в интернет и в первом же вопросе на stackoverflow пишут "Arrays are mostly faster than objects".
Я еще смотрел в разных источниках, мнения разнятся.

Объясните, пожалуйста, почему такой вопрос вообще обсуждается и имеет место быть? Ведь обращение к объекту по ключу - это вообще не поиск. Скрипт сразу знает и сразу получает данные. В массиве напротив - это всегда перебор всего массива каждый раз.

Comments

[Lynn «Кофеман»]

Какое-то странное сравнение тёплого с мягким.
А самое главное, никакого смысла в этом нет, пока у вас не миллионы ключей и вы не выбираете разные ключи миллионы раз в секунду, узким местом у вас будет что угодно другое (например реакт), но не получение значения по ключу.

[Stranger in the Q]

Преждевременная оптимизация это пустая трата времени, для проекта в целом

[WebDev]

Алексей Тен, Почему теплое с мягким? Вполне обычный вопрос. Я могу отдавать с сервера массив, а могу объект. Если какой-то из этих вариантов предпочтительнее в плане производительности, выберу его. Вот вы как отдаете данные с сервера массивом или объектом?

[ayazer]

WebDev, массивом объектов ;)

[dom1n1k]

Именно что теплое с мягким.
Обращаться к элементу массива нужно по индексу, вот тогда он будет быстрее. А поиск с полным перебором, да еще и в функциональном стиле, конечно же будет на порядки медленнее хеш-таблицы (если бенчмарк показал, что быстрее - это проблема бенчмарка).
Но в реальной жизни использовать массив для чата, наверное, будет не лучшей идеей, потому что есть проблемка с разреженностью массива. Она решаема, но с ней массив скорее всего потеряет и удобство, и преимущество в скорости и вообще непонятно в чем понт.
Самое правильное решение - использовать Map.

Answer 1

[Иван Титов]

Мне это напомнило историю, когда некий докладчик сравнил поиск в Яндексе и прямое указание сайта в адресной строке. Типа, когда он пишет адрес сайта, то сразу переходит на него, и якобы поиск не включается. Однако даже при прямом указании адреса сайта всё равно включается поиск: вы ввели адрес сайта, но это не точный путь к серверу, где хранятся данные. Пока идёт запрос к данным, и пока они идут обратно, включаются несколько поисков на разных этапах.

Так же и здесь. По сути системе нужно достать некое значение из памяти. Массивы изначально заточены под машинную организацию памяти: по порядку. Логично предположить, что если вам нужно N-e значение, то оно быстрее достанется из памяти, так как оно N-e в самой памяти, начиная от некой ячейки (грубо говоря). Более сложные ассоциативные массивы (или объекты) организованы в памяти более сложно (извиняюсь за тавтологию). Ассоциативный массив - это, как минимум, два обычных массива. Соответственно, выполняя поиск по нему, работают уже минимум два поиска.

это всегда перебор всего массива каждый раз.

Если ключи уникальны, а в обычных javascript массивах это так, то вряд ли поиск продолжается после нахождения нужного элемента.

В целом веб-приложения это не совсем та сфера, где надо оптимизировать запросы, на базе архитектуры, я имею в виду, когда получаешь выигрыш в пару миллисекунд. Страница грузится пару секунд, анимации длятся 0.3с и так далее - на этом фоне выигрыш будет нулевой, даже с 1 миллиардом пользователей онлайн )

По существу вопроса, мне кажется, вы всё делаете совершенно правильно, потому что в вебе самое главное - это удобство постоянного развития проекта. Если код внешне, и по логике похож на то, как данные организованы в бытовом восприятии, это удобно: быстро вникаешь и можно дорабатывать.

Answer 2

[Антон В.]

Добрый день

Написал два скрипта с замером времени поиска.

Search by object

let obj = {}

for(let i =0; i<1000; i++){
    obj['i'+i]=i
}

console.time('time')
for(let i =0; i<1000; i++){
const objResult = obj['i'+i];
}
console.timeEnd('time')

time: 0.156982421875ms

Search by array

let obj = []

for(let i =0; i<1000; i++){
    obj.push('i'+i)
}

console.time('time')

for(let i =0; i<1000; i++){
    const arrResult = obj.find(el => el === 'i'+i);
}
console.timeEnd('time')

time: 32.946044921875ms

Время конечно может отличатся, но в целом видится что поиск по массиву работаем медленнее обращения по ключу, по крайне мере в промышленном масштабе.

Comments

[Антон В.]

JS Benchmarks

Answer 3

[Saboteur]

Почему вы считаете, что обращение по ключу - не поиск?

Ключ это прямой адрес в памяти?
Нет, а значит наверное надо выполнить поиск по всем объектам, чтобы найти нужный по ключу?
Нужно смотреть реализацию геттера, чтобы понять насколько там все сложно.

Comments

[Валентин]

А что, в is объект - не hashtable?