Javascript поиск ассоциативном массиве

Тонкости ES6: Коллекции (часть 2)

От переводчика: это вторая часть перевода статьи про коллекции в EcmaScript 6. Первую часть можно прочитать тут. По разным причинам перевод второй части затянулся на достаточно долгий срок.

Map

• new Map возвращает новый пустой ассоциативный массив.
• new Map(pairs) создает новый ассоциативный массив и наполняет его данными из существующей коллекции пар Javascript поиск ассоциативном массиве . Эта коллекция может быть другим Map объектом, массивом из двухэлементных массивов, генератором который возвращает двухэлементые массивы, и т.д.
• map.size возвращает количество элементов в ассоциативном массиве.
• map.has(key) проверяет, существует ли ключ key в ассоциативном массиве.
• map.get(key) возвращает значение ассоциируемое с ключом key, либо undefined, если такого ключа нет. (аналогично objJavascript поиск ассоциативном массиве )
• map.set(key, value) добавляет запись в массив, ассоциирующую key с value. Перезаписывает существующую ассоциацию, если таковая имеется (аналогично objJavascript поиск ассоциативном массиве )
• map.delete(key) удаляет запись (аналогично delete objJavascript поиск ассоциативном массиве )
• map.clear() удаляет все записи в ассоциативном массиве.
• map[Symbol.iterator]() возаращает итератор по записям в ассоциативном массиве. Итератор представляет каждую запись как массив Javascript поиск ассоциативном массиве .
• map.forEach(f) работает так:

for (let Javascript поиск ассоциативном массиве of map) f(value, key, map); 

На что тут жаловаться? Вот некоторые фичи, которых нет в ES6 коллекциях, и которые, я думаю, были бы полезны:

• Приспособление для значений по умолчанию, как collections.defaultdict в Python.
• Хэлпер-функция, Map.fromObject(obj) , чтобы облегчить написание ассоциативных массивов с использованием синтаксиса объект-литерал (object-literal syntax) (Прим. перев: пример синтаксиса объект-литерал в ES — < "test" : 1 >)

Опять же, эти фичи легко добавить.

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

Отличия JS, часть 1: хэш-таблицы без хэш-кодов?

Есть одна полезная фича, которую классы коллекций в ES6, насколько мне известно, не поддерживают вообще.

Допустим, у нас есть Set из URL-объектов.

var urls = new Set; urls.add(new URL(location.href)); // два URL-объекта urls.add(new URL(location.href)); // одинаковы ли они? alert(urls.size); // 2 

Эти два URL должны быть интерпретированы как идентичные. Все поля у них одинаковые. Но в Javascript это два разных объекта, и перегрузить понятие языка о равенстве объектов никак нельзя.

Другие языки это поддерживают. В Java, Python, Ruby отдельные классы могут перегружать равенство. Во многих имплементациях Scheme, индивидуальные хэш-таблицы могут быть созданы с использованием разных понятий равенства. С++ поддерживает оба варианта.

Однако все эти механизмы требуют от пользователей имплементации кастомных хэш-функций, и все они экспонируют системную хэш-функцию по умолчанию. Комитет решил не выставлять на показ хэш-коды в Javascript — во всяком случае пока — из-за открытых вопросов об интероперабельности и безопасности, что не является поводом для такого беспокойства в других языках.

Отличия JS, часть 2: Сюрприз! Предсказуемость!

Вы наверное думаете, что детерминированное поведение со стороны компьютера не повод для удивления. Но люди часто удивляются, когда я им говорю, что итерация по элементам в Map и Set происходит в порядке их добавления в коллекцию. Она детерминирована.

• Есть свидетельства, что некоторые программисты находят произвольный порядок итерации удивительным и поначалу непонятным. [1][2][3][4][5][6]
• Порядок энумерации свойств не специфицирован в ECMAScript, однако все крупные имплементации вынуждены сойтись на конкретном порядке вставки, для совместимости. Поэтому есть мнение, что если TC39 не станет специфицировать детерменированный порядок итерации, «веб сделает это за нас». [7]
• Порядок итерации хэш-таблицы может раскрыть части хэш-кодов объектов. Это возлагает огромную ответственность за безопасность на имплементатора хэш-функции. Например, адрес объекта не должен быть восстанавливаемым из раскрытых частей его хэш-кода (раскрытие адреса объекта недоверенному ECMAScript-коду хоть и не может эксплуатироваться злоумышленниками само по себе, но было бы большой дырой в безопасности).

