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

Вступление

Алгоритмы и структуры данных считаются основными навыками инженеров-программистов. Насколько полезны эти навыки для специалистов по обработке данных и аналитиков?

Типичный специалист по данным проводит большую часть своего времени на языках высокого уровня, таких как 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