Оцениваем сложность алгоритмов на C# по памяти и времени с примерами |
||
МЕНЮ Главная страница Поиск Регистрация на сайте Помощь проекту Архив новостей ТЕМЫ Новости ИИ Голосовой помощник Разработка ИИГородские сумасшедшие ИИ в медицине ИИ проекты Искусственные нейросети Искусственный интеллект Слежка за людьми Угроза ИИ ИИ теория Внедрение ИИКомпьютерные науки Машинное обуч. (Ошибки) Машинное обучение Машинный перевод Нейронные сети начинающим Психология ИИ Реализация ИИ Реализация нейросетей Создание беспилотных авто Трезво про ИИ Философия ИИ Big data Работа разума и сознаниеМодель мозгаРобототехника, БПЛАТрансгуманизмОбработка текстаТеория эволюцииДополненная реальностьЖелезоКиберугрозыНаучный мирИТ индустрияРазработка ПОТеория информацииМатематикаЦифровая экономика
Генетические алгоритмы Капсульные нейросети Основы нейронных сетей Распознавание лиц Распознавание образов Распознавание речи Творчество ИИ Техническое зрение Чат-боты Авторизация |
2024-04-19 16:07 Продолжаем говорить о производительности и оптимизации кода. Сегодня поговорим о том, как и зачем оценивать сложность алгоритмов, а также наглядно покажем, как эта сложность влияет на производительность кода. В прошлой статье мы разбирались, что такое бенчмаркинг кода и как с его помощью оценивать производительность кода в .NET. В этой – поговорим про оценку сложности алгоритмов. А чтобы все было наглядно, вместе попробуем оценить алгоритмы, которые используются для решения задачки на собеседовании в Google. Задач такого плана полным-полно на платформах типа LeetCode, CodeWars и других. И их ценность не в том, чтобы заучить различные алгоритмы сортировок, которые вы никогда не будете на практике писать самостоятельно, а в том, чтоб увидеть типичные проблемы, с которыми вы можете столкнуться в практических задачах при разработке. Оценка сложности алгоритмов Зачем вообще оценивать сложность алгоритмов и какие способы оценки бывают? Понимать сложность алгоритмов важно по следующим причинам:
Для каждого алгоритма можно сделать несколько оценок сложности: O большое (O(f)) — позволяет оценить верхнюю границу сложности алгоритмов. Это отношение количества входных данных для алгоритма ко времени, за которое алгоритм сможет их обработать. Простыми словами – это максимальное время работы алгоритма при работе с большими объемами данных. Омега (?(f)) — позволяет оценить нижнюю границу сложности — сколько времени займет работа алгоритма в лучшем случае. Тета (?(f)) —позволяет получить “плотную” оценку сложности, то есть такую, при которой скорость работы в худшем и лучшем случае будет пропорциональна одной функции. Применимо не ко всем алгоритмам.
В скобках после О указывают функцию, которая ограничивает сложность. При этом n — это размер входных данных. Например, O(n) означает, что сложность алгоритма растёт линейно. В таком случае время выполнения алгоритма увеличивается прямо пропорционально размеру входных данных. Если представить график распространенных сложностей алгоритмов, они будут выглядеть вот так: Если условно разделить сложности на зоны, то сложности вида O(log n), O(1) или O(C) можно будет отнести к зоне «Отлично». Такие алгоритмы вне зависимости от объемов данных будут выполняться очень быстро — практически мгновенно. Алгоритмы сложности O(n) можно отнести к зоне «Средне» — алгоритмам, сложность которых растет предсказуемо и линейно. Например, если 100 элементов ваш алгоритм обрабатывает за 10 секунд, то 1000 он обработает примерно за 100 секунд. Не лучший результат, но предсказуемый. Алгоритмы из красной зоны со сложностями и выше трудно отнести к высокопроизводительным. НО! тут все сильно зависит от объемов входных данных. Если вы уверены, что у вас всегда будет небольшой объем данных (например, 100 элементов), и обрабатываться он будет в приемлемое для вас время, то все в порядке, такие алгоритмы тоже можно использовать. Но если же вы не уверены в постоянности объемов данных (может прийти и 10 000 элементов вместо 100) — лучше все-таки задуматься над оптимизацией алгоритмов. Добавим, что оценка сложности по времени — это теоретическая оценка. Она не учитывает внутренние оптимизации и кеш процессора, в реальности картина может отличаться. Оценка сложности по памяти Оценку сложности алгоритмов следует проводить не только по времени выполнения, но и по потребляемой памяти — часто про это забывают во время изучения темы. Например, для ускорения вычислений можно создать какую-нибудь промежуточную структуру данных типа массива или стека для ускорения алгоритма и кеширования результатов. Это приведет к дополнительным затратам памяти, но при этом может существенно ускорить вычисления.
Важно отметить, что при оценке сложности алгоритмов по памяти используют упрощенную модель работы с памятью, так называемою RAM-машину. Это означает, что мы можем читать и записывать любую ячейку памяти за время одной операции. Таким образом, время вычислительных операций и операций с памятью становится одинаковым, что упрощает анализ. Это ближе всего к работе с оперативной памятью, и, например, не учитывает регистры процессора, работу с диском, garbage collector и много чего еще. Немного практики: правила расчета сложности на пальцах Мы приводим примеры на C#, хотя здесь можно было бы обойтись и псевдокодом. Надеемся, что они будут понятны. Пример 1: Возьмем для начала простой алгоритм присвоения переменной: Какова его сложность по времени и по памяти? С одной стороны, нас может ввести в заблуждение массив данных data неизвестной размерности. Но брать его в расчет при оценке сложности внутреннего алгоритма будет некорректно. Правило 1: внешние данные не учитываются в сложности алгоритма. Получается, наш алгоритм состоит только из одной строчки: var a = data[target]; Доступ к элементу массива по индексу — известная операция со сложностью O(1) или O(C). Соответственно, и весь алгоритм по времени у нас займет O(1).
Пример 2: Рассмотрим второй алгоритм, очень похожий на первый: Влияет ли размерность входного массива data на количество операций в нем? Нет. А на выделенную память? - Тоже нет. Сложность этого алгоритма по времени выполнения можно было бы оценить как O(2*C) — поскольку у нас выполняется в два раза больше операций, чем в предыдущем примере, 2 присваивания вместо 1. Но у нас и на этот счет есть правило: Правило 2: опускать константные множители, если они не влияют на результат кардинальным образом. Если принять это правило в расчет, сложность этого алгоритма будет такой же, как и в первом примере — O(C) по времени и O(C) по памяти. Пример 3: В третьем примере добавим в наш алгоритм цикл для обработки данных: Как мы видим, количество операций, которые будет выполнять цикл, напрямую зависит от количества входных данных: больше элементов в data — больше циклов обработки потребуется для получения финального результата. Казалось бы, если взять в учет каждую строчку кода нашего алгоритма, то получилось бы что-то такое: И тогда финальная сложность алгоритма получится O(C)+O(n). Но тут опять вмешивается новое правило: Правило 3: опускать элементы оценки, которые меньше максимальной сложности алгоритма. Поясню: если у вас O(C)+O(n), результирующая сложность будет O(n), поскольку. O(n) будет расти всегда быстрее, чем O(C). Еще один пример — . При такой сложности у нас n2 всегда растет быстрее, чем N, а значит O(n) мы отбрасываем и остается только . Итак, сложность нашего третьего примера — O(n). По памяти без изменений — О(С). Пример 4: В четвертом примере посчитаем сумму всех возможных пар значений из массива: И для его обработки нам теперь нужно два цикла. Оба этих цикла будут зависеть от размерности входных данных data. Правило 4: вложенные сложности перемножаются. Сложность внешнего цикла в нашем примере — O(n), сложность внутреннего цикла — O(n). Согласно правилу, две эти сложности должны быть умножены. В результате максимальная сложность всего алгоритма выйдет равной . По памяти без изменений — О(С). Пример с подвохом: Подадим на вход двумерный массив и посчитаем сумму значений. Снова видим вложенные циклы — и если во входном массиве N x M элементов, то есть сложность O(N * M), и кажется, что это эквивалентно . Но на самом деле, нет — в данном случае на вход просто подается N * M элементов и время пропорционально N * M, то линейное O(n). Пример 5: А что мы видим тут? Цикл — уже известная нам сложность – O(n). Но внутри вызывается функция Если мы вспомним ее сложность , а также правило 4, то получим, что сложность этого алгоритма — при всей его визуальной минималистичности. Со сложностью по времени без изменений. Правило 5: включайте в оценку общей сложности алгоритма оценки всех вложенных вызовов функций. Именно поэтому важно понимать сложность методов синтаксического сахара вроде LINQ, базовых коллекций и типов данных — чтоб была возможность оценить, как метод будет вести себя при увеличении объемов данных. При использовании их в коде без понимания внутреннего устройства, вы рискуете получить очень высокую сложность алгоритма, который будет захлебываться при увеличении входящих данных. Приведу пример минималистичного алгоритма, который выглядит хорошо и компактно (ни в коем случае не претендует на эталонный код), но станет бомбой замедленного действия при работе с большими объемами данных: Что мы тут видим? Цикл = O(n), Where = O(n), Contains = O(n), так как newArr – это массив. Итого сложность такого алгоритма будет от по времени выполнения. ToArray() будет выделять на каждой итерации дополнительную память под копию массива, а значит сложность по памяти составит O(n). Задачка от Google Возьмем для нашего финального оценивания задачку, которую дают на собеседовании в Google.
Вкратце, цель алгоритма — найти в отсортированном массиве два любых числа, которые в сумме дали бы нам искомое число target. Решение 1: полный проход по массиву Сложность по времени: O(n2) Сложность по памяти: O(С) Это решение в лоб. Не самое оптимальное, поскольку время быстро растет при увеличении количества элементов, но зато дополнительную память мы особо не потребляем. Решение 2: используем HashSet Проходимся по массиву и элементы, которые мы уже проверили добавляем, в HashSet. Если HashSet содержит недостающий для суммы элемент, значит все хорошо , мы закончили и можем возвращать результат. Добавление и поиск в HashSet делается за время O(C). Сложность по времени: O(n) Сложность по памяти: O(n) Это как раз пример того, как можно выиграть в производительности, выделив дополнительную память для промежуточных структур. Решение 3: используем бинарный поиск Алгоритм бинарного поиска имеет известную сложность — O(log(n)). O(n) нам добавилась от внешнего цикла for, а все, что внутри цикла while — это и есть алгоритм бинарного поиска. Согласно Правилу 4 сложности перемножаются. Сложность по времени: O(n*log(n)) Сложность по памяти: O(С) Решение 4: используем метод двух указателей Двигаем левый и правый указатели к центру, пока они не сойдутся или не найдется пара подходящих нам значений. Сложность по времени: O(n) Сложность по памяти: O(С) И это — самый оптимальный из всех вариантов решения, не использующий дополнительной памяти и совершающий наименьшее количество операций. Бенчмаркинг решений Теперь, зная сложности всех четырех вариантов решения, попробуем провести бенчмаркинг этого кода и посмотреть, как алгоритмы будут вести себя на различных наборах данных. В этом поможет информация из предыдущей нашей статьи. Результаты будут следующими: Что мы тут видим? За baseline решения мы берем прямой проход массиву Быстрее на малом объеме данных выполняется только наш самый оптимальный вариант решения — Вариант же с На 1 000 же элементов вариант с полным проходом по циклу ( На 10 000 элементах алгоритму с полным проходом потребовалось и вовсе 9,7 секунды для завершения расчетов, в то время как остальные справлялись за 0.1 секунды и меньше. А самый оптимальный вариант решения и вовсе нашел решение за 3 миллисекунды. Почему же бинарный поиск обогнал HashSet? Ведь в теории O(n * log(n)) должен быть медленнее O(n)? Дело в том, что на реальных, а не теоретических компьютерах выделение и освобождение работает не за одинаковое время – то и дело включается Garbage collector. Это подтверждают значения стандартного отклонения (StdDev) в бенчмарке HashSet. Заключение Мы разобрались, как оценивать сложность алгоритмов, а также узнали, как с помощью BenchmarkDotNet проследить связь между сложностью алгоритмов и временем выполнения кода. Это позволит еще до выполнения бенчмаркинга приблизительно оценить — хороший код вы написали или нет. Источник: habr.com Комментарии: |
|