для чего нужны алгоритмы и структуры данных
Для чего изучать структуры данных и алгоритмы
Грамотное структурирование данных и общая схема алгоритма программы имеют большое значение для получения эффективной программы или веб-приложения. Программист должен владеть такими навыками, иначе будет написан плохой исходный код.
Если человек решил выбрать для себя путь программиста или веб-разработчика, то ему придётся столкнуться с одним или несколькими языками программирования. Чтобы создать хороший исходный код обязательно следует изучить структуры данных и алгоритмы.
Сегодня пользуются популярностью следующие языки программирования:
Структуры данных
Есть несколько типов переменных: целое число, дробное число (с плавающей точкой), строка, символ, истина или ложь и так далее.
Ошибки большинства начинающих программистов связаны с неправильным использованием типов данных. Есть ряд правил, в числе которых запрет на проведение тех или иных действий с данными разных типов. Например, нельзя провести операцию сложения между числовыми и строковыми значениями.
Переменная выбранного типа занимает определённую ячейку в оперативной памяти. При структурировании данных, нужно рационально разбивать переменные по типам. Нет смысла делать для выбора из двух вариантов переменную числового типа.
Алгоритмы
Если структуры данных необходимы для работы с входной, преобразуемой и исходной информацией, то алгоритм является последовательностью действий, которые программа выполняет для достижения какой-то задачи.
Знание синтаксиса языка программирования позволяет написать эффективный алгоритм со сниженным количеством строк исходного кода.
Основные действия, за которые отвечает алгоритм программы:
Список можно и продолжать, но стоит остановиться именно на этих компонентах, общих для подавляющего большинства языков.
Программа, написанная на C++, будет самостоятельно отрисовывать пользовательский интерфейс. Но если это языки PHP или Python, исполняемые на стороне сервера, то внешняя часть будет оформлена за счёт HTML и CSS.
Составление в алгоритме удобного способа вводить данные и задавать программе, что конкретно она должна с ними делать, важная часть в работе программиста. Конечно, если программист адаптирует программу под личное использование, то здесь можно ограничиться самым примитивным интерфейсом в рамках имеющихся задач.
Ваши алгоритмы должны быть хорошо структурированы и эффективно решать все стоящие перед программой задачи.
Нужны ли программисту алгоритмы и структуры данных
Денис Цьоменко, разработчик в DataRobot, поделился с DOU.UA своими наблюдениями о том, пригождается ли программисту на практике знание алгоритмов.
Впервые я написал строчку кода 10 лет назад. С тех пор я каждый день удивляюсь, как много возможностей открыла для человечества разработка. В разработку же меня привело решение алгоритмических задач и участие в соревнованиях по программированию. Первый коммерческий проект я завершил 7 лет назад. Тогда осознал, что недостаточно написать рабочий эффективный код за короткое время. Инженер должен знать архитектурные подходы, придерживаться стиля и банально писать читаемый код.
Но статья будет скорее о первом: о написании рабочего эффективного кода, который прослужит долго. Она будет полезна как новичкам, которые ищут возможности для профессионального роста, так и для опытных специалистов, которые знают несколько языков, могут прихлопнуть любой баг и тянуть любой проект, но стремятся к разработке новых проектов.
Вечный холивар по теме «нужна ли программисту математика» подвергается изменению и превращается в более опасный для индустрии спор. Все чаще на форумах, конференциях и в головах мелькает мысль: «Нужно ли программисту знать алгоритмы и структуры данных?». И этот спор имеет место быть. Сомнительно, что разрабатывая продукт, придется самостоятельно реализовывать быструю сортировку или словарь. Продвинутые же структуры данных пригодятся не более чем 10-20% инженеров. И даже если человек входит в этот процент, он возразит: «Все гуглится и учится за пару дней».
Мысль противоположной стороны выражается так: «Через 5-7 лет 80% задач, которые необходимы при разработке продукта, смогут выполнять школьники 13-14 лет, которые закончили качественные курсы. Но компаниям нужны инженеры, способные решить остальные 20%». Это могут быть знания и в математической статистике, и в алгебре, и в теории программирования. Но фундамент, в любом случае, строится на знаниях алгоритмов и структур данных.
«Нельзя доверять коду, который вы не написали полностью сами», — Кен Томпсон.
Алгоритмы на собеседованиях
В каждой компании есть свой подход к собеседованиям и оценке кандидатов. Также отличаются цели найма. Но есть вещи, которые их объединяют. Я проходил собеседования в различные компании разных размеров и направлений. Где-то алгоритмы и решение задач были ключевым фактором, где-то — вспомогательным. Задачи могут быть разных уровней сложности. Например, самая простая из тех, что мне встречались, — развернуть строку без использования дополнительной памяти. Одна из задач сводилась к умению быстро считать максимальное значение функции xor на префиксном дереве (бор). Ее сложность скорее заключалась в неочевидном решении, чем в реализации. Хорошая задача на собеседовании должна иметь несколько возможных решений, кроме оптимального. Невозможно знать все.
Пример плохой задачи, которую я встретил на собеседовании, это нахождения решения системы обычных дифференциальных уравнений. За вменяемое время невозможно приблизиться к решению, если ты не знаешь алгоритм Рунге-Кутты. Такого же типа собеседования обычно рассчитаны как раз не на проверку умения заучивать редкие алгоритмы, а на умение эффективно использовать стандартные. Чем же отличаются подходы в разных компаниях?
Большие корпорации
Компаниям-гигантам не важно, какой язык Вы знаете или сколько фреймворков выучили. Microsoft, Google или Tesla не нужны «исполнители», которых у них десятки тысяч. Этим компаниям нужны люди, которые смогут придумать и создать новый продукт, оптимизировать устаревший и дальше продвигать эти компании вверх. Умножьте это на количество кандидатов и необходимый ресурс для отбора. В итоге получим «алгоритмические» собеседования. Такой подход критикуют, пытаются изменить и усовершенствовать. Например, вопросами по софт скиллам или по дизайну систем. Подобные интервью иногда отсеивают достойных кандидатов, но продолжают проводиться и доказывать эффективность.
Нравится вам это или нет, но чтобы попасть в подобную компанию, вам необходимы алгоритмы. Разница между большими и средними компаниями в том, что в первых реже встречаются задачи уровня Hard, а знаний продвинутых алгоритмов не требуют, потому что они набирают много кандидатов и упустить хорошего инженера из-за незнания отдельно взятой структуры данных просто невыгодно.
Пройти такое собеседование помогут даже не знания алгоритмов, а количество решенных типичных задач. Важно понимать, что правильное решение не всегда гарантирует успешное прохождение собеседования. Точно также, как и неоптимальное решение не гарантирует отказ. Люди хотят работать с людьми, а не с машинами для написания кода, поэтому хотят посмотреть, как Вы думаете и говорите. В развитии этого навыка очень помогают пробные интервью. Вы можете проводить их с другом, коллегой или на различных ресурсах, где можно провести и пройти интервью со случайными людьми. Классическим же мануалом по прохождению в большие корпорации является книга «Cracking the Coding Interview». И если Вы хотите попасть в одну из них, то советую прочитать.
Минимальный набор знаний для прохождения интервью в большие компании
Средние компании
Опыт лучших перенимают и организации, которые гонятся за ними. В Украине существует минимум 3 компании, которые фокусируются на problem solving interview (DataRobot, Ring Labs, Grammarly). Еще большая часть включают их в свой процесс собеседований как вспомогательные.
На определенном этапе развития компании ей понадобятся быстродействие, оптимизация и новые крутые фишки. А возможно ли придумать что-то новое, не зная и не понимая существующее? Ответ очевиден.
В некоторых компаниях среднего размера могут встречаться задачи, которые требуют точечной подготовки. Это возможно из-за конкретных требований проекта и ограничений в количестве набираемых кандидатов. Когда вы набираете 10 человек, а не 1000, тогда вы действительно хотите отобрать лучших из лучших.
Стартапы
Любой успешный стартап — это не только крутая идея, но и качественная реализация. В самом начале пути, когда пишется PoC (Proof of Concept), можно игнорировать и архитектуру, и оптимизацию. В таком случае при развитии и расширении стартапа придется выделить время на переписывание/ доработку/ рефакторинг.
Казалось бы, при чем здесь алгоритмы? Problem solving задачи развивают также умение быстро писать решение задачи, не задумываясь об архитектуре. И это часто то, что нужно для старта: написать «что-нибудь», что будет работать в кратчайшие сроки. Поэтому к «спортивным программистам» относятся с опаской. Да, они напишут для вашего продукта что угодно за минимальное время. Сможет ли этот код поддерживать кто-то другой? Ответ на этот вопрос размыт.
На этой волне можно вспомнить статью об украинском стартапе Looksery, который был основан людьми, связанными с олимпиадами. Они и набирали себе подобных: призеров и участников ACM ICPC (студенческая командная олимпиада), финалистов IOI (олимпиада для школьников), ребят с высоким рейтингом на CodeForces или TopCoder. Чем закончилась эта история, думаю, все осведомлены, или могут узнать по ссылке выше.
С другой стороны, собеседования в стартапы — самые непредсказуемые. Иногда это может быть и одно интервью об опыте и «чем хочешь заниматься», а после этого — офер. В другом случае, это может быть длительный процесс с 8+ интервью различной сложности.
Аутсорс
С аутсорсом все сложнее. Из всех типов компаний я меньше всего собеседовался в аутсорс, но общаясь с многими коллегами/ друзьями, которые работают в разного рода аутсорсинговых компаниях, можно сделать выводы.
Я ни разу не встречал людей, у которых спрашивали problem solving в аутсорсе. В маленьком /среднем/ крупном — не важно.
Связано это с тем, что аутсорсу нужно сразу бросить разработчика в бой. Им важно, чтобы он понимал язык, фреймворки, которые используются на проекте. Также кандидат должен пройти интервью с заказчиком, которому также не выгодно даже 2-4 недели обучать сотрудника. Добавим сюда большой процент legacy-кода, который не то что оптимизировать, а сложно поддерживать. В итоге получим интервью, которое тестирует вашу память, опыт, что угодно, но не умение решать задачи. К тому же, у крупного аутсорса есть свои академии, где готовят Trainee, Junior-позиции под себя. Им выгодно впихнуть в голову ученика пару фреймворков, чем пытаться научить его решать бесполезные на проекте задачи.
Если у Вас есть истории о прохождении problem solving interview в аутсорсе — поделитесь в комментариях. Будем надеяться на лучшее.
Использование алгоритмов в реальной разработке
За свою карьеру в различных компаниях в трех странах (США, Германия, Украина) я, так или иначе, сталкивался с алгоритмами. Иногда это неявное использование с применением стандартных библиотек, иногда — явная реализация. Даже обычное наследование — это, по сути, граф взаимосвязей между классами. Получается, что каждый день на работе программисты используют какой-то алгоритм или структуру данных. Хэш-таблицы, сортировка, алгоритмы поиска и другие популярные алгоритмы уже реализованы в большинстве популярных языках. И чем лучше понимание как эти алгоритмы реализованы внутри, тем легче будет найти эффективное применение и не встретить неожиданные баги, которые сложно отследить. Два моих любимых примера, которые встречались не один раз, это возгласы: «Почему так долго?» при использовании хэш-таблиц. И второй пример — это флейк тестов при использовании сортировки.
Типичный пример 1
Дано: длинные строки примерно такой структуры: «<время>. <много информации о том, что произошло в этот момент времени>» (структура может отличаться). Для каждой строки нужно посчитать какое-то значение. Например: сколько раз ее просматривали, редактировали и т.д.
Программист решает использовать стандартный dictionary, HashTable, unordered_set, в зависимости от языка. Но «под капотом» — это и есть хэш-таблица.
Код написан, тесты проходят, апрув получили — мерджим и запускаем в продакшн.
И на проде получаем, что запрос исполняется долго, обновление данных так вообще происходит пару минут. Программист в растерянности и панике.
В чем проблема?
В том, что теоретически получение значения по хэшу в среднем занимает константное время работы. Но получение этого хэша от строки — линейно. И с большими строками это работает крайне паршиво. Это если не говорить о коллизиях, которые также могут возникать. В худшем случае, получение значения по хэшу занимает линейное время от размера хэш-таблицы.
Что делать?
Все зависит от конкретной задачи. Самое простое исправление в примере выше — это хранить хэш только от времени (считаем его уникальным), а остальную строку, при необходимости, как значение по этому ключу вместе с остальной нужной информацией. Может быть, выгоднее даже хранить данные в отсортированном виде и проходиться по массиву двоичным поиском. Например, если строки очень длинные, но довольно уникальные. Главное, это понимать и знать, как работает то, что вы используете, какой алгоритм и структуру оптимально выбрать под ваш случай.
Типичный пример 2
Программист достает данные из таблицы, модифицирует их и возвращает клиенту в отсортированном виде. Сортировка производится по ключу, который прислал клиент в запросе.
На первый взгляд, все просто. Вытаскиваем нужные данные. Модифицируем. Сортируем стандартным сортом, в который передаем свой компаратор, ключ и т. д. Если нет необходимости модифицировать, то отсортируем на этапе запроса.
Тесты написаны, код уже давно в мастере. Об этой задаче давно забыли, добавили новые поля в таблицу, клиент присылает запросы с другими ключами — сервер работает как часы. В один прекрасный момент начинают не проходить тесты при проверке задач, которые никак не связаны с этим участком кода. Другие программисты жмут перезапуск тестов, и со второй-третьей попытки тесты проходят. Разработчик думает, что ему не повезло, и в этот момент возникли проблемы с базой, отвалился докер-контейнер или другой инструментарий. Но это начинает происходить все чаще и чаще на одном и том же тесте. Что произошло?
Сортировка во многих языках программирования не гарантирует стабильность. То есть запустив ее два раза на одном и том же наборе элементов, результат не гарантирует тот же порядок элементов. Таким образом, сформировав тест, который отсортирован по нужному ключу после сортировки, порядок других элементов с совпадающим ключом может быть другим. И сравнение двух таких массивов не сработает, но вам может повезти: ключи, по которым производится сортировка, уникальные, и обнаруживается ошибка спустя месяцы после написания кода.
Что делать?
Сортировать по двум ключам: ключу, который нужен, и уникальному в структуре данных. Например, ID элемента таблицы. Тогда каждый раз результат будет одинаковым.
Как итог, понимание, что Вы используете, поможет вам на таких этапах разработки:
Хочешь сделать хорошо — сделай это сам
К сожалению или к счастью, не все алгоритмы уже реализованы. Некоторые реализованные сложные алгоритмы требуют модификации или гибкости в использовании. Ниже приводятся некоторые примеры использования из жизни. Они будут видоизменены и немного упрощены для статьи. Но главные идеи и применения алгоритмов описаны.
Задача 1
Дано: набор пользователей, которые упорядочены по дате регистрации. Для группы людей, которые зарегистрировались в заданный временной промежуток, нужно уметь считать суммарное и максимальное количество взаимодействий с сервером.
Для этой задачи можно придумать большое количество решений в зависимости от вашей инфраструктуры, хранилища и других факторов. Одним из подходящих будет использование дерева отрезков (segment tree).
Количество пользователей — это величина, которая постоянно растет. К тому же, при большом количестве различных запросов даже на миллионе пользователей будут заметны потери скорости.
Дерево отрезков дает возможность обновлять данные за O(logN), получать показатели для последовательной группы людей тоже за О(logN). Да, нагрузка на память увеличилась за счет того, что нужно хранить два таких дерева (для максимума и для суммы), и они занимают в 4 раза больше места, чем массив с данными. Но в моем случае это было не критично.
Почему не использовать готовую реализацию?
Базовая версия пишется/ копируется менее чем за час. Настройка под себя же этой структуры данных из библиотеки потребовала больше ресурсов как для написания, так и для поддержания в будущем.
Планировалось, что могут потребоваться более сложные вещи вроде группового обновления данных. Например, при обнаружении подозрительной активности с аккаунтов, которые были зарегистрированы в одно время. Из доступных дополнений также возможны: получение порядковой статистики, сохранение предыдущих версий дерева.
Результат
Как я знаю от бывших коллег, это работает и модифицируется до сегодняшнего дня. Хотя было написано меньше чем за день (вместе с тестами). Если бы в команде никто не слышал о таком алгоритме, то на его поиски и реализацию ушли бы недели.
Задача 2
Люди работают в большой корпорации. Необходимо оптимизировать бизнес-процессы и документооборот. У каждого сотрудника есть своя нагрузка, количество необходимых утверждений (подписей) для дальнейшей обработки документа/ товара. Нужно максимизировать эффективность и минимизировать время обработки и затраченные ресурсы.
Решение
При решении схожей задачи у меня не было представления о линейной алгебре и транспортной задаче. Но я слышал об алгоритме Min Cost Max Flow.
По сути, каждого человека/ транспорт можно представить в виде вершины графа с показателями эффективности: количество обработанных единиц за время и затраты на них. Между вершинами есть последовательные взаимосвязи, которые известны.
С изменениями, но для решения этого применялся алгоритм поиска минимальной стоимости максимального потока.
Сомневаюсь, что данный алгоритм пригодится мне еще хоть один раз. Но он также интересен тем, что в базовом варианте объединяет три других: BFS, Форда-Фалкерсона и Белмана-Форда.
Результат
В свое время для меня это выглядело как шедевр. А в объединении с приятным UI, было еще и используемой вещью. Но проект завершил свое существование, а вместе с ним оборвалась жизнь и этого кода.
Задача 3. Разбор логов сервера
Дано: Файл логов 100 МБ+. Нужно наладить быстрый поиск по этому файлу. Слова и фразы поиска — это коды, тексты ошибок и ID пользователей (короткие строки).
Стандартные средства уже не удовлетворяли запросы проекта и нужно было придумать более быстрый способ. И снова помог алгоритм, который я видел до этого — Ахо-Корасик. Про результаты лучше всего расскажет график:
Результат
Это было не так давно, но есть подозрение, что эта реализация прослужит еще пару лет. Если инфраструктуру и процессы не изменят раньше.
Как я пришел к изучению алгоритмов и советы
Этот путь долгий и трудоемкий, особенно при совмещении с реальной работой. Но существуют ресурсы, которые помогают оптимизировать этот процесс.
При подготовке к прохождению интервью, два самых популярных ресурса это:
Существуют также ресурсы, которые предлагают обучение в более игровой форме. Например: Codewars или Code in game.
Если же вы захотите перейти на следующий уровень, изучать продвинутые алгоритмы и решать связанные с ними задачи, то стоит взглянуть на соревновательные сайты, такие как Topcoder, Codechef и другие.
А также абсолютно всем советую ознакомиться с книгой «Алгоритмы. Построение и анализ» Томаса Кормена. В ней подробно описаны большинство популярных алгоритмов. К тому же, книга написана понятным языком и легко читается, как в оригинале, так и в переводе.
Выводы
Сейчас в работе вы можете не нуждаться в алгоритмах. Например, если вы верстаете страницы, разрабатываете API и имеете сотни других рутинных задач.
Когда вы работаете с архитектурой, хайлоадом, базами данных, то знания алгоритмов и структур данных вам однозначно пригодятся. Невозможно заниматься 3D-моделированием, машинным обучением, IoT-разработкой, не погружаясь в детали и нюансы алгоритмики. Любая отрасль, где нужна оптимизация памяти или времени, требует этого. Они помогут вам и в выборе архитектуры. Вы не сможете выбрать графовую базу данных для своего проекта, если не знаете, что такое граф.
Конечно, для начинающих разработчиков, которые хотят в кратчайшие сроки найти свою первую работу, лучшим вариантом будет выучить один язык и несколько фреймворков, и с третьего, пятого, двадцатого собеседования вы ее найдете. При продвижении в карьере, алгоритмы вам точно пригодятся.
Опытным разработчикам, которым на текущий момент не нужны знания подобного характера, могу сказать только одно: фундаментальные знания помогут вам найти более интересный проект, где нужно будет писать новый функционал, а не поддерживать и тащить на себе старый. Небольшая часть разработчиков в восторге от legacy-кода. А может вы узнаете о какой-то интересной для вас задаче и сможете улучшить существующее решение, создать свой продукт на его основе.
Разбираемся в алгоритмах и структурах данных. Доступно и понятно
Представляем вам отличную статью Адама Леоса, опубликованную на DOU.UA. В этой статье автор доступным языком объясняет алгоритмы, их сложность и структуры данных.
Всем привет. Меня зовут Адам Леос, и я Senior Software Engineer в PlutoTV. Кроме основной работы, я активно участвую в развитии IT-сферы и повышении уровня разработчиков в целом. Например, я принимаю участие в хакатонах (как участник и как судья), пишу технические статьи, провожу вебинары и выступаю с докладами как приглашенный технический специалист в компаниях и как спикер на конференциях.
Темы для своих презентаций я подбираю так, чтобы это был не пиар себя/компании/технологии, а чтобы материал привнес что-то нужное, был полезен разработчику (желательно непосредственно сразу). Одна из таких тем — необходимость знания алгоритмов и структур данных. По определенным причинам среди разработчиков из стран СНГ бытует мнение, что эти знания не нужны и не важны. Спойлер! Это не так.
Для кого предназначена эта статья? Она будет полезна каждому, кто желает добиться одной (или нескольких, можно всех) из следующих целей:
И совершенно не важно, какого вы уровня разработчик или каким направлением занимаетесь. Материал будет одинаково полезен как начинающим свой путь в разработке, так и опытным техническим лидерам.
Статья будет базироваться на двух тезисах (и опровергать их):
Сложность алгоритма
Чтобы определять эффективность/неэффективность какого-либо кода и понимать, что и как мы можем улучшить, нам необходимо ввести единственное понятие, которое будет использоваться в статье. Это сложность алгоритма, то есть то, как будет расти расход ресурсов с увеличением размера входных данных. Сейчас мы проработаем это определение с разных сторон и приведем несколько примеров.
Теперь взглянем на синтетический пример (мы будем начинать с очень простых вещей и постепенно усложнять, в то же время переходя от синтетических примеров к реальной жизни). В этом примере будем читать сумму всех чисел в переданном массиве.
Здесь мы получили массив, объявили переменную-сумму, изначально равную 0, и запустили итерацию по массиву, беря каждый элемент массива и добавляя его к сумме. Все просто. Теперь давайте проанализируем: что будет, если мы вызовем эту функцию с массивом из пяти чисел [1, 2, 3, 4, 5]? Очевидно, мы сделаем пять итераций — за каждый элемент в массиве, чтобы взять его и добавить к сумме. А что, если массив будет состоять из десяти чисел? Логично, что потребуется десять итераций.
Паттерн очевиден: чем длиннее массив мы передаем, тем больше итераций мы делаем (соответственно, больше времени тратим на выполнение). Только что мы выразили сложность алгоритма, и, вспомнив определение выше (как будет расти расход ресурсов с увеличением размера входных данных), мы увидим, как же рос расход ресурсов в нашем случае (расход времени — делали больше итераций) с увеличением размера входных данных (массива-инпута). Так, у нашего алгоритма сейчас линейная зависимость от входных данных: за каждый элемент массива мы делаем дополнительную итерацию.
Нотация Big O
Лучше всего зависимости можно увидеть на графиках, и для описания таких зависимостей существует нотация Big O (это те самые O(n), O(log n) и прочие, которые мы рассмотрим чуть дальше). Если выразить, что это такое, одним предложением, то это будет звучать так: функция, которая описывает рост сложности алгоритма. Что за сложность алгоритма и как она может расти, мы примерно себе представили. Big O — это функция, которая этот рост описывает. Единственное уточнение: функция фигурирует здесь в математическом смысле, то есть как функция, которая используется для построения графика.
Давайте возьмем наш синтетический код из примера выше и построим график зависимости размера входных данных от количества итераций. По оси X (горизонтальной) мы возьмем рост входных данных от 0 до какого-то конечного числа n. Основными точками пускай будут 1, 100, 1000 и 10 000 единиц (элементов в массиве). По оси Y (вертикальной) будет рост количества операций также от 0 вверх с основными точками в 1, 100, 1000, 10 000 операций. Остается только провести линию по зависимости, что была у нас в алгоритме.
Как вы помните, на каждый элемент в массиве нам необходимо сделать дополнительную операцию сложения. Значит, если нам пришло 100 элементов, делаем 100 операций. Приходит 10 000 элементов — делаем 10 000 операций. Приходит n элементов — делаем n операций. Вот и та самая n в сложности O(n), которая также называется линейной. Все очень просто.
Здесь все классно, но надо посмотреть с разных сторон и на других примерах, чтобы закрепить. Рассмотрим новый пример простойПосчитать (simpleCalculate). Мы ничего не принимаем и выполняем какие-то операции: вычисляем переменные, выводим что-то в консоль (просто чтобы было больше операций) и возвращаем разницу.
Сложность такого алгоритма O(1) — постоянная, или константная. Здесь тоже все примитивно: наш алгоритм вообще ничего не принимает, поэтому никак не зависит от входных данных. Соответственно, даже если бы по какой-то причине в него передавали различные значения, он бы постоянно выполнял одни и те же операции, никак не увеличивая и не уменьшая расход ресурсов, поэтому сложность постоянная. На графике это показано еще доступнее:
Как видно на графике, у нас просто прямая линия: количество операций не растет и постоянно при любых значениях входных данных. Единственный важный для понимания момент здесь — в обозначении сложности O(1). Единица не указывает на количество операций и не будет меняться на другие числа, если алгоритм будет выполнять больше операций (как минимум наш алгоритм тоже выполняет больше операций). Единица здесь, так же, как и n в O(n), — это специальное обозначение, в этом случае константной сложности, и все.
А что случится, если мы будем принимать число как аргумент функции и добавлять его к нашей разнице? Какая сложность следующего кода?
Сложность этого алгоритма также будет O(1). Несмотря на то что мы уже принимаем аргумент и используем его, все, что мы делаем, — одну дополнительную операцию по сложению. Какое бы большое, маленькое, дробное или отрицательное число ни было, мы всегда просто берем его и складываем одной операцией (естественно, при условии, что оно помещается в память, но это уже совсем другая история), то есть количество операций постоянно и не зависит от инпута.
Ну хорошо, а когда же зависимость появится? Проще всего будет показать при использовании массива, если бы мы принимали массив чисел и в конце вычисляли дополнительное число для сложения, итерируя по массиву.
Здесь-то у нас уже появляется снова линейная зависимость от размера входных данных, знакомая нам по первому примеру. Больше массив — больше операций мы делаем для вычисления дополнительного слагаемого. Помните сложность такого алгоритма? O(n).
Отлично, сейчас многим может показаться, что они раскусили систему: если входные данные — это массив, то сложность всегда линейная, О(n), и думать здесь нечего. Но мы можем посмотреть на такую версию предыдущего кода.
В этот раз, все еще принимая массив аргументов, мы просто берем его длину как дополнительное число для сложения. А получение длины массива, хранящейся в отдельном свойстве, — мгновенная (та же константная) операция. Поэтому какой бы большой массив мы сюда ни передали, мы всегда будем мгновенно получать его длину и одной операцией добавлять к разнице. Итого это константная сложность, O(1).
Дальше у нас будет такой пример. Допустим, у нас есть массив чисел, и мы хотим все числа сложить со всеми — для этого у нас будет двойной вложенный цикл.
Сложность такого алгоритма уже значительно выше, за каждый элемент массива нам нужно сделать полную итерацию по массиву. То есть, имея лишь массив из пяти элементов [1, 2, 3, 4, 5], мы проделаем 25 операций. Применив простейшую математику, мы можем прийти к тому, что нам требуется квадрат операций на наш размер входных данных. Эта сложность называется квадратичной и обозначается О(n^2). График демонстрирует резко растущий расход ресурсов такого алгоритма.
И если с вложенными циклами это очевидно, то здесь разработчика может поджидать резкое увеличение сложности, казалось бы, на ровном месте.
Как вы уже догадались, сложность такого алгоритма — O(n^2). По сути, здесь присутствует тот же вложенный цикл. Реализация метода indexOf под капотом — это обычный цикл, обход массива: так как индексы каждого элемента в массиве не хранятся, то его надо найти. Само собой, опытный разработчик об этом знает. Правда, если при этом опытный разработчик не знает алгоритмов, то, скорее всего, он этот код так и оставит. К слову, оптимизация здесь была бы суперпростой. В методе forEach второй аргумент — это индекс итерируемого элемента, и легким движением руки квадратичная сложность превращается в линейную, потенциально сохраняя нам большое количество ресурсов на выполнение.
Последним важным моментом по этому разделу будет упоминание того, что нотация Big O указывает на самую быстрорастущую сложность алгоритма и игнорирует константные оптимизации. Давайте дополним наш пример с вложенными циклами еще одним линейным циклом:
Сложность этого алгоритма будет не O(n + n^2), а просто квадратичная, O(n^2) — как раз потому, что квадрат будет расти несоизмеримо быстрее, делая влияние линейной сложности нерелевантной.
Пример роста в цифрах
Чтобы увидеть разницу, полезно взглянуть на сравнение количества операций в зависимости от сложности с одинаковыми размерами входных данных. Давайте смоделируем ситуацию, когда у нас на вход приходит массив с 10 000 (десятью тысячами) элементов, и определим, сколько операций проделают разные сложности:
Есть еще хорошая картинка, на которой графики различных сложностей расположены друг рядом с другом. На ней наглядно показаны различия:
Несколько полезных комментариев к картинке:
Структуры данных
Прежде чем мы перейдем к примерам из реальной жизни, нам необходимо разобраться в двух самых популярных структурах данных, которые позволят применять различные эффективные оптимизации (а после этого будут и более сложные, но очень интересные структуры данных).
Прежде всего, давайте выразим, что такое структуры данных. Как и до этого, сделаем это в одном предложении: это определенный способ организации данных для максимально эффективного использования. Ничего сложного… У нас есть данные, которыми мы постоянно оперируем, и мы хотим их как-то организовать, чтобы затем эффективно использовать (оперировать).
Какие основные операции мы проворачиваем с данными? Все задачи в основном сводятся к следующим операциям:
И для всего этого у нас есть множество разнообразных структур данных, которые в чем-то лучше (более эффективные), а в чем-то хуже (менее эффективны), чем другие. На картинке ниже наглядно продемонстрированы некоторые структуры данных и то, с какими сложностями они связаны для каждой из четырех операций.
От разработчика требуется понимание, что есть разные структуры с разной эффективностью для разных задач. И знание структур данных подразумевает просто грамотное использование самой подходящей (максимально эффективной) структуры для решения какой-либо задачи. Надо часто искать? Берете это. Часто что-то вставляете? Берете другое. Приходится переставлять и удалять? Берете третье.
Дальше давайте поговорим о самых ярких представителях жанра в ежедневной разработке и об их грамотном использовании.
Массивы
Самой первой и, возможно, самой популярной структурой будут массивы. Давайте взглянем на основные манипуляции, которые мы производим с массивами, и проанализируем сложность. Вот есть у нас массив:
Что мы можем с ним делать? Очевидно, получить какой-то из элементов по индексу.
Как считаете, какова сложность этой операции? Кто предположил (или знал), что это O(1), оказался прав. Мы можем мгновенно по уникальному идентификатору (индексу) получить любой элемент массива (даже которого там нет, просто получим undefined). Так же можно и записывать по индексу.
Так делать (обычно) все же не стоит, ибо это чревато последствиями: можно получить «дырки» в массиве и прочие радости мутаций. Но это уже другая тема.
Ладно, давайте о методах: например, добавление элемента в конец массива.
Сложность такой операции будет O(1).
Примечание. Добавление элемента в конец списка в JavaScript — константная операция, только не обычная, а «амортизированная». Что это значит? В JS мы не управляем памятью напрямую, но в языках программирования, где мы ей управляем, создание массива под наши нужды будет немного отличаться. Нам будет необходимо выделить память под массив определенного размера. То есть выделив память на массив длиной в 20 элементов и захотев добавить 21-й, мы будем вынуждены выделять еще память, что является О(n)-операцией. Несмотря на то что мы не делаем такого в JavaScript, это происходит «под капотом». И хотя преимущественно мы будем вставлять элементы в О(1), иногда могут быть «скачки», когда под наш новый элемент выделяется больше памяти. Так что эта операция как бы константная, но амортизированная.
Что у нас с удалением с конца массива?
Здесь мы имеем также O(1). Хорошо, а что с задачами добавления и удаления с начала массива?
Как многие знают (или догадались по подводке), здесь мы имеем другую картину. Вставка и удаление элемента с начала списка имеют сложность О(n). Все потому, что, манипулируя элементами в начале списка, мы должны обновить индексы всех последующих элементов. Если произошло удаление, то элемент, который был вторым, должен стать первым, вторым станет третий и т. д. То же самое происходит при вставке в начало: требуется обновить индексы всех последующих элементов.
Это, как вы сами видите, значительно менее эффективно. Именно поэтому разнообразные реализации стеков (stack) базируются на push & pop, а не на unshift & shift. Немного о стеках. Представьте стопку документов на подпись: тот, что лежит сверху, и берем первым для подписи. Если мы что-то добавляем, то кладем поверх всех, и он становится первым для следующей подписи. Это еще называется LIFO — last in, first out (последним вошел — первым вышел). Самым популярным применением в программировании будут разнообразные стеки операций: например, стек изменений в редакторе кода, чтобы иметь возможность быстро отменять изменения и возвращаться к предыдущим состояниям, или стек передвижения по страницам в браузере, чтобы быстро переходить по страницам.
Напоследок обязательно стоит упомянуть другие методы работы с массивами, которые имеют О(n)-сложность (как в примере с indexOf). Это будут практически все методы по работе с массивами — все, где мы что-то фильтруем, ищем, перебираем, переворачиваем и даже превращаем в строку (toString) — все это имеет O(n)-сложность.
Объекты
Вторая по популярности структура — объекты. Они используются для удобного хранения с возможностью быстрого манипулирования данными. Прежде чем мы взглянем на примеры, быстро рассмотрим операции. Их не много, и они помогут лучше понять последующие идеи и их преимущества.
Так выглядит обычный объект. Мы можем получить любое из его свойств по «имени свойства», являющегося уникальным идентификатором. Это будет мгновенная операция вне зависимости от способа.
Точно так же мы можем произвести перезапись свойства или даже записать новое, все будет константной операцией.
Еще мы можем запросить все ключи или все значения объекта. Для этого существуют специальные методы, возвращающие нам массив значений.
Как вы можете догадаться, сложность этих методов — О(n): надо пройти по всем значениям, создавая из них массив.
Именно благодаря тому, что каждое свойство объекта — уникальный идентификатор и по этому уникальному ID мы можем мгновенно получать, записывать, удалять и обновлять данные, объекты часто используются как вспомогательная структура для многих оптимизаций через маппинг. Для многих это может быть знакомо по аналогам из других языков: словарю (dictionary) или «карте» (map). К слову, в ES2015 в JS тоже добавили объект Map — как раз для такого использования. Кто не знаком, он предоставляет методы для всех тех манипуляций, которые мы проводили раньше с объектом, имитируя Map. Например:
Теперь давайте взглянем на применение. Начнем с решения очень популярной на собеседованиях задачи (например, ее устное решение спрашивали у меня в Microsoft). Задача — посчитать количество уникальных символов в строке. Решение тривиально и работает с любыми символами:
Результатом вызова с какой-либо строкой будет карта по уникальным символам и их количеству:
То есть мы создали карту и заполнили символами из строки, где каждый символ — уникальный идентификатор. Так мы могли мгновенно проверить его наличие в карте, получить значение и перезаписать его. И это работало для любого символа любого языка, специальных символов и даже пробелов. В общем, идею маппинга вы уловили: это создание вспомогательной структуры для определенных операций за О(1). Теперь давайте перейдем к их применению в реальной жизни.
Полезный маппинг в реальном мире
Здесь я хотел бы привести один из примеров, где я применял это в одной из предыдущих компаний. Почему именно его? Потому что это очень наглядная демонстрация ситуации, когда незнание алгоритмов и их сложности ведет к огромному падению производительности на ровном месте при приличном, на первый взгляд, коде. Здесь четко показано, как можно при минимальных усилиях (за полчаса) получить большой прирост производительности (почти в 100 раз).
Краткое описание проекта: делал я как-то видеостриминговое приложение на ReactJS + Node.js для альтернативных платформ типа Smart TV и игровых приставок.
Была там одна задача, которую решили еще до моего прихода на проект. Ситуация была следующая. У нас в приложении есть тысячи шоу: какие-то сериалы, фильмы — весь видеоконтент приложения со следующей структурой (все упрощено и переименовано в угоду простоте восприятия и для удовлетворения NDA, все совпадения случайны):
То есть массив из множества объектов, представляющий отдельное шоу и хранящий информацию по этому шоу, — стандартные ID, name и прочее.
Ну и в каких-то моментах мы получаем другой массив «забаненных» шоу. По определенным причинам мы не хотим показывать это шоу пользователю: конкретно что-то с пользователем, или канал сегодня решил не показывать это, или вообще там проблемы с транслированием именно на этом канале именно для этого пользователя и прочие мутные бизнес-причины. У нас есть массив других объектов, хранящих немного информации, достаточной для бана каких-то шоу «на месте».
И вот код, как это было решено:
Что здесь происходит? Начинается цикл по всем шоу, берется ID каждого из этих шоу и запускается обход забаненных шоу с целью найти совпадения. Если совпадение есть, шоу должно быть забанено (условно помечаем флагом isBanned).
Чей-то опытный глаз уже мог заметить проблему (и возможно, нервно задергаться). Вообще, здесь совершается слишком много ненужных операций: мы для каждого шоу запускаем итерацию по забаненным, это очень большая и лишняя нагрузка. А ведь оптимизируется это очень легко, нам нужна лишь карта забаненных ID, с помощью которой мы бы могли мгновенно проверять, забанено шоу или нет. Реализовать это можно как с помощью обычных объектов, так и с помощью Map или даже Set (Set — это просто набор, то есть оперируем как с Map, только никаких значений записям не присваиваем, просто добавляем уникальные ключи, чтобы они были в наборе, и выполняем мгновенные проверки на их наличие):
Что изменилось: мы вынесли вложенный цикл итерирования по забаненным шоу наружу и проходим по нему всего один раз для заполнения нашего Set, который будет набором всех забаненных ID с возможностью мгновенно проверять, есть ли там определенная запись. В итоге мы не запускаем множество ненужных циклов внутри обхода всех шоу, а делаем лишь мгновенную проверку на наличие итерируемого шоу в списке (Set) забаненных. И если совпадение есть, то шоу должно быть помечено как забаненное.
Это можно реализовать как еще короче, так и более развернуто и доступно. Можно использовать объект вместо Set и просто делать запись в объект, где ключом будет тот же уникальный ID забаненного шоу, а значением — что угодно, то же булево true. И затем для проверки, забанено ли итерируемое шоу, достаточно «постучаться» в объект по ID, и мы получим либо true, что будет значить, что шоу надо банить, либо undefined, а значит, шоу в забаненных нет, пропускаем.
Отлично. Если с оптимизацией времени вроде бы все понятно (делай меньше операций, опирайся на сложность, и будет тебе благо), то что же с памятью?
Память в реальном мире
А с памятью все тоже просто (хоть и менее прозрачно). В качестве примера я буду использовать оптимизацию, которую я сделал уже на текущем проекте в PlutoTV (тоже видеостриминговое приложение на React под телевизоры и приставки).
Был вот такой красивый и функциональный код:
Здесь получали какой-то ответ с каналами и прочим и как-то подгоняли под свои нужды: фильтровали, что-то добавляли, что-то удаляли, что-то перемещали. Сделано это изящной и грамотной цепочкой с отдельным методом под каждую операцию.
Кто уже увидел проблему для памяти? Что делают методы filter и map? Возвращают новый массив, под который необходимо выделить память, возможно, много (возможно, непозволительно много для некоторых платформ). А существует этот массив лишь для того, чтобы по нему запустить новый цикл и провернуть другую операцию с теми же элементами, что и в предыдущем цикле. Какое расточительство памяти на ровном месте!
Исправить это можно очень просто, заменив все на один обход. Например, с помощью reduce:
Идея, как видите, очень проста. Мы имеем один reduce (можно даже заменить фильтрацию, просто не наполняя аккумулятор по условию). Естественно, можно записать как короче, так и размашистее, кто как любит. Суть в том, что мы не выделяем кучу памяти под новые массивы, которые даже толком не используем. Эта маленькая оптимизация позволила сохранить от 10% до 30% расхода памяти приложения в зависимости от старины девайса. Что очень много: 30% для одного места, когда все приложение еще должно где-то работать.
Сортировки
Еще очень полезно будет разобраться с сортировками. Сразу скажу, что необходимость реализовывать какую-то свою уникальную сортировку у вас будет появляться крайне редко (а то и вовсе не случится за всю карьеру), так как в каждом языке программирования присутствуют довольно хорошо оптимизированные методы сортировки (отличным примером будут оптимизации array.sort() в JavaScript, которые мы обязательно разберем дальше). Но сортировки вне зависимости от необходимости их реализовывать — это очень классный пример алгоритмов и балансировки между расходами времени и памяти. Так что давайте взглянем на две самые популярные сортировки с очень разными расходами ресурсов.
Первым делом мы посмотрим на знакомую многим сортировку пузырьком (Bubble Sort). Идея этой сортировки в том, чтобы, проходя по массиву, находить самый большой элемент и «протаскивать» его до конца массива. Очевидно, чтобы отсортировать таким образом, когда за один обход мы дотаскиваем только один самый большой элемент, нам потребуется n обходов массива (где n — длина массива). А когда нам необходимо сделать n обходов, каждый из которых заключается в полном обходе массива, это O(n^2)-сложность. Ну вы и сами уже знаете.
Давайте посмотрим на визуализацию, а затем погрузимся в реализацию.
Как вы увидели, суть протаскивания примитивна: это прохождение по массиву, определение текущего и последующего элементов и их сравнение. Если левый больше правого, меняем их местами и берем следующий. Таким образом, мы либо постоянно двигаем самый большой элемент вправо, пока не доведем до конца массива, либо же, наткнувшись на больший элемент, чем текущий, просто идем дальше и оперируем теперь новым самым большим.
В коде все будет тоже очень просто.
Бесполезна ли эта сортировка, имеющая аж квадратичную сложность, когда есть более быстрые универсальные сортировки? Отнюдь. Как мы могли наблюдать, у сортировки пузырьком (как и у подобных ей, типа сортировки вставками) есть одно довольно важное преимущество — расход памяти. Здесь нам требуется лишь одна вспомогательная переменная для смены мест двух элементов, то есть константная сложность по памяти. Это огромная разница по сравнению со следующей быстрой универсальной сортировкой — сортировкой слиянием. Давайте взглянем на нее.
С первого раза непросто понять, что происходит, но мы сейчас все проработаем. Идея сортировки слиянием состоит в том, чтобы разбивать массив пополам на пару новых массивов (и каждую половинку снова пополам, и те тоже пополам), пока у нас не получатся массивы, состоящие лишь из одного элемента. Затем мы начинаем сливать их обратно в единый массив попарно, как и разбивали. Таким образом, мы можем очень быстро наполнять массив, на месте же его и сортируя, просто принимая решение, какой из элементов на каждом этапе вставлять (то есть вставляем все время меньший элемент и получаем отсортированный по возрастанию массив).
Благодаря постоянной разбивке пополам и попарному слиянию сложность этой сортировки — O(n * log n), то есть длина массива (надо как минимум раз полностью пройти по массиву), умноженная на логарифм от длины (сложность постоянного деления пополам). Сейчас взглянем на код и на еще одну визуализацию, и все должно стать понятно.
Здесь основной код, который будет в то же время использоваться рекурсивно, для разбивки массива пополам и сортировки этих двух половин. (Сам метод сортировки разберем немного позже).
Посмотрим на еще одну визуализацию, на которой хорошо видно, как массивы разбиваются и затем попарно сливаются обратно. Сразу после визуализации перейдем к методу merge.
В чем будет заключаться наша логика слияния? У нас приходят два массива: левый и правый. Оба либо уже отсортированы (см. логику выше), либо просто состоят из одного элемента. Теперь нам нужно начать обход по обоим (достаточно одного обхода с двумя указателями: первый указывает на итерируемый элемент левого массива, второй — на итерируемый элемент правого массива) и брать меньший из двух элементов, закидывая его в новый массив, который мы вернем как отсортированный.
Думаю, здесь уже все ясно. Последним моментом будет то, что нам достаточно пройти до конца хотя бы один массив, потому что все оставшиеся непройденные числа будут точно больше, их надо просто добавить в конец нашего отсортированного массива. (Это происходит в конце кода, где мы сливаем остатки методом concat.)
Сейчас вы и сами видите, что более быстрая сортировка требует значительно больше памяти (выделяется большое количество памяти под все эти новые массивы, которое не идет ни в какое сравнение с константным расходом сортировки пузырьком).
Так что теперь мы можем качественно понять, что за оптимизации скрыты под капотом у array.sort(). Несмотря на то что имплементации могут отличаться от браузера к браузеру (и даже от версии к версии), глобальная идея заключается в том, чтобы использовать сортировку слиянием и быструю сортировку (также O(n * log n)) в зависимости от типа данных в массиве. Но массив не разбивается на подмассивы до одного элемента, как в нашей реализации. Вместо этого разбивание останавливается на 10 элементах, и уже к этим массивам из 10 элементов применяется сортировка вставками (аналог пузырьковой, O(n^2)). И лишь после этого начинается алгоритм слияния / быстрой сортировки. Таким образом, экономится очень много памяти (не создается целая куча лишних массивов) и практически нет проигрыша по быстродействию (сортировка вставками довольно эффективна на небольших массивах). Вот и чудесный пример балансировки между быстродействием и расходом памяти.
Важное послесловие о сортировках: я не просто так несколько раз писал, что сортировка слиянием и быстрая сортировка — это лучшие универсальные сортировки. То есть они будут стабильно хорошо работать в любых ситуациях с любыми данными (естественно, в пределах разумного). Хотя да, существуют разные сортировки со сложностью лучше, чем O(n * log n): например, radix sort. Но их применение специфично и не является универсальным. Хотя такие сортировки, само собой, широко применяются, просто они эффективны в конкретных ситуациях.
Выводы
Полезные материалы
Материал тесно перекликается с моими выступлениями, поэтому также рекомендую посмотреть видеозапись выступления (презентация в Казахстане на русском). Также я очень хотел бы еще рассказать о графах, деревьях, поиске и прочих интересных и важных моментах, но это увеличит объем текущей статьи минимум в три раза, поэтому поговорим о них отдельно в следующей публикации.