Вот так мы оказались с хэш-таблицами, которые следят за порядком вставки в JS!

Весомые причины использовать слабые коллекции

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

if (element.isMoving) < smoothAnimations(element); >element.isMoving = true; 

К сожалению, задание expando-свойства в DOM-объекте таким образом — плохая идея, что и обсуждалась в статье. В той статье мы решили проблему, используя символы. Но не можем ли мы сделать то же самое используя Set ? Это может выглядеть так:

if (movingSet.has(element)) < smoothAnimations(element); >movingSet.add(element); 

Есть только один недостаток: Map и Set имеют сильную ссылку (strong reference) на каждый ключ и каждое значение. Это значит, если DOM-элемент был удален из документа, сборщик мусора не может освободить память пока элемент не удален из movingSet . Библиотеки обычно с грехом пополам справляются с очисткой памяти после себя. Это может привести к утечкам памяти.

ES6 предлагает удивительное решение для этого. Сделайте movingSet WeakSet вместо Set . Проблема утечки решена!

Итак, можно решить эту проблему с помощью слабых коллекций или символов. Что лучше? Дискуссия о преимуществах и недостатках каждого способа сделает этот пост слишком длинным. Если вы можете использовать один символ на протяжении всей жизни веб-страницы, то это, наверное, нормально. Если вы хотите использовать много короткоживущих символов, это тревожный знак: рассмотрите возможность использовать WeakSet вместо этого, чтобы предотвратить утечки памяти.

WeakMap и WeakSet

• WeakMap поддерживает только new, .has(), .get(), .set(), .delete() .
• WeakSet поддерживает только new, .has(), .add(), .delete() .
• Значения в WeakSet и ключи в WeakMap должны быть объектами.

Эти ограничения позволяют сборщику мусора собирать мертвые объекты из живых слабых коллекций. Похожего эффекта можно добиться с помощью слабых ссылок или словарей со слабыми ключами (weak-keyed dictionaries), но слабые коллекции в ES6 имеют все преимущества управления памятью без раскрытия факта, что в скриптах произошла сборка мусора.

Отличия JS, часть 3: скрывая недетерменированность сборщика мусора

Под капотом, слабые коллекции имплементированы как таблицы эфемеронов (ephemeron tables).

Вкратце, WeakSet не держит сильной ссылки на объекты внутри себя. Когда объект в WeakSet собирается сборщиком мусора, он просто удаляется из WeakSet . То же для WeakMap . У него нет сильных ссылок ни на один ключ. Если ключ жив, живо и значение.

Зачем все эти ограничение? Почему просто не добавить слабые ссылки в JS?

Опять же, комитет не хочет раскрывать недетерминированное поведение скриптам. Слабая кроссбраузерная совместимость — проклятие веб-разработки. Слабые ссылки раскрывают детали имплементации сборщика мусора — само определение платформо-специфичного произвольного поведения. Конечно, приложения не должны зависеть от деталей конкретной платформы, но слабые ссылки делают сложным для понимания, насколько вы зависите от поведения сборщика мусора в текущем браузере, в котором вы запускаете свое приложение. C ними сложно иметь дело.

Напротив, слабые коллекции в ES6 имеют более ограниченное, но крепкое множество фич. Факт сборки ключа или значения сборщиком мусора ненаблюдаем, так что приложения никак не могут зависеть от него, даже по случайности.

Это конкретный случай того, как специфичные для веба проблемы привели к удивительному решению в дизайне, которое улучшило JS как язык.

Где я могу использовать коллекции?

Все четыре класса коллекций поддерживаются в Firefox, Chrome, MS Edge и Safari. Для поддержки старых браузеров, используйте полифил (polyfill) типа es6-collections.

WeakMap был впервые имплементирован в Firefox Андреасом Галом, бывшим CTO Mozilla. Том Шустер имплементровал WeakSet . Я имплементировал Map и Set . Спасибо Тоору Фудзисаве (Tooru Fujisawa) за патчи.

На следующей неделе «Тонкости ES6» берут двухнедельный перерыв. Эта серия статей рассказала о многом, но некоторые самые мощные фичи ES6 еще будут описаны. Присоеденяйтесь к нам, когда мы вернемся с новым контентом 9 июля.

Источник

Эффективность поиска в массиве Javascript: ассоциативный или сохраненный?

Я читал, и они говорят, что ассоциативные массивы не дадут вам такой же эффективности, как массивы. Ассоциативный массив может искать вещи в O (N) времени, где массив может искать вещи в O (1). Вот мой вопрос: какой из них был бы более эффективным с точки зрения быстрого поиска значений и не слишком большого объема памяти? Ассоциативный:

var myVars=new Array(); myVars['test1'] = a; myVars['test2'] = b; myVars['test3'] = c; . (up to 200+ values) echo myVars['test2']; 

var myVars=new Array(); var TEST1 = 1; var TEST2 = 2; var TEST3 = 3; . (up to 200+ values) myVars[TEST1] = a; myVars[TEST2] = b; myVars[TEST3] = c; . (up to 200+ values) echo myVars[TEST2]; 

FWIW В Javascript нет такой вещи, как ассоциативный массив . просто объект с похожим процессом доступа.

@Felix Ваш тест не является реалистичным для его конкретного вопроса. Смотрите мой тест. Это опровергает ваше. Кроме того, ваше тестирование доступа к объектам и массивам недостаточно продуманно. Вы не сравниваете яблоки с яблоками.

4 ответа

Во-первых, первое использование Array неверно. Хотя это можно сделать, это не значит, что вам следует. Вы «злоупотребляете» тем фактом, что массивы тоже являются объектами. Это может привести к неожиданному поведению, например. хотя вы добавите 200 значений, myVars.length будет 0 .

Не используйте массив JavaScript как ассоциативный массив. Для этого используйте простые объекты:

var myVars = <>; myVars['test1'] = a; myVars['test2'] = b; myVars['test3'] = c; 

Во-вторых, в JavaScript нет реальной разницы между двумя (объектами и массивами). Массивы расширяют объекты и добавляют некоторое поведение, но они все еще являются объектами. Элементы сохраняются как свойства массива.

Дополнительную информацию можно найти в спецификации:

Объекты массива предоставляют особый подход к определенному классу имен свойств. Имя свойства P (в виде значения String) является индексом массива тогда и только тогда, когда ToString (ToUint32 (P)) равно P и ToUint32 (P) не равно 2 32 -1. (. )

имеют одинаковое время доступа † что определенно не O(n) .

†: Лучше сказать, должно быть. По-видимому, это варьируется в разных реализациях.

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

var myVars = []; myVars[0] = a; myVars[1] = b; myVars[2] = c; 

Более важно: вам нужно выбрать правильную структуру данных для своих нужд, и это определяется не только временем доступа к одному элементу, но также:

• Являются ли клавиши последовательными номерами или произвольными строками/цифрами?
• Вам нужно получить доступ ко всем элементам коллекции (т.е. через все)?

Числовые массивы (массивы) и ассоциативные массивы (или хэш-таблицы/карты (объекты в JS)) предоставляют различные решения для различных задач.

Вы уверены, что это неправильно? Я не программист JavaScript, но я понимаю, что Array JavaScript является типом Object и, следовательно, может использоваться как любой другой объект. Это сбивает с толку, но технически неверно.

@btilly: это неправильно, потому что это сбивает с толку. Я не имею в виду технически неправильно. Например, если вы назначите значения таким образом, arr.length все равно будет 0 . Уточню мой ответ .

@btilly До тех пор, пока вы не захотите перебрать свой хэш и в конечном итоге использовать все методы Array. Конечно, вы можете обойти это, но ненужную работу, когда есть более чистый и гораздо более распространенный контейнер.

Извините, мне следовало объяснить лучше. У меня есть более одного из этих устройств хранения данных, и наличие справочной таблицы для каждого из них было бы довольно раздражающим. В идеале я предпочел бы видеть myVars [‘test1’] в своем коде, чем myVars [23], особенно когда у меня есть несколько myVars для просмотра.

Я согласен с обновлением. Тем не менее, вот тест производительности: jsperf.com/javascript-associative-vs-non-associative-arrays

@howdoicodethis: тогда используйте объекты. Если есть разница, то она не должна быть такой огромной. Вы всегда можете запустить тесты позже и посмотреть, получите ли вы что-нибудь, перейдя из или в массив.

@FelixKling, я думаю, твой jsperf слишком ограничен. Массив в JavaScript — это хеш-таблица, запрос которой обходится несколько дороже, чем объекта, но почти все современные браузеры ускоряют время чтения. Нет существенной разницы в производительности между доступом к свойствам в массиве vs Object; однако операции редактирования / удаления / добавления имеют разные вычислительные затраты.

Источник