Основные алгоритмы и структуры данных
Структура данных должна быть спроектирована согласно требованиям вашего приложения. Вы можете сохранить все данные в один гигантский массив, но понадобится слишком много времени для поиска необходимой информации. Поэтому нужно использовать другой подход.
В зависимости от приложения, вам доступно несколько основных структур. Разница между ними обусловлена компромиссами между тем, как много времени понадобиться на создание структуры, как просто добавлять или находить элементы и как много места занимает структура в памяти.
Мы опустим подробности и нюансы различных структур данных, но как обычно предоставим вам минимальный набор инструментов. С ним вы сможете идентифицировать и решить основные проблемы по хранению массивов, хешей и объектов. Новые подходы особенно актуальны при поиске специфического поля в большом массиве данных и при планировании будущих запросов.
Вы уже ознакомились с кратким введением в алгоритмы в предыдущих уроках, а также написали свой собственную Сортировку слиянием. Вы увидите, что алгоритмы сортировки довольно распространены. Другой важной особенностью алгоритмов, является скорость поиска в миллисекундах. Очень важно качество вашего алгоритма в больших объемах информации. Обход дерева данных в поисках определенного элемента довольно частая задача.
К счастью все эти проблемы уже давным-давно решены. Понимание того, как они решены, дадут вам великолепные инструменты для решения (подобных) проблем в будущем. Алгоритмы - это путь к решению систематических проблем. В этом кратком введении мы фокусируемся на нескольких вариантах, которые вы сможете использовать по своему усмотрению. Это поиск в ширину и поиск в глубину.
Пункты для размышления
Постарайтесь ответить на предложенные вопросы. После выполнения задания попробуйте ответить на них ещё раз
- Что такое структура данных?
- Что такое стек?
- Что такое очередь?
- Какая разница между стеком и очередью?
- В чем польза стека?
- В чем польза очереди?
- Какой лучший способ применить стеки и очереди в Ruby (подсказка: думай просто)?
- Зачем иметь много различных методов поиска?
- Расскажите про поиск в ширину (BFS)?
- Чем является поиск в глубину (DFS)?
- В каких ситуациях вы бы использовали BFS?
- В каких ситуациях вы бы использовали DFS?
- Когда BFS непрактичен?
Задания
- Ознакомьтесь со статьей о структурах данных на Wikipedia.
- Изучите Очередь и Стеки в этом видео
- Узнайте о бинарном поиске здесь от CS50x.
- Ознакомьтесь с базовыми алгоритмами в курсе Coursera. Первые 10 минут важны для для понимания алгоритмов, остальная часть с большим математическим углублением.
- Прочитайте введение в алгоритмы для веб-разработчиков для еще одного взгляда на базовые алгоритмы.
- Наконец, изучите методы поиска в ширину и глубину в этом видео на YouTube.
Дополнительные ресурсы
Этот раздел содержит полезные ссылки на дополнительные материалы. Они не обязательны, так что расценивайте их как нечто полезное, если вы хотите поглубже погрузиться в тему
- Великолепный курс в Академии Хана
- Углубленные курсы по алгоритмам
- Визуализация алгоритмов от Майка Бостока
- Бесплатные курсы от Coursera
- Другие бесплатные курсы от Udacity
- Краткая инструкция по Сортировке, Префиксному дереву и Куче в Ruby, от Ильи Григорика Ilya Grigorik