В одной из предыдущих статей нашего сайта мы рассказывали о том, какие основные структуры данных бывают, какими особенностями они обладают. Был представлен общий список структур данных, куда вошли как сложные, так и более простые. Все это теория, которую следует знать. Но более интересен вопрос практического применения той либо иной структуры данных в контексте программирования на JavaScript, то есть при разработке программного обеспечения. Мы уже рассказывали про массивы. Предмет сегодняшнего разговора — объекты.
Объекты
Специалисты называют объекты второй по популярности структурой данных. На практике объекты применяются как для получения возможности быстрого манипулирования информацией, так и для повышения удобства ее хранения. Но прежде чем изучить практические примеры, давайте рассмотрим общие операции, к тому же, их не так уж и много.
Вот как может выглядеть обычный объект на языке программирования JavaScript:
У нас есть возможность получить практически любое свойство по его имени, так как имя представляет собой уникальный идентификатор. Такая операция будет мгновенной.
Таким же образом мы можем перезаписать свойства либо даже выполнить создание и запись нового.
Вдобавок к этому, можно запросить все ключи либо все значения объекта. Для этого есть специальные методы, которые возвращают массив значений.
Сложность таких методов — О(n), то есть нужно пройтись по всем значениям, создавая из них массив.
Так как любое свойство объекта является его уникальным идентификатором, по ID разработчик может мгновенно получать, удалять, записывать и обновлять информацию. В результате объекты нередко применяются во вспомогательном качестве при выполнении оптимизаций через маппинг. Маппинг предоставляет методы для всех вышеописанных манипуляций, имитируя Map. К примеру, мы можем:
- проверить, существует ли запись (has), а не сравнивать с undefined;
- получить по ключу (get), записать (set);
- использовать forEach непосредственно сразу к map, выполняя итерацию на месте и по связкам (ключ, значение);
- и так далее.
Как же это все будет выглядеть на практике? Давайте вспомним очень популярную на собеседованиях задачу — посчитать число уникальных символов в строке. Решение такой задачи будет тривиальным, плюс будет работать с любыми символами:
Результат вызова — карта по уникальным символам и их числу:
Таким образом мы сформировали карту, заполнив ее символами из строки, причем каждый символ является уникальным идентификатором. Этим способом мы могли, что называется, мгновенно проверить наличие символа в карте, получить значение, а потом перезаписать его. И все это работало бы для любого символа и любого языка, включая специальные символы и даже пробелы. То есть идея маппинга в том и заключается, чтобы создать вспомогательную структуру данных для определенных операций при алгоритмической сложности О(1).
Список структур данных
Напоследок давайте освежим в памяти основные структуры данных:
- Массивы. Наиболее популярный способ структуризации. У каждого элемента есть индекс, соответствующий положению этого элемента в массиве.
- Очереди. Вспоминаем очередь на кассу и принцип FIFO — First In, First Out.
- Стеки. Вспоминаем стопку книг или других предметов и принцип LIFO — Last In, First Out.
- Деревья. Иерархические структуры данных, состоящие из вершин и ребер.
- Связные списки. Цепочки узлов, каждый из которых содержит информацию и указатель на следующий узел в этой цепочке.
- Графы. Похожи на деревья, но более сложны. Не вдаваясь в подробности, скажем, что дерево является ограниченной формой графа.
- Боры. Префиксные деревья с древовидной структурой данных, показывающие высокую эффективность при решении задач на строки.
- Хэш-таблицы. Эта структура данных реализует интерфейс ассоциативного массива и хранит пары «ключ-значение».
Помните, что общие знания структур данных помогут не только на собеседовании, но и могут быть полезными при создании программного обеспечения, т. к. при правильном использовании структуризации вы сможете не только успешно выполнять сложные задачи, но и оптимизировать свой код.
Также на нашем сайте вам могут быть интересны следующие тематические статьи:
— «Понятие структуры данных для программиста. Массивы»;
— «Топ-8 структур данных для программиста»;
— «Дерево как структура данных. Двоичные деревья».
Предмет следующего разговора — сортировки и их применение в контексте программирования. Следите за обновлениями блога!
По материалам сайта: https://dou.ua/lenta/articles/what-you-should-know-about-algorithms/.