Производительность массива включает сопоставление с объектом и доступ к нему в JavaScript

Question

В соответствии с основами CS функциональность search несортированного списка должна происходить за O (n) время, когда прямой доступ к массиву будет происходить за O (1) время для HashMaps.

Так более ли целесообразно отображать массив в словарь и затем напрямую обращаться к элементу, или я должен просто использовать include?Этот вопрос специально для JavaScript, потому что я полагаю, что это сводится к основным деталям реализации того, как реализованы includes() и {}.

let y = [1,2,3,4,5]
y.includes(3)

или ...

let y = {
          1: true,
          2: true
          3: true
          4: true
          5: true
        }
5 in y

Answer 1

Хорошо.Несмотря на очевидное ожидание, что адрес объекта и набор должны превосходить массивы, включенные в тестирование, Chrome показывает, что реализация превосходит ожидания.

На стендах, в которых я участвовал в Chrome Array, был самый лучший исполнитель.

Я также тестировал локально с Node и получил больше ожидаемых результатов.В том случае, когда адрес объекта побеждает, а за ним внимательно следит Set, то включение массива было несколько медленнее, чем оба.

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

Вот результаты, которые я получил:

Узел (12.6.0):

ops for Object address 7804199
ops for Array includes 5200197
ops for Set has        7178483

Chrome(75,0):
https://jsbench.me/myjyq4ixs1/1

Answer 2

Это правда, что поиск объекта происходит за линейное время, поэтому использование свойств объекта вместо массива является одним из вариантов, но если вы просто пытаетесь проверить, включено ли значение в коллекцию, было бы более целесообразно использоватьSet, который является (обычно неупорядоченным) набором значений, который также можно искать в линейном времени.(Использование простого объекта вместо этого потребовало бы, чтобы у вас были значения в дополнение к вашим ключам, которые вам не нужны, поэтому используйте вместо них Set.)

const set = new Set(['foo', 'bar']);
console.log(set.has('foo'));
console.log(set.has('baz'));

Это будет полезно, когда вам придется искать несколько значений для того же самого Set.Но добавление элементов к Set (точно так же, как добавление свойств к объекту) - это O(N), поэтому, если вы просто собираетесь искать одно значение, один раз , это не принесет никакой пользыни объектная техника, и вы также можете просто использовать массив includes test.