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

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

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

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

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

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

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

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

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

Задания

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

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

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

• Великолепный курс в Академии Хана
• Углубленные курсы по алгоритмам
• Визуализация алгоритмов от Майка Бостока
• Бесплатные курсы от Coursera
• Другие бесплатные курсы от Udacity
• Краткая инструкция по Сортировке, Префиксному дереву и Куче в Ruby, от Ильи Григорика Ilya Grigorik