Структуры данных в JavaScript: множество, словарь или массив

Короткий ответ. Структуру выбирай по вопросу, который задаёшь чаще всего. «Видел ли я это раньше?» Множество. «Какое значение у этого ключа?» Словарь. «Какое сейчас минимальное?» Куча. «Что на позиции i, и важен ли порядок?» Массив. Множество и словарь отвечают за один шаг, неотсортированный массив проходит все элементы.

Четыре вопроса

«Видел ли я это раньше?» Множество. Проверка за один шаг при любом размере.

«Какое значение у этого ключа?» Ассоциативный массив. Та же скорость, и он несёт с собой данные.

«Какое сейчас минимальное?» Куча. Вставка и снятие минимума за log n.

«Что лежит на позиции i, и важен ли порядок?» Массив.

Почти каждая задача первой половины программы это один из четырёх в костюме.

Первые два живут в паттерне хеш-множество и словарь.

Цена одной и той же операции

Найти один элемент:

• Неотсортированный массив: шаг на каждый элемент.
• Отсортированный массив: log n бинарным поиском.
• Множество или словарь: один шаг в среднем.
• Куча: один шаг для минимума. Для остального полный проход.

Первая строка и превращает решения в квадратичные.

Проверка вхождения внутри цикла это два вложенных прохода. На экране выглядит как один.

Когда массив всё ещё выигрывает

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

Примерно до 100 элементов проход по массиву часто быстрее.

Современные кеши процессора построены под непрерывную память.

Ещё два случая.

Массив, индексированный маленькими целыми числами, обходит словарь по всем статьям.

Какой вариант разрешён, решают ограничения входа.

Порядок, сортировка или «элемент перед этим» требуют массива или дерева. Хеширование уничтожает порядок по своей природе.

Три ошибки, которые стоит назвать

Словарь там, где хватило бы множества. Все значения true? Нужно было множество.

Множество меньше и говорит то, что ты имел в виду.

Ключи обычного объекта в JavaScript. Объект превращает любой ключ в строку.

Поэтому 1 и "1" попадают в одну ячейку. А объект в роли ключа становится «[object Object]».

Ключи, которые не строки, требуют Map.

Удалить не то. Счётчик упал до нуля, а ключ остался на месте.

Нули ломают проверку «есть ли такой ключ» молча.

Дошёл до нуля, удаляй ключ.

Как решить за десять секунд

До первой строки кода закончи предложение: «операция, которую я сделаю тысячи раз, это _____».

Потом возьми структуру, которая делает эту операцию за один шаг.

Скажи это вслух на собеседовании. Выбор структуры с названной причиной и есть то, что проверяют.

Где это в треке

AlgoPath тратит шаги с 11 по 13 на один этот выбор. С кодом, который пишешь ты, до первого именованного паттерна.

Ценовая сторона выбора в статье Big O без математики.

Первые 33 шага бесплатные.