Что такое структура данных в программировании

Содержание
  1. Основные структуры данных. Матчасть. Азы
  2. Что такое структура данных?
  3. Какие бывают?
  4. Основные структуры данных.
  5. Массивы
  6. Бывают
  7. Основные операции
  8. Вопросы
  9. Стеки
  10. Основные операции
  11. Вопросы
  12. Очереди
  13. Основные операции
  14. Вопросы
  15. Связанный список
  16. Бывают
  17. Основные операции
  18. Вопросы
  19. Графы
  20. Бывают
  21. Встречаются в таких формах как
  22. Общие алгоритмы обхода графа
  23. Вопросы
  24. Деревья
  25. Три способа обхода дерева
  26. Вопросы
  27. Trie ( префиксное деревое )
  28. Вопросы
  29. Хэш таблицы
  30. Вопросы
  31. Список ресурсов
  32. Вместо заключения
  33. Важнейшие структуры данных, которые вам следует знать к своему собеседованию по программированию
  34. Что такое структура данных?
  35. Зачем нужны структуры данных?
  36. Наиболее распространенные структуры данных
  37. Массивы
  38. Простейшие операции с массивами
  39. Вопросы по массивам, часто задаваемые на собеседованиях
  40. Стеки
  41. Вопросы о стеке, часто задаваемые на собеседованиях
  42. Очереди
  43. Простейшие операции с очередью
  44. Вопросы об очередях, часто задаваемые на собеседованиях
  45. Связный список
  46. Простейшие операции со связными списками:
  47. Вопросы о связных списках, часто задаваемые на собеседованиях:
  48. Графы
  49. Вопросы о графах, часто задаваемые на собеседованиях:
  50. Деревья
  51. Вопросы о деревьях, часто задаваемые на собеседованиях:
  52. Вопросы о борах, часто задаваемые на собеседованиях:
  53. Хеш-таблица
  54. Вопросы о хешировании, часто задаваемые на собеседованиях:
  55. Структуры данных, которые необходимо знать каждому программисту
  56. Что такое структура данных?
  57. Массивы
  58. Основные операции с массивами
  59. Применение массивов
  60. Связанный список (Linked List)
  61. Основные операции со связанными списками
  62. Применение связанных списков
  63. Основные операции со стеком
  64. Применение стеков
  65. Очередь
  66. Основные операции с очередями
  67. Применение очередей
  68. Ключевые термины
  69. Распространенные алгоритмы обхода графов
  70. Основные операции с графами
  71. Применение графов
  72. Дерево
  73. Основные операции с BST
  74. Применение деревьев
  75. Хэш-таблица
  76. Хеширование (хэш-функция)
  77. Зачем нужен хэш?
  78. Коллизии
  79. Основные операции с хэш-таблицами
  80. Заключение
  81. Структуры данных для самых маленьких
  82. Что такое структуры данных?
  83. Алгоритмы
  84. О большое
  85. Память
  86. Списки
  87. Хеш-таблицы
  88. Стеки
  89. Очереди
  90. Графы
  91. Связные списки
  92. Деревья
  93. Двоичные деревья поиска
  94. Конец

Основные структуры данных. Матчасть. Азы

Все чаще замечаю, что современным самоучкам очень не хватает матчасти. Все знают языки, но мало основы, такие как типы данных или алгоритмы. Немного про типы данных.

Еще в далеком 1976 швейцарский ученый Никлаус Вирт написал книгу Алгоритмы + структуры данных = программы.

40+ лет спустя это уравнение все еще верно. И если вы самоучка и надолго в программировании пробегитесь по статье, можно по диагонали. Можно код кофе.

В статье так же будут вопросы, которое вы можете услышать на интервью.

Что такое структура данных?

Структура данных — это контейнер, который хранит данные в определенном макете. Этот «макет» позволяет структуре данных быть эффективной в некоторых операциях и неэффективной в других.

Какие бывают?

Линейные, элементы образуют последовательность или линейный список, обход узлов линеен. Примеры: Массивы. Связанный список, стеки и очереди.

Нелинейные, если обход узлов нелинейный, а данные не последовательны. Пример: граф и деревья.

Основные структуры данных.

Массивы

Массив — это самая простая и широко используемая структура данных. Другие структуры данных, такие как стеки и очереди, являются производными от массивов.

Изображение простого массива размера 4, содержащего элементы (1, 2, 3 и 4).

ivvjkxghqmm87r3ceaup

