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

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

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

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

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

К счастью все эти проблемы уже давным-давно решены. Понимание того, как они решены, дадут вам великолепные инструменты для решения (подобных) проблем в будущем. Алгоритмы - это путь к решению систематических проблем. В этом кратком введении мы фокусируемся на нескольких вариантах, которые вы сможете использовать по своему усмотрению. Это поиск в ширину и поиск в глубину.

Пункты для размышления

Постарайтесь ответить на предложенные вопросы. После выполнения задания попробуйте ответить на них ещё раз

  • Что такое структура данных?
  • Что такое стек?
  • Что такое очередь?
  • Какая разница между стеком и очередью?
  • В чем польза стека?
  • В чем польза очереди?
  • Какой лучший способ применить стеки и очереди в Ruby (подсказка: думай просто)?
  • Зачем иметь много различных методов поиска?
  • Расскажите про поиск в ширину (BFS)?
  • Чем является поиск в глубину (DFS)?
  • В каких ситуациях вы бы использовали BFS?
  • В каких ситуациях вы бы использовали DFS?
  • Когда BFS непрактичен?

Задания

  1. Ознакомьтесь со статьей о структурах данных на Wikipedia.
  2. Изучите Очередь и Стеки в этом видео
  3. Узнайте о бинарном поиске здесь от CS50x.
  4. Ознакомьтесь с базовыми алгоритмами в курсе Coursera. Первые 10 минут важны для для понимания алгоритмов, остальная часть с большим математическим углублением.
  5. Прочитайте введение в алгоритмы для веб-разработчиков для еще одного взгляда на базовые алгоритмы.
  6. Наконец, изучите методы поиска в ширину и глубину в этом видео на YouTube.

Дополнительные ресурсы

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

Поделиться уроком: