Понимание таких концепций, как алгоритмическая сложность и правильное использование структур данных, позволит вам писать более оптимальный код.
Вступление
Алгоритмы и структуры данных считаются основными навыками инженеров-программистов. Насколько полезны эти навыки для специалистов по обработке данных и аналитиков?
Типичный специалист по данным проводит большую часть своего времени на языках высокого уровня, таких как Python / R / SQL, и ему редко приходится задумываться о базовых реализациях. Это связано с тем, что большинство алгоритмов анализа данных и машинного обучения уже упакованы в готовые к использованию, сильно оптимизированные библиотеки, такие как Scikit-Learn, Numpy, Pandas и другие (у поклонников R есть свои собственные инструменты).
Чтобы ответить на вопрос, стоят ли алгоритмы и структуры данных вашего времени, я перечислю несколько инструментов, которые вы будете иметь в своем арсенале после прохождения типичного курса алгоритмов.
Алгоритмическая сложность
Первое полезное понятие, с которым вы столкнетесь, - это алгоритмическая сложность и нотация Big-Oh. Это метод, который позволяет понять, насколько хорошо ваш код масштабируется с данными. Эта концепция важна для специалистов по данным из-за необходимости обрабатывать постоянно увеличивающийся объем информации, производимой ежедневно.
Избавившись от менее важных деталей, вы сможете оценить производительность алгоритма независимо от того, написан он на Python или C и выполняется на ноутбуке или суперкомпьютере НАСА. В некотором смысле он определяет базовый словарь для разработки и анализа алгоритмов, подавляя при этом архитектуру и детали, зависящие от языка - они считаются постоянным фактором, не имеющим отношения к общей картине.
В качестве примера представьте, что вас просят выбрать алгоритм машинного обучения для определенной задачи классификации и вы рассматриваете возможность использования машины опорных векторов (SVM) из-за ее хорошей способности обрабатывать границы нелинейных решений. Вы открываете документацию, чтобы проверить детали SVM, и замечаете следующее:
Поняв алгоритмическую сложность, вы можете пересмотреть использование SVM для больших наборов данных из-за высоких требований к вычислительным ресурсам в диапазоне от O (n²) до O (n³). Это означает, что если мы удвоим объем данных, время выполнения, вероятно, увеличится от 4 до 8 раз.
Небольшое предостережение по поводу обозначения Big-Oh - это считается «асимптотическим анализом», что в теории справедливо только для достаточно больших входных данных из-за наличия постоянных факторов, которые на практике могут быть довольно большими.
Графические алгоритмы
Алгоритмы графов актуальны в мире науки о данных, имея приложения для обнаружения мошенничества, кластеризации, ранжирования, систем рекомендаций и т. Д.
Обычно в курсах алгоритмов основное внимание уделяется графам, вероятно, потому, что на них легче продемонстрировать общие парадигмы алгоритмов.
Среди графовых алгоритмов вы встретите:
- Общий поиск по графам - позволяет выполнять общий поиск по графам.
- Кратчайший путь - позволяет вычислить кратчайший путь между любыми двумя вершинами. Применимо для таких задач, как сетевой анализ, навигация, подключение к социальным сетям и обнаружение мошенничества.
- Связанные компоненты и минимум разрезов - позволяет обнаруживать сообщества и кластеры на графике.
- Минимальное остовное дерево - полезно для кластеризации и сегментации изображений.
Вы потратите много времени на изучение алгоритмов на графах и сможете реализовывать быстрые решения.
Даже если вы с большей вероятностью будете использовать существующие реализации алгоритмов графов вместо того, чтобы писать их с нуля, знание внутренней работы и ограничений поможет вам выбрать правильный алгоритм для задачи.
Структуры данных
Python - это пример языка программирования с удобными и универсальными структурами данных. Настолько удобно, что многие люди склонны использовать список Python в качестве хранилища данных по умолчанию для всех своих нужд. Это может привести к значительным узким местам производительности в определенных сценариях.
Изучая структуры данных, вы поймете их сильные и слабые стороны и сможете рассуждать о применимости структуры данных для различных задачи.
Вы узнаете о полезных структурах данных, таких как:
- Куча - для случаев использования, когда вам требуются вычисления для объектов, имеющих минимальные (или максимальные) значения. Интересные применения куч - это моделирование, управляемое событиями, и онлайн-(потоковое) вычисление медианы.
- Деревья двоичного поиска - структура данных швейцарского ножа, очень эффективная для множества операций, таких как вставка, выбор и поиск.
- Хеш-таблицы - позволят понять, как наборы и словари реализуются за кулисами и почему они предпочтительны для приложений поиска. Вы узнаете о хэш-функциях, конфликтах и рисках безопасности, возникающих из-за неправильной реализации.
- Одна из наиболее интересных структур данных - это фильтр Блума. Это вероятностная структура данных, подходящая для эффективного хранения и поиска. Небольшая оговорка - вероятность ложного срабатывания у него отличная от нуля, когда утверждается, что объект присутствует, хотя на практике это не так. Для некоторых приложений этот недостаток не критичен. Например, фильтры Блума используются в веб-браузерах для кэширования адресов недавно посещенных страниц и в интернет-маршрутизаторах.
Распознавание узких мест и оптимизация вычислений с помощью соответствующих структур данных позволит вам на порядок ускорить определенные приложения. Это особенно актуально для специалистов по обработке данных, которые занимаются проблемами моделирования и оптимизации.
Алгоритмические парадигмы
Вы поймете общие способы решения множества алгоритмических проблем:
- Алгоритмы разделяй и властвуй - деление больших проблем на более мелкие подзадачи и рекурсивное решение. Лучше всего демонстрируется использование алгоритмов сортировки.
- Рандомизированные алгоритмы - оптимальное решение, основанное на теории вероятностей. Это особенно интересно с точки зрения науки о данных. Примеры использования - QuickSort или поиск статистики порядка i, такой как минимум, максимум или медиана.
- Жадные алгоритмы - интуитивно понятные алгоритмы, полезные для таких приложений, как планирование и кеширование.
- Динамическое программирование - применимо к множеству задач. Обычно демонстрируется с помощью «задачи о ранце» [1], которая за кулисами представляет собой проблему ограниченной оптимизации, возникающую в нескольких реальных сценариях.
Преимущество изучения алгоритмических парадигм - вы узнаете, как создаются алгоритмы без привязки к какому-либо языку программирования, и сможете применить эти знания в своей работе.
Непреодолимые проблемы
Если вам когда-либо было интересно, что означает «NP-полнота» [2] - добро пожаловать в мир неразрешимых проблем. Вы поймете, какие проблемы считаются неразрешимыми и почему нет проверенного способа гарантировать оптимальное решение, кроме перебора. Эти проблемы являются активной областью исследований до сегодняшнего дня и считаются сложнейшими проблемами теоретической информатики.
Вы сможете распознавать проблемы NP-Complete и различные подходы к получению приближенных решений с использованием таких методов, как эвристика и локальный поиск. Типичным примером проблемы NP-Complete является задача «Коммивояжер» [3].
На практике вы редко встретите проблемы NP-Complete, однако знание того, что они существуют и как их решать, полезно.
Резюме
В этой статье мы обсудили несколько важных концепций, которые вы поймете после изучения алгоритмов и структур данных:
- Алгоритмическая сложность
- Графические алгоритмы
- Структуры данных
- Алгоритмические парадигмы
- Непреодолимые проблемы
Знание этих концепций улучшит ваше понимание программной части науки о данных и позволит вам писать лучший код.
использованная литература
[1] Задача о рюкзаке, Википедия, https://en.wikipedia.org/wiki/Knapsack_problem
[2] NP-Completeness, Wikipedia, https://en.wikipedia.org/wiki/NP-completeness.
[3] Задача коммивояжера, Википедия, https://en.wikipedia.org/wiki/Travelling_salesman_problem