Каждому элементу данных присваивается положительное числовое значение (индекс), который соответствует позиции элемента в массиве. Большинство языков определяют начальный индекс массива как 0.

Бывают

Одномерные, как показано выше.
Многомерные, массивы внутри массивов.

Основные операции

Вопросы

Стеки

Стек — абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).

Это не массивы. Это очередь. Придумал Алан Тюринг.

Примером стека может быть куча книг, расположенных в вертикальном порядке. Для того, чтобы получить книгу, которая где-то посередине, вам нужно будет удалить все книги, размещенные на ней. Так работает метод LIFO (Last In First Out). Функция «Отменить» в приложениях работает по LIFO.

Изображение стека, в три элемента (1, 2 и 3), где 3 находится наверху и будет удален первым.

vupphsidgppdcjzld h6haiohv8

Основные операции

Вопросы

Очереди

Подобно стекам, очередь — хранит элемент последовательным образом. Существенное отличие от стека – использование FIFO (First in First Out) вместо LIFO.

Пример очереди – очередь людей. Последний занял последним и будешь, а первый первым ее и покинет.

Изображение очереди, в четыре элемента (1, 2, 3 и 4), где 1 находится наверху и будет удален первым

vsvzd nhfbt8lgqygo n6kevota

Основные операции

Вопросы

Связанный список

Связанный список – массив где каждый элемент является отдельным объектом и состоит из двух элементов – данных и ссылки на следующий узел.

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

Бывают

Однонаправленный, каждый узел хранит адрес или ссылку на следующий узел в списке и последний узел имеет следующий адрес или ссылку как NULL.

Двунаправленный, две ссылки, связанные с каждым узлом, одним из опорных пунктов на следующий узел и один к предыдущему узлу.

Круговой, все узлы соединяются, образуя круг. В конце нет NULL. Циклический связанный список может быть одно-или двукратным циклическим связанным списком.

Самое частое, линейный однонаправленный список. Пример – файловая система.

Основные операции

Вопросы

Графы

Граф-это набор узлов (вершин), которые соединены друг с другом в виде сети ребрами (дугами).

Бывают

Ориентированный, ребра являются направленными, т.е. существует только одно доступное направление между двумя связными вершинами.
Неориентированные, к каждому из ребер можно осуществлять переход в обоих направлениях.
Смешанные

Встречаются в таких формах как

Общие алгоритмы обхода графа

Вопросы

Деревья

Дерево-это иерархическая структура данных, состоящая из узлов (вершин) и ребер (дуг). Деревья по сути связанные графы без циклов.

Древовидные структуры везде и всюду. Дерево скилов в играх знают все.

7uicvvfrp5r11e6a ysnnueynu8

«Бинарное дерево — это иерархическая структура данных, в которой каждый узел имеет значение (оно же является в данном случае и ключом) и ссылки на левого и правого потомка. » — Procs

Три способа обхода дерева

Вопросы

Trie ( префиксное деревое )

Разновидность дерева для строк, быстрый поиск. Словари. Т9.

Вот как такое дерево хранит слова «top», «thus» и «their».

bgardz981ki0zew8rybb7iui9iu

Слова хранятся сверху вниз, зеленые цветные узлы «p», «s» и «r» указывают на конец «top», «thus « и «their» соответственно.

Вопросы

Хэш таблицы

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

Объект хранится в виде пары «ключ-значение», а коллекция таких элементов называется «словарем». Каждый объект можно найти с помощью этого ключа.

По сути это массив, в котором ключ представлен в виде хеш-функции.

Эффективность хеширования зависит от

Вопросы

Список ресурсов

Вместо заключения

Матчасть так же интересна, как и сами языки. Возможно, кто-то увидит знакомые ему базовые структуры и заинтересуется.

Спасибо, что прочли. Надеюсь не зря потратили время =)

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

Источник

Важнейшие структуры данных, которые вам следует знать к своему собеседованию по программированию

Никлаус Вирт, швейцарский ученый-информатик, в 1976 году написал книгу под названием «Алгоритмы + Структуры данных = Программы».

Через 40 с лишним лет это тождество остается в силе. Вот почему соискатели, желающие стать программистами, должны продемонстрировать, что знают структуры данных и умеют их применять.

Практически во всех задачах от кандидата требуется глубокое понимание структур данных. При этом не столь важно, выпускник ли вы (закончили университет или курсы программирования), либо у вас за плечами десятки лет опыта.

Иногда в вопросах на интервью прямо упоминается та или иная структура данных, например, «дано двоичное дерево». В других случаях задача формулируется более завуалированно, например, «нужно отследить, сколько у нас книг от каждого автора».

Изучение структур данных — незаменимое дело, даже если вы просто стараетесь профессионально совершенствоваться на нынешней работе. Начнем с основ.

Переведено в Alconost

image loader

Что такое структура данных?

Если коротко, структура данных — это контейнер, информация в котором скомпонована характерным образом. Благодаря такой «компоновке», структура данных будет эффективна в одних операциях и неэффективна — в других. Наша цель — разобраться в структурах данных таким образом, чтобы вы могли выбрать из них наиболее подходящую для решения конкретной стоящей перед вами задачи.

Зачем нужны структуры данных?

Поскольку структуры данных используются для хранения информации в упорядоченном виде, а данные — самый важный феномен в информатике, истинная ценность структур данных очевидна.

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

В зависимости от конкретного сценария, данные нужно хранить в подходящем формате. У нас в распоряжении — ряд структур данных, обеспечивающих нас такими различными форматами.

Наиболее распространенные структуры данных

Сначала давайте перечислим наиболее распространенные структуры данных, а затем разберем каждую по очереди:

Массивы

Массив — это простейшая и наиболее распространенная структура данных. Другие структуры данных, например, стеки и очереди, производны от массивов.

Здесь показан простой массив размером 4, содержащий элементы (1, 2, 3 и 4).
image loader
Каждому элементу данных присваивается положительное числовое значение, именуемое индексом и соответствующее положению этого элемента в массиве. В большинстве языков программирования элементы в массиве нумеруются с 0.

Существуют массивы двух типов:

Простейшие операции с массивами

Вопросы по массивам, часто задаваемые на собеседованиях

Стеки

Всем известна знаменитая опция «Отмена», предусмотренная почти во всех приложениях. Задумывались когда-нибудь, как она работает? Смысл такой: в программе сохраняются предшествующие состояния вашей работы (количество сохраняемых состояний ограничено), причем, они располагаются в памяти в таком порядке: последний сохраненный элемент идет первым. Одними массивами такую задачу не решить. Именно здесь нам пригодится стек.

Стек можно сравнить с высокой стопкой книг. Если вам нужна какая-то книга, лежащая около центра стопки, вам сначала придется снять все книги, лежащие выше. Именно так работает принцип LIFO (Последним пришел — первым вышел).

Так выглядит стек, содержащий три элемента данных (1, 2 и 3), где 3 находится сверху — поэтому будет убран первым:
image loader
Простейшие операции со стеком:

Вопросы о стеке, часто задаваемые на собеседованиях

Очереди

Очередь, как и стек — это линейная структура данных, элементы в которой хранятся в последовательном порядке. Единственное существенное отличие между стеком и очередью заключается в том, что в очереди вместо LIFO действует принцип FIFO (Первым пришел — первым вышел).

Идеальный реалистичный пример очереди — это и есть очередь покупателей в билетную кассу. Новый покупатель становится в самый хвост очереди, а не в начало. Тот же, кто стоит в очереди первым, первым приобретет билет и первым ее покинет.

Вот изображение очереди с четырьмя элементами данных (1, 2, 3 и 4), где 1 идет первым и первым же покинет очередь:
image loader

Простейшие операции с очередью

Вопросы об очередях, часто задаваемые на собеседованиях

Связный список

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

Связный список напоминает цепочку узлов, в каждом из которых содержится информация: например, данные и указатель на следующий узел в цепочке. Есть головной указатель, соответствующий первому элементу в связном списке, и, если список пуст, то он направлен просто на null (ничто).

При помощи связных списков реализуются файловые системы, хеш-таблицы и списки смежности.

Вот так можно наглядно изобразить внутреннюю структуру связного списка:
image loader

Существуют такие типы связных списков:

Простейшие операции со связными списками:

Вопросы о связных списках, часто задаваемые на собеседованиях:

Графы

Граф — это множество узлов, соединенных друг с другом в виде сети. Узлы также называются вершинами. Пара (x,y) называется ребром, это означает, что вершина x соединена с вершиной y. Ребро может иметь вес/стоимость — показатель, характеризующий, насколько затратен переход от вершины x к вершине y.
image loader

Вопросы о графах, часто задаваемые на собеседованиях:

Деревья

Дерево — это иерархическая структура данных, состоящая из вершин (узлов) и ребер, которые их соединяют. Деревья подобны графам, однако, ключевое отличие дерева от графа таково: в дереве не бывает циклов.

Деревья широко используются в области искусственного интеллекта и в сложных алгоритмах, выступая в качестве эффективного хранилища информации при решении задач.

Вот схема простого дерева и базовая терминология, связанная с этой структурой данных:
image loader

Существуют деревья следующих типов:

Вопросы о деревьях, часто задаваемые на собеседованиях:

Найдите высоту двоичного дерева
Найдите k-ное максимальное значение в двоичном дереве поиска
Найдите узлы, расположенные на расстоянии “k” от корня
Найдите предков заданного узла в двоичном дереве

Бор, также именуемый «префиксное дерево» — это древовидная структура данных, которая особенно эффективна при решении задач на строки. Она обеспечивает быстрое извлечение данных и чаще всего применяется для поиска слов в словаре, автозавершений в поисковике и даже для IP-маршрутизации.

Вот как три слова «top» (верх), «thus» (следовательно), and «their» (их) хранятся в бору:
image loader

Слова располагаются в направлении сверху вниз, и зеленые узлы «p», «s» и «r» завершают, соответственно, слова «top», «thus» и «their».

Вопросы о борах, часто задаваемые на собеседованиях:

Хеш-таблица

Хеширование — это процесс, применяемый для уникальной идентификации объектов и сохранения каждого объекта по заранее вычисленному индексу, именуемому его «ключом». Таким образом, объект хранится в виде «ключ-значение», а коллекция таких объектов называется «словарь». Каждый объект можно искать по его ключу. Существуют разные структуры данных, построенные по принципу хеширования, но чаще всего из таких структур применяется хеш-таблица.

Как правило, хеш-таблицы реализуются при помощи массивов.

Производительность хеширующей структуры данных зависит от следующих трех факторов:

Вопросы о хешировании, часто задаваемые на собеседованиях:

Удачи и интересного обучения! 🙂

Перевод статьи выполнен в Alconost.

Alconost занимается локализацией игр, приложений и сайтов на 68 языков. Переводчики-носители языка, лингвистическое тестирование, облачная платформа с API, непрерывная локализация, менеджеры проектов 24/7, любые форматы строковых ресурсов.

Мы также делаем рекламные и обучающие видеоролики — для сайтов, продающие, имиджевые, рекламные, обучающие, тизеры, эксплейнеры, трейлеры для Google Play и App Store.

Источник

Структуры данных, которые необходимо знать каждому программисту

%D0%B8%D0%B7%D0%BE%D0%B1%D1%80%D0%B0%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5 2021 04 18 190846

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

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

Что такое структура данных?

Независимо от профессии, ежедневная работа связана с данными. Шеф-повар, инженер-программист или даже рыбак — все они работают с теми или иными формами данных.

Структуры данных — это контейнеры, которые хранят данные в определенном формате. Этот специфический формат придает структуре данных определенные качества, которые отличают ее от других структур и делают ее пригодной (или напротив, неподходящей) для тех или иных сценариев использования.

Рассмотрим некоторые из наиболее важных структур данных, которые помогут создавать эффективные решения.

Массивы

Массивы — одна из самых простых и часто применяемых структур данных. Такие структуры данных, как очереди и стеки, основаны на массивах и связанных списках (которые мы рассмотрим чуть позже).

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

Существует два типа массивов: одномерные и многомерные. Первые представляют собой простейшие линейные структуры, а вторые — вложенные и включают другие массивы.

Основные операции с массивами

Применение массивов

Связанный список (Linked List)

Связанный список — это набор элементов, называемых узлами, в линейной последовательной структуре. Узел — простой объект с двумя свойствами. Это переменные для хранения данных и адреса памяти следующего узла в списке. Поэтому узел знает только о том, какие данные он содержит и кто его сосед. Это позволяет создавать связанные списки, в которых каждый узел связан с другим.

1*PLdEZaEaA0Tq9oSsFhdfJg

Существует несколько типов связанных списков.

Основные операции со связанными списками

Применение связанных списков

Стек — линейная структура данных, которая создается на основе массивов или связанных списков. Стек следует принципу Last-In-First-Out (LIFO, “первым на вход — последним на выход”), т.е. последний элемент, вошедший в стек, будет первым, кто покинет его. Причина, по которой эта структура называется стеком, в том, что ее можно визуализировать как стопку книг на столе (по-английски stack).

Основные операции со стеком

Применение стеков

1*CdSykgFllQeBAQNL L2QcA

Очередь

Как и стек, очередь — это еще один тип линейной структуры данных, основанной либо на массивах, либо на связанных списках. Очереди отличаются от стеков тем, что они основаны на принципе First-In-First-Out (FIFO, “первым на вход — первым на выход”), где элемент, который входит в очередь первым, и покинет ее первым.

Реальная аналогия структуры данных “очереди” — это очередь людей, ожидающих покупки билета в кино.

Основные операции с очередями

Применение очередей

1*qbta Z7wXy6IeaFttNyYGw

Ключевые термины

Графы делятся на два типа. Они различаются главным образом по направлениям пути между двумя вершинами.

Распространенные алгоритмы обхода графов

Основные операции с графами

Применение графов

Дерево

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

1*UE3lEecVlbDXgQgj0lpb0w

Существует несколько типов деревьев.

BST — самые распространенные типы деревьев.

Основные операции с BST

Применение деревьев

Хэш-таблица

Хэш-таблица хранит данные в парах ключ-значение. Это означает, что каждый ключ в хэш-таблице имеет некое значение, связанное с ним. Такая простая компоновка обеспечивает эффективность хэш-таблиц, независимо от их размера, при работе с данными.

Хэш-таблицы похожи на обычное хранилище данных с парой ключ-значение, однако их отличает способ генерации ключей. Они создаются с помощью специального процесса, называемого хэшированием.

Хеширование (хэш-функция)

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

Зачем нужен хэш?

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

Коллизии

Когда ключи равняются 18 и 35, происходит коллизия, поскольку они направляются к индексу 1.

Коллизии можно разрешить с помощью таких стратегий, как раздельная цепочка и открытая адресация.

Основные операции с хэш-таблицами

Заключение

Разработчикам важно знать хотя бы основы этих структур, поскольку при правильной реализации они помогут повысить эффективность ваших приложений.

Источник

Структуры данных для самых маленьких

James Kyle как-то раз взял и написал пост про структуры данных, добавив их реализацию на JavaScript. А я взял и перевёл.

Дисклеймер: в посте много ascii-графики. Не стоит его читать с мобильного устройства — вас разочарует форматирование текста.

image loader

Сегодня мы узнаем всё о структурах данных.

«Оооооой как интересно. », да?

Да уж, не самая сочная тема на сей день, однако крайне важная. Не для того, чтобы сдавать курсы наподобие CS101, а чтобы лучше разбираться в программировании.

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

Чтобы познакомиться со структурами данных, мы реализуем некоторые из них. Не беспокойтесь, код будет лаконичен. На самом деле, тут больше комментариев, а кода между ними — раз, два и обчёлся.

Что такое структуры данных?

По сути, это способы хранить и организовывать данные, чтобы эффективней решать различные задачи. Данные можно представить по-разному. В зависимости от того, что это за данные и что вы собираетесь с ними делать, одно представление подойдёт лучше других.

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

Алгоритмы

Алгоритм — такое хитроумное название для последовательности совершаемых действий.

Структуры данных реализованы с помощью алгоритмов, алгоритмы — с помощью структур данных. Всё состоит из структур данных и алгоритмов, вплоть до уровня, на котором бегают микроскопические человечки с перфокартами и заставляют компьютер работать. (Ну да, у Интела в услужении микроскопические люди. Поднимайся, народ!)

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

Например, для сортировки неупорядоченного множества элементов существует до смешного большое количество алгоритмов:

Сортировка вставками, Сортировка выбором, Сортировка слиянием, Сортировка пузырьком, Cортировка кучи, Быстрая сортировка, Сортировка Шелла, Сортировка Тима, Блочная сортировка, Поразрядная сортировка.

Некоторые из них значительно быстрее остальных. Другие занимают меньше памяти. Третьи легко реализовать. Четвёртые построены на допущениях относительно наборов данных.

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

Для сравнения производительности алгоритмов используется грубое измерение средней производительности и производительности в худшем случае, для обозначения которых используется термин «О» большое.

О большое

«О» большое — обозначение способа приблизительной оценки производительности алгоритмов для относительного сравнения.

О большое — заимствованное информатикой математические обозначение, определяющее, как алгоритмы соотносятся с передаваемым им некоторым количеством N данных.

О большое характеризует две основные величины:

