Оцениваем сложность алгоритмов на C# по памяти и времени с примерами
Продолжаем говорить о производительности и оптимизации кода. Сегодня поговорим о том, как и зачем оценивать сложность алгоритмов, а также наглядно покажем, как эта сложность влияет на производительность кода.
В прошлой статье мы разбирались, что такое бенчмаркинг кода и как с его помощью оценивать производительность кода в .NET. В этой – поговорим про оценку сложности алгоритмов. А чтобы все было наглядно, вместе попробуем оценить алгоритмы, которые используются для решения задачки на собеседовании в Google.
Задач такого плана полным-полно на платформах типа LeetCode, CodeWars и других. И их ценность не в том, чтобы заучить различные алгоритмы сортировок, которые вы никогда не будете на практике писать самостоятельно, а в том, чтоб увидеть типичные проблемы, с которыми вы можете столкнуться в практических задачах при разработке.
Оценка сложности алгоритмов
Зачем вообще оценивать сложность алгоритмов и какие способы оценки бывают?
Понимать сложность алгоритмов важно по следующим причинам:
без этих знаний вы не сможете отличить суб-оптимальный код от оптимального и оптимизировать его;
каждый средний или большой проект рано или поздно будет оперировать большим объемом данных. Важно, чтоб ваши алгоритмы это предусматривали и не стали бомбой замедленного действия;
если вы не понимаете концепции оценки сложности алгоритмов, есть вероятность, что вы будете писать низкопроизводительный код.
Чаще говорят про оценку алгоритма по времени (time complexity) — сколько времени понадобится для его выполнения. Время выполнения зависит от количества элементарных операций, которые выполняет компьютер.
Для каждого алгоритма можно сделать несколько оценок сложности:
O большое (O(f)) — позволяет оценить верхнюю границу сложности алгоритмов. Это отношение количества входных данных для алгоритма ко времени, за которое алгоритм сможет их обработать. Простыми словами – это максимальное время работы алгоритма при работе с большими объемами данных.
Омега (Ω(f)) — позволяет оценить нижнюю границу сложности — сколько времени займет работа алгоритма в лучшем случае.
Тета (Θ(f)) — позволяет получить “плотную” оценку сложности, то есть такую, при которой скорость работы в худшем и лучшем случае будет пропорциональна одной функции. Применимо не ко всем алгоритмам.
В IT компаниях зачастую обращают внимание на большое O (Big-O notation), поскольку чаще всего достаточно представлять, как быстро будет расти количество операций при увеличении входных данных в худшем случае. Остальные типы оценок используются редко.
В скобках после О указывают функцию, которая ограничивает сложность. При этом n — это размер входных данных. Например, O(n) означает, что сложность алгоритма растёт линейно. В таком случае время выполнения алгоритма увеличивается прямо пропорционально размеру входных данных.
Если представить график распространенных сложностей алгоритмов, они будут выглядеть вот так:
Если условно разделить сложности на зоны, то сложности вида O(log n), O(1) или O(C) можно будет отнести к зоне «Отлично». Такие алгоритмы вне зависимости от объемов данных будут выполняться очень быстро — практически мгновенно.
Алгоритмы сложности O(n) можно отнести к зоне «Средне» — алгоритмам, сложность которых растет предсказуемо и линейно. Например, если 100 элементов ваш алгоритм обрабатывает за 10 секунд, то 1000 он обработает примерно за 100 секунд. Не лучший результат, но предсказуемый.
Алгоритмы из красной зоны со сложностями
Добавим, что оценка сложности по времени — это теоретическая оценка. Она не учитывает внутренние оптимизации и кеш процессора, в реальности картина может отличаться.
Оценка сложности по памяти
Оценку сложности алгоритмов следует проводить не только по времени выполнения, но и по потребляемой памяти — часто про это забывают во время изучения темы.
Например, для ускорения вычислений можно создать какую-нибудь промежуточную структуру данных типа массива или стека для ускорения алгоритма и кеширования результатов. Это приведет к дополнительным затратам памяти, но при этом может существенно ускорить вычисления.
Сложность по памяти также называют пространственной сложностью (space complexity) и для оценки используют такую же нотацию как для времени — большое O. Например, сложность по памяти
, означает что в худшем случае для алгоритма не понадобится больше памяти, чем пропорционально .
Важно отметить, что при оценке сложности алгоритмов по памяти используют упрощенную модель работы с памятью, так называемою RAM-машину. Это означает, что мы можем читать и записывать любую ячейку памяти за время одной операции. Таким образом, время вычислительных операций и операций с памятью становится одинаковым, что упрощает анализ. Это ближе всего к работе с оперативной памятью, и, например, не учитывает регистры процессора, работу с диском, garbage collector и много чего еще.
Немного практики: правила расчета сложности на пальцах
Мы приводим примеры на C#, хотя здесь можно было бы обойтись и псевдокодом. Надеемся, что они будут понятны.
Пример 1:
Возьмем для начала простой алгоритм присвоения переменной:
private void Alg1(int[] data, int target)
{
var a = data[target];
}
Какова его сложность по времени и по памяти?
С одной стороны, нас может ввести в заблуждение массив данных data неизвестной размерности. Но брать его в расчет при оценке сложности внутреннего алгоритма будет некорректно.
Правило 1: внешние данные не учитываются в сложности алгоритма.
Получается, наш алгоритм состоит только из одной строчки:
var a = data[target];
Доступ к элементу массива по индексу — известная операция со сложностью O(1) или O(C). Соответственно, и весь алгоритм по времени у нас займет O(1).
Дополнительная же память выделяется только под одну переменную. А значит, объем данных, которые мы будем передавать (хоть 1 000, хоть 10 000), не скажется на финальном результате. Соответственно, сложность по памяти у нас так же — O(1) или O(C). Такие алгоритмы называются алгоритмами на месте (in-place). Они могут использовать дополнительную память, но её размер не зависит от количества входных данных.
Для упрощения записи дальше я везде буду писать O(C) вместо O(1), C в этом случае — это константа. Она может равняться 1, 2 или даже 100 — для современных компьютеров это число не принципиально, поскольку и 1, и 100 операций выполняются практически за одно и то же время.
Пример 2:
Рассмотрим второй алгоритм, очень похожий на первый:
private void Alg2(int[] data, int target)
{
var a = data[target];
var b = data[target + 1];
}
Влияет ли размерность входного массива data на количество операций в нем? Нет.
А на выделенную память? - Тоже нет.
Сложность этого алгоритма по времени выполнения можно было бы оценить как O(2*C) — поскольку у нас выполняется в два раза больше операций, чем в предыдущем примере, 2 присваивания вместо 1. Но у нас и на этот счет есть правило:
Правило 2: опускать константные множители, если они не влияют на результат кардинальным образом.
Если принять это правило в расчет, сложность этого алгоритма будет такой же, как и в первом примере — O(C) по времени и O(C) по памяти.
Пример 3:
В третьем примере добавим в наш алгоритм цикл для обработки данных:
private int Alg3(int[] data)
{
var sum = 0;
for (int i = 0; i < data.Length; i++)
{
sum += data[i];
}
return sum;
}
Как мы видим, количество операций, которые будет выполнять цикл, напрямую зависит от количества входных данных: больше элементов в data — больше циклов обработки потребуется для получения финального результата.
Казалось бы, если взять в учет каждую строчку кода нашего алгоритма, то получилось бы что-то такое:
private int Alg3(int[] data)
{
var sum = 0; // O(C)
for (i=0; i < data.Length; i++) // O(n)
{
sum += data[i]; // O(C)
}
return sum;
}
И тогда финальная сложность алгоритма получится O(C)+O(n). Но тут опять вмешивается новое правило:
Правило 3: опускать элементы оценки, которые меньше максимальной сложности алгоритма.
Поясню: если у вас O(C)+O(n), результирующая сложность будет O(n), поскольку. O(n) будет расти всегда быстрее, чем O(C).
Еще один пример —
Итак, сложность нашего третьего примера — O(n). По памяти без изменений — О(С).
Пример 4:
В четвертом примере посчитаем сумму всех возможных пар значений из массива:
private int Alg4(int[] data)
{
var sum = 0;
for (int i = 0; i ‹ data.Length; i++)
{
for (int j = 0; j ‹ data.Length; j++)
{
sum += data[i]*data[j];
}
}
return sum;
}
И для его обработки нам теперь нужно два цикла. Оба этих цикла будут зависеть от размерности входных данных data.
Правило 4: вложенные сложности перемножаются.
Сложность внешнего цикла в нашем примере — O(n), сложность внутреннего цикла — O(n). Согласно правилу, две эти сложности должны быть умножены. В результате максимальная сложность всего алгоритма выйдет равной
Пример с подвохом:
Подадим на вход двумерный массив и посчитаем сумму значений.
private int Alg4_tricky_case(int[][] data)
{
var sum = 0;
for (int i = 0; i < data.Length; i++)
{
for (int j = 0; j < data.Length; j++)
{
sum += data[i][j];
}
}
return sum;
}
Снова видим вложенные циклы — и если во входном массиве N x M элементов, то есть сложность O(N * M), и кажется, что это эквивалентно
Пример 5:
А что мы видим тут? Цикл — уже известная нам сложность – O(n). Но внутри вызывается функция Alg4()
из предыдущего примера:
private int Alg5(int[] data)
{
var sum = 0;
for (int i = 0; i ‹ data.Length; i++)
{
sum += Alg4(data);
}
return sum;
}
Если мы вспомним ее сложность
Правило 5: включайте в оценку общей сложности алгоритма оценки всех вложенных вызовов функций.
Именно поэтому важно понимать сложность методов синтаксического сахара вроде LINQ, базовых коллекций и типов данных — чтоб была возможность оценить, как метод будет вести себя при увеличении объемов данных. При использовании их в коде без понимания внутреннего устройства, вы рискуете получить очень высокую сложность алгоритма, который будет захлебываться при увеличении входящих данных.
Приведу пример минималистичного алгоритма, который выглядит хорошо и компактно (ни в коем случае не претендует на эталонный код), но станет бомбой замедленного действия при работе с большими объемами данных:
private List<int> Alg6(int[] data)
{
List<int> dups = new List<int>();
for (var i = 0; i < data.Length; i++)
{
var currentItem = data[i];
var newArr = data.Skip(i + 1).ToArray();
var duplicates = newArr.Where(x => newArr.Contains(currentItem));
dups.AddRange(duplicates);
}
return dups;
}
Что мы тут видим? Цикл = O(n), Where = O(n), Contains = O(n), так как newArr – это массив.
Итого сложность такого алгоритма будет от
ToArray() будет выделять на каждой итерации дополнительную память под копию массива, а значит сложность по памяти составит O(n).
Задачка от Google
Возьмем для нашего финального оценивания задачку, которую дают на собеседовании в Google.
Подробный разбор задачи и алгоритмы решения можно посмотреть вот в этом видео от Саши Лукина. Рекомендую посмотреть его перед продолжением чтения этой статьи.
Вкратце, цель алгоритма — найти в отсортированном массиве два любых числа, которые в сумме дали бы нам искомое число target.
Решение 1: полный проход по массиву
public static int[] FindPairWithFullWalkthrough(int[] data, int target)
{
for (int i = 0; i < data.Length; i++)
{
for (int j=i+1; j < data.Length; j++)
{
if (data[i] + data[j] == target)
return new[] { data[i], data[j] };
}
}
return new int[0];
}
Сложность по времени:
Сложность по памяти: O(С)
Это решение в лоб. Не самое оптимальное, поскольку время быстро растет при увеличении количества элементов, но зато дополнительную память мы особо не потребляем.
Решение 2: используем HashSet
public static int[] FindPairUsingHashSet(int[] data, int target)
{
HashSet<int> set = new HashSet<int>();
for (int i = 0; i < data.Length; i++)
{
int numberToFind = target - data[i];
if (set.Contains(numberToFind))
return new [] { data[i], numberToFind };
set.Add(data[i]);
}
return new int[0]
}
Проходимся по массиву и элементы, которые мы уже проверили добавляем, в HashSet. Если HashSet содержит недостающий для суммы элемент, значит все хорошо , мы закончили и можем возвращать результат. Добавление и поиск в HashSet делается за время O(C).
Сложность по времени: O(n)
Сложность по памяти: O(n)
Это как раз пример того, как можно выиграть в производительности, выделив дополнительную память для промежуточных структур.
Решение 3: используем бинарный поиск
public static int[] FindPairUsingBinarySearch(int[] data, int target)
{
for (int i = 0; i < data.Length; i++)
{
int numberToFind = target - data[i];
int left = i + 1;
int right = data.Length - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (data[mid] == numberToFind)
{
return new[] { data[i], data[mid] };
}
if (numberToFind < data[mid])
{
right = mid - 1;
}
else
{
left = mid + 1;
}
}
}
return new int[0];
}
Алгоритм бинарного поиска имеет известную сложность — O(log(n)). O(n) нам добавилась от внешнего цикла for, а все, что внутри цикла while — это и есть алгоритм бинарного поиска. Согласно Правилу 4 сложности перемножаются.
Сложность по времени: O(n*log(n))
Сложность по памяти: O(С)
Решение 4: используем метод двух указателей
public static int[] FindPairUsingTwoPointersMethod(int[] data, int target)
{
int left = 0;
int right = data.Length - 1;
while (left < right)
{
int sum = data[left] + data[right];
if (sum == target) return new[] { data[left], data[right] };
if (sum < target)
{
left++;
}
else
{
right--;
}
}
return new int[0];
}
Двигаем левый и правый указатели к центру, пока они не сойдутся или не найдется пара подходящих нам значений.
Сложность по времени: O(n)
Сложность по памяти: O(С)
И это — самый оптимальный из всех вариантов решения, не использующий дополнительной памяти и совершающий наименьшее количество операций.
Бенчмаркинг решений
Теперь, зная сложности всех четырех вариантов решения, попробуем провести бенчмаркинг этого кода и посмотреть, как алгоритмы будут вести себя на различных наборах данных. В этом поможет информация из предыдущей нашей статьи.
Результаты будут следующими:
Что мы тут видим?
За baseline решения мы берем прямой проход массиву FindPairWithFullWalkthrough
. На 10 объектах он отрабатывает в среднем за 20 наносекунд и занимает второе место по производительности.
Быстрее на малом объеме данных выполняется только наш самый оптимальный вариант решения — FindPairUsingTwoPointersMethod
.
Вариант же с HashSet
занял в 8 раз больше времени для работы с малым объемом данных и потребовал выделения дополнительной памяти, которую потом нужно будет собрать Garbage Collector-у.
На 1 000 же элементов вариант с полным проходом по циклу (FindPairWithFullWalkthrough
) начал заметно отставать от остальных алгоритмов. Причиной этому — его сложность O(n^2), которая растет заметно быстрее всех остальных сложностей.
На 10 000 элементах алгоритму с полным проходом потребовалось и вовсе 9,7 секунды для завершения расчетов, в то время как остальные справлялись за 0.1 секунды и меньше. А самый оптимальный вариант решения и вовсе нашел решение за 3 миллисекунды.
Почему же бинарный поиск обогнал HashSet? Ведь в теории O(n * log(n)) должен быть медленнее O(n)? Дело в том, что на реальных, а не теоретических компьютерах выделение и освобождение работает не за одинаковое время – то и дело включается Garbage collector. Это подтверждают значения стандартного отклонения (StdDev) в бенчмарке HashSet.
Заключение
Мы разобрались, как оценивать сложность алгоритмов, а также узнали, как с помощью BenchmarkDotNet проследить связь между сложностью алгоритмов и временем выполнения кода. Это позволит еще до выполнения бенчмаркинга приблизительно оценить — хороший код вы написали или нет.