Оцениваем сложность алгоритмов на 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© можно будет отнести к зоне «Отлично». Такие алгоритмы вне зависимости от объемов данных будут выполняться очень быстро — практически мгновенно.
Алгоритмы сложности O (n) можно отнести к зоне «Средне» — алгоритмам, сложность которых растет предсказуемо и линейно. Например, если 100 элементов ваш алгоритм обрабатывает за 10 секунд, то 1000 он обработает примерно за 100 секунд. Не лучший результат, но предсказуемый.
Алгоритмы из красной зоны со сложностями O (n2) и выше трудно отнести к высокопроизводительным. НО! тут все сильно зависит от объемов входных данных. Если вы уверены, что у вас всегда будет небольшой объем данных (например, 100 элементов), и обрабатываться он будет в приемлемое для вас время, то все в порядке, такие алгоритмы тоже можно использовать. Но если же вы не уверены в постоянности объемов данных (может прийти и 10 000 элементов вместо 100) — лучше все-таки задуматься над оптимизацией алгоритмов.
Оценка сложности по памяти
Оценку сложности алгоритмов следует проводить не только по времени выполнения, но и по потребляемой памяти — часто про это забывают во время изучения темы.
Например, для ускорения вычислений можно создать какую-нибудь промежуточную структуру данных типа массива или стека для ускорения алгоритма и кеширования результатов. Это приведет к дополнительным затратам памяти, но при этом может существенно ускорить вычисления.
Сложность по памяти также называют пространственной сложностью (space complexity) и для оценки используют такую же нотацию как для времени — большое O. Например, сложность по памяти О (n2), означает что в худшем случае для алгоритма не понадобится больше памяти, чем пропорционально n2.
Важно отметить, что при оценке сложности алгоритмов по памяти используют упрощенную модель работы с памятью, так называемою RAM-машину. Это означает, что мы можем читать и записывать любую ячейку памяти за время одной операции. Таким образом, время вычислительных операций и операций с памятью становится одинаковым, что упрощает анализ. Это ближе всего к работе с оперативной памятью, и, например, не учитывает регистры процессора, работу с диском, garbage collector и много чего еще.
Немного практики: правила расчета сложности на пальцах
Мы приводим примеры на C#, хотя здесь можно было бы обойтись и псевдокодом. Надеемся, что они будут понятны.
Пример 1:
Возьмем для начала простой алгоритм присвоения переменной:
private void Alg1(int[] data, int target)
{
var a:int = data[target];
}Какова его сложность по времени и по памяти?
С одной стороны, нас может ввести в заблуждение массив данных data неизвестной размерности. Но брать его в расчет при оценке сложности внутреннего алгоритма будет некорректно.
Правило 1: внешние данные не учитываются в сложности алгоритма.
Получается, наш алгоритм состоит только из одной строчки:
var a = data[target];
Доступ к элементу массива по индексу — известная операция со сложностью O (1) или O©. Соответственно, и весь алгоритм по времени у нас займет O (1).
Дополнительная же память выделяется только под одну переменную. А значит, объем данных, которые мы будем передавать (хоть 1 000, хоть 10 000), не скажется на финальном результате. Соответственно, сложность по памяти у нас так же — O (1) или O©. Такие алгоритмы называются алгоритмами на месте (in-place). Они могут использовать дополнительную память, но её размер не зависит от количества входных данных.
Для упрощения записи дальше я везде буду писать O© вместо O (1), C в этом случае — это константа. Она может равняться 1, 2 или даже 100 — для современных компьютеров это число не принципиально, поскольку и 1, и 100 операций выполняются практически за одно и то же время.
Пример 2:
Рассмотрим второй алгоритм, очень похожий на первый:
private vpid Alg2(int[]data, int target)
{
var a:int = data[target];
var b:int = data[target + 1];
}Влияет ли размерность входного массива data на количество операций в нем? Нет.
А на выделенную память? — Тоже нет.
Сложность этого алгоритма по времени выполнения можно было бы оценить как O (2*C) — поскольку у нас выполняется в два раза больше операций, чем в предыдущем примере, 2 присваивания вместо 1. Но у нас и на этот счет есть правило:
Правило 2: опускать константные множители, если они не влияют на результат кардинальным образом.
Если принять это правило в расчет, сложность этого алгоритма будет такой же, как и в первом примере — O© по времени и O© по памяти.
Пример 3:
В третьем примере добавим в наш алгоритм цикл для обработки данных:
private int Alg3(int[] data)
{
var sum = 0;
for (int i = 0; i < data.Lenght; i++)
{
usum += data[i];
}
return sum;
}Как мы видим, количество операций, которые будет выполнять цикл, напрямую зависит от количества входных данных: больше элементов в data — больше циклов обработки потребуется для получения финального результата.
Казалось бы, если взять в учет каждую строчку кода нашего алгоритма, то получилось бы что-то такое:
private int Alg3(int[] data)
{
var sum = 0; // O(C)
for (i , data.Lenght; i++) // O(n)
{
sum += data[i];//O(C)
}
return sum;
}И тогда финальная сложность алгоритма получится O©+O (n). Но тут опять вмешивается новое правило:
Правило 3: опускать элементы оценки, которые меньше максимальной сложности алгоритма.
Поясню: если у вас O©+O (n), результирующая сложность будет O (n), поскольку. O (n) будет расти всегда быстрее, чем O©.
Еще один пример — O (n)+O (n2). При такой сложности у нас n2 всегда растет быстрее, чем N, а значит O (n) мы отбрасываем и остается только O (n2).
Итак, сложность нашего третьего примера — 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). Согласно правилу, две эти сложности должны быть умножены. В результате максимальная сложность всего алгоритма выйдет равной O (n2). По памяти без изменений — О©.
Пример с подвохом:
Подадим на вход двумерный массив и посчитаем сумму значений.
private int Alg4(int[][] data)
{
var sum = 0;
for (int i = 0; i < dana.Lenght; i++)
{
fir (int j = 0; j < data[i].Lenght; j++)
{
sum += data[i][j];
}
}
return sum;
}Снова видим вложенные циклы — и если во входном массиве N x M элементов, то есть сложность O (N * M), и кажется, что это эквивалентно O (n2). Но на самом деле, нет — в данном случае на вход просто подается N * M элементов и время пропорционально N * M, то линейное O (n).
Пример 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;
}Если мы вспомним ее сложность O (n2), а также правило 4, то получим, что сложность этого алгоритма — O (n3) при всей его визуальной минималистичности. Со сложностью по времени без изменений.
Правило 5: включайте в оценку общей сложности алгоритма оценки всех вложенных вызовов функций.
Именно поэтому важно понимать сложность методов синтаксического сахара вроде LINQ, базовых коллекций и типов данных — чтоб была возможность оценить, как метод будет вести себя при увеличении объемов данных. При использовании их в коде без понимания внутреннего устройства, вы рискуете получить очень высокую сложность алгоритма, который будет захлебываться при увеличении входящих данных.
Приведу пример минималистичного алгоритма, который выглядит хорошо и компактно (ни в коем случае не претендует на эталонный код), но станет бомбой замедленного действия при работе с большими объемами данных:
private List Alg6(int[] data)
{
List dups = new List();
for (var i = 0; i < data.Lenght; i++)
{
var currentItem:int = data[i];
var newArr:int[] = data.Skip(i + 1).ToArray();
var duplicates:IEnumerable = newArr.Where(x:int => newArr.Contains(currentItem));
dups.AddRange(duplicates);
}
return dups;
} Что мы тут видим? Цикл = O (n), Where = O (n), Contains = O (n), так как newArr — это массив.
Итого сложность такого алгоритма будет от O (n3) по времени выполнения.
ToArray () будет выделять на каждой итерации дополнительную память под копию массива, а значит сложность по памяти составит O (n2).
Задачка от Google
Возьмем для нашего финального оценивания задачку, которую дают на собеседовании в Google.
Подробный разбор задачи и алгоритмы решения можно посмотреть вот в этом видео от Саши Лукина. Рекомендую посмотреть его перед продолжением чтения этой статьи.
Вкратце, цель алгоритма — найти в отсортированном массиве два любых числа, которые в сумме дали бы нам искомое число target.
Решение 1: полный проход по массиву
public static int[] FindPairWithFullWalkthrough(int[] data, int target)
{
for (int i = 0; i < dataLenght; i++)
{
for (int j=i+1; j < data.Lenght; j++)
{
if (data[i] + data[j] == target)
return new[] { data[i], data[j] };
}
}
retirn new int[0];
}Сложность по времени: O (n2)
Сложность по памяти: O©
Это решение в лоб. Не самое оптимальное, поскольку время быстро растет при увеличении количества элементов, но зато дополнительную память мы особо не потребляем.
Решение 2: используем HashSet
public static int[] FindPairUsingHashSet(int[] data, int target)
{
HashSet set = new Hashset();
for (int i = 0; i < data.Lenght; 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©.
Сложность по времени: O (n)
Сложность по памяти: O (n)
Это как раз пример того, как можно выиграть в производительности, выделив дополнительную память для промежуточных структур.
Решение 3: используем бинарный поиск
public static int[] FindPairUsingBinarySearch(int[] data, int target)
{
for (int i = 0; i < data.Lenght; i++)
{
int numberToFind = target - data[i];
int left = i + 1;
in right = data.Lenght - 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 stati int[] FindPairUsingTwoPointersMethod(int[] data, int target)
{
int left = 0;
int right = data.Lenght - 1;
while (left < right)
{
int sim = data[left] + data[right];
if (sum == target) return new[] { data[left], data[right] };
{
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 проследить связь между сложностью алгоритмов и временем выполнения кода. Это позволит еще до выполнения бенчмаркинга приблизительно оценить — хороший код вы написали или нет.
Habrahabr.ru прочитано 3988 раз