Оценка времени выполнения — общее количество операций, которое алгоритм проведёт на данном множестве данных.

Оценка объёма — общее количество памяти, требующееся алгоритму для обработки данного множества данных.

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

Вот некоторые распространённые значения О большого:

Чтобы дать представление, о каких порядках чисел мы говорим, давайте взглянем, что это будут за значения в зависимости от N.

Как видите, даже при относительно небольших числах можно сделать *дофига* дополнительной работы.

Структуры данных позволяют производить 4 основных типа действий: доступ, поиск, вставку и удаление.

Замечу, что структуры данных могут быть хороши в одном из действий, но плохи в другом.

Кроме того, некоторые действия имеют разную «среднюю» производительность и производительность в «самом худшем случае».

Идеальной структуры данных не существует. Вы выбираете самую подходящую, основываясь на данных и на том, как они будут обрабатываться. Чтобы сделать правильный выбор, важно знать различные распространённые структуры данных.

Память

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

Фрагмент памяти можно представить так:

Если вы задумывались, почему в языках программирования отсчёт начинается с 0 — потому, что так работает память. Чтобы прочитать первый фрагмент памяти, вы читаете с 0 до 1, второй — с 1 до 2. Адреса этих фрагментов соответственно равны 0 и 1.

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

Просторы памяти — как Дикий Запад. Каждая работающая на компьютере программа хранится внутри одной и той же *физической* структуры данных. Использование памяти — сложная задача, и для удобной работы с ней существуют дополнительные уровни абстракции.

Абстракции имеют два дополнительных назначения:

— Сохраняют данные в памяти таким образом, чтобы с ними было эффективно и/или быстро работать.

— Сохраняют данные в памяти так, чтобы их было проще использовать.

Списки

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

Список — представление пронумерованной последовательности значений, где одно и то же значение может присутствовать сколько угодно раз.

Начнём с пустого блока памяти, представленного обычным JavaScript-массивом. Также нам понадобится хранить значение длины списка.

Заметьте, что мы хотим хранить длину отдельно, поскольку в реальности у «памяти» нет значения length, которое можно было бы взять и прочитать.

Первым делом нужно получать данные из списка. Обычный список позволяет очень быстро получить доступ к памяти, поскольку вы уже знаете нужный адрес.

Сложность операции доступа в список — O(1) — «ОХРЕНЕННО!!»

У списков есть порядковые номера, поэтому можно вставлять значения в начало, середину и конец.

Это настолько же легко, как добавить значение в адрес, следующий за нашим списком. Поскольку мы храним длину, вычислить адрес — проще простого. Добавим значение и увеличим длину.

Добавление элемента в конец списка — константа O(1) — «ОХРЕНЕННО!!»

Комментарии хабра: poxu не согласен с автором и объясняет, что существует операция расширения памяти, увеличивающая сложность добавления элементов в список.

Далее, реализуем метод «pop», убирающий элемент из конца нашего списка. Аналогично push, всё, что нужно сделать — убрать значение из последнего адреса. Ну, и уменьшить длину.

Удаление элемента из конца списка — константа O(1) — «ОХРЕНЕННО!!»

«Push» и «pop» работают с концом списка, и в общем-то являются простыми операциями, поскольку не затрагивают весь остальной список.

Давайте посмотрим, что происходит, когда мы работаем с началом списка, с операциями «unshift» и «shift».

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

Чтобы сделать такой сдвиг, нужно пройтись по каждому из элементов и поставить на его место предыдущий.

Поскольку мы вынуждены пройтись по каждому из элементов списка:

Добавление элемента в начало списка — линейно O(N) — «НОРМАС.»

Осталось написать функцию сдвига списка в противоположном направлении — shift.

Мы удаляем первое значение и затем сдвигаем каждый элемент списка на предшествующий адрес.

Удаление элемента из начала списка — линейно O(N) — «НОРМАС.»

Списки отлично справляются с быстрым доступом к элементам в своём конце и работой с ними. Однако, как мы увидели, для элементов из начала или середины они не слишком хороши, так как приходится вручную обрабатывать адреса памяти.

Давайте посмотрим на иную структуру данных и её методы по добавлению, доступу и удалению значений без необходимости знать адреса элементов.

Хеш-таблицы

Хеш-таблица — неупорядоченная структура данных. Вместо индексов мы работаем с «ключами» и «значениями», вычисляя адрес памяти по ключу.

Смысл в том, что ключи «хешируются» и позволяют эффективно работать с памятью — добавлять, получать, изменять и удалять значения.

Вновь используем обычный JavaScript-массив, представляющий память.

Чтобы сохранять пары ключ-значение из хеш-таблицы в память, нужно превращать ключи в адреса. Этим занимается операция «хеширования».

Она принимает на вход ключ и преобразовывает его в уникальное число, соответствующее этому ключу.

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

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

Любая реализация хеш-таблиц сталкивается с этой проблемой.

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

Давайте определим функцию «hashKey».

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

Теперь определим функцию «get», получающую значение по ключу.

Сложность чтения значения из хеш-таблицы — константа O(1) — «ОХРЕНЕННО!!»

Перед тем, как получать данные, неплохо бы их сперва добавить. В этом нам поможет функция «set».

Сложность установки значения в хеш-таблицу — константа O(1) — «ОХРЕНЕННО!!»

Наконец, нужен способ удалять значения из хеш-таблицы. Сложность удаления значения из хеш-таблицы — константа O(1) — «ОХРЕНЕННО!!»

Теперь мы прекратим работать с памятью напрямую: все последующие структуры данных будут реализовываться через другие структуры данных.

Стеки

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

Однако стеки могут быть реализованы через другие структуры данных, чтобы получить дополнительную функциональность.

Наиболее общий пример использования стеков — у вас есть один процесс, добавляющий элементы в стек и второй, удаляющий их из конца — приоритизируя недавно добавленные элементы.

Нам вновь понадобится JavaScript-массив, но на этот раз он символизирует не память, а список, вроде реализованного выше.

Нам понадобится реализовать два метода, функционально идентичных методам списка — «push» и «pop».

Push добавляет элементы на верхушку стека.

Pop удаляет элементы из верхушки.

Кроме того, добавим функцию peek, показывающую элемент на верхушке стека без его удаления. Прим. переводчика: peek – взглянуть.

Очереди

Теперь создадим очередь — структуру, комплементарную стеку. Разница в том, что элементы очереди удаляются из начала, а не из конца, т.е. сначала старые элементы, потом новые.

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

И вновь мы призываем на помощь JavaScript-массив! В случае с очередью мы опять рассматриваем его как список, а не как память.

Аналогично стекам мы определяем две функции для добавления и удаления элементов из очереди.

Первым будет «enqueue» — добавление элемента в конец списка.

Далее — «dequeue». Элемент удаляется не из конца списка, а из начала.

Аналогично стекам объявим функцию «peek», позволяющую получить значение в начале очереди без его удаления.

Важно заметить, что, поскольку для реализации очереди использовался список, она наследует линейную производительность метода shift (т.е. O(N) — «НОРМАС.»).

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

С этого места и далее мы будем работать со структурами данных, где значения ссылаются друг на друга.

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

Сейчас вы поймёте, что я имею ввиду.

Графы

На самом деле граф — совсем не то, о чём вы подумали, увидев ascii-график.

Граф — структура наподобие этой:

image loader

Эти вершины можно представить вот так:

А весь граф будет выглядеть вот так:

Представим список вершин JavaScript-массивом. Массив используется не с целью специально упорядочить вершины, а как место для хранения вершин.

Начнём добавлять значения в граф, создавая вершины без каких-либо линий.

Теперь нужен способ искать вершины в графе. Обычно для ускорения поиска делается ещё одна структура данных поверх графа.

Но в нашем случае мы просто переберём все вершины, чтобы найти соответствующую значению. Способ медленный, но работающий.

Теперь мы можем связать две вершины, проведя «линию» от одной до другой (прим. переводчика: дугу графа).

Полученный граф можно использовать вот так:

Кажется, что для такой мелкой задачи сделано слишком много работы, однако это мощный паттерн.

Он часто применяется для поддержания прозрачности в сложных программах. Это достигается оптимизацией взаимосвязей между данными, а не операций над самими данными. Если вы выберете одну вершину в графе, невероятно просто найти связанные с ней элементы.

Графами можно представлять уйму вещей: пользователей и их друзей, 800 зависимостей в папке node_modules, даже сам интернет, являющийся графом связанных друг с другом ссылками веб-страниц.

Связные списки

Давайте теперь посмотрим, как графоподобная структура может оптимизировать упорядоченный список данных.

Связные списки — распространённая структура данных, зачастую используемая для реализации других структур. Преимущество связного списка — эффективность добавления элементов в начало, середину и конец.

Связный список по своей сути похож на граф: вы работаете с вершинами, указывающими на другие вершины. Они расположены таким образом:

Если представить эту структуру в виде JSON, получится нечто такое:

В отличие от графа, связный список имеет единственную вершину, из которой начинается внутренняя цепочка. Её называют «головой», головным элементом или первым элементом связного списка.

Также мы собираемся отслеживать длину списка.

Первым делом нужен способ получать значение по данной позиции.

В отличие от обычных списков мы не можем перепрыгнуть на нужную позицию. Вместо этого мы должны перейти к ней через отдельные вершины.

Теперь необходим способ добавлять вершины в выбранную позицию.

Создадим метод add, принимающий значение и позицию.

Последний метод, который нам понадобится — remove. Найдём вершину по позиции и выкинем её из цепочки.

Две оставшиеся структуры данных относятся к семейству «деревьев».

Как и в жизни, существует множество различных древовидных структур данных.

Прим. переводчика: ну не-е-е-е, я пас…

Binary Trees:
AA Tree, AVL Tree, Binary Search Tree, Binary Tree, Cartesian Tree, left child/right sibling tree, order statistic tree, Pagoda,…

B Trees:
B Tree, B+ Tree, B* Tree, B Sharp Tree, Dancing Tree, 2-3 Tree,…

Heaps:
Heap, Binary Heap, Weak Heap, Binomial Heap, Fibonacci Heap, Leonardo Heap, 2-3 Heap, Soft Heap, Pairing Heap, Leftist Heap, Treap,…

Trees:
Trie, Radix Tree, Suffix Tree, Suffix Array, FM-index, B-trie,…

Multi-way Trees:
Ternary Tree, K-ary tree, And-or tree, (a,b)-tree, Link/Cut Tree,…

Space Partitioning Trees:
Segment Tree, Interval Tree, Range Tree, Bin, Kd Tree, Quadtree, Octree, Z-Order, UB-Tree, R-Tree, X-Tree, Metric Tree, Cover Tree,…

Application-Specific Trees:
Abstract Syntax Tree, Parse Tree, Decision Tree, Minimax Tree,…

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

Деревья похожи на графы или связные списки, с той разницей, что они «однонаправленые». Это значит, что в них не может существовать циклических ссылок.

image loader

Если вы можете пройти круг по вершинам дерева… что ж, поздравляю, но это не дерево.

Деревья применяются во множестве задач. Они используются для оптимизации поиска или сортировки. Они могут лучше организовывать программу. Они могут создать представление, с которым проще работать.

Деревья

Начнём с простой древовидной структуры. В ней нет особых правил, и выглядит она примерно так:

Дерево должно начинаться с единственного родителя, «корня» дерева.

Нам нужен способ обходить наше дерево и вызывать определённую функцию в каждой его вершине.

Теперь нужен способ добавлять вершины в дерево.

Это простое дерево, возможно, полезное лишь в случае, когда отображаемые данные на него похожи.

Однако при наличии дополнительных правил деревья могут выполнять кучу различных задач.

Двоичные деревья поиска

Двоичные деревья поиска — распространённая форма деревьев. Они умеют эффективно читать, искать, вставлять и удалять значения, сохраняя при этом отсортированный порядок.

Представьте, что у вас есть последовательность чисел:

Развернём её в дерево, начинающееся из центра.

Это делает обход дерева при поиске значения очень эффективным. Например, попробуем найти число 5 в нашем дереве.

Заметьте, чтобы добраться до 5, потребовалось сделать лишь 3 проверки. А если бы дерево состояло из 1000 элементов, путь был бы таким:

Всего 10 проверок на 1000 элементов!

Ещё одной важной особенностью двоичных деревьев поиска является их схожесть со связными списками — при добавлении или удалении значения вам нужно обновлять лишь непосредственно окружающие элементы.

Как и в прошлой секции, сперва нужно установить “корень” двоичного дерева поиска.

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

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

Однако теперь, когда мы доберёмся до левой или правой вершины, равной null,
мы добавим вершину в эту позицию.

Конец

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

Также можете прочитать другую мою статью, «The Super Tiny Compiler» github.com/thejameskyle/the-super-tiny-compiler

Также эту статью можно прочитать на гитхабе.

Перевод: aalexeev, редактура: iamo0, Чайка Чурсина.

Источник

Мир познаний
Добавить комментарий

Adblock
detector