Сложность алгоритмов и типичные ошибки в Python

Всем привет! Я расскажу, что такое сложность алгоритмов и откуда она берётся, разберу типичные заблуждения и самые частые ошибки новичков. Материал рассчитан в первую очередь на начинающих Python-разработчиков, а также на тех, у кого Python — первый язык программирования.

Что такое сложность алгоритмов?

Когда рассказывают про сложность алгоритмов, чаще всего приводят в пример график, на котором нарисованы функции, и говорят, что вот этот алгоритм по сложности равен этой функции, а тот алгоритм равен другой функции, и так далее. Типичные примеры:

• Log(N) — бинарный поиск в уже отсортированном массиве;

• N — работа кода в одном цикле;

• N*Log(N) — сортировка;

• N**2 — цикл, вложенный в другой цикл.

Примечание: ассемблер настолько близок к машинному коду, что фактически одному оператору ассемблера соответствует одна машинная инструкция (1:1). Таким образом, можно довольно точно оценить фактическую сложность алгоритма.

Очевидно, что чем сложнее алгоритм, тем быстрее возрастает функция. Но что это значит, если копнуть поглубже? Рассмотрим на примере C++ какой-нибудь алгоритм со сложностью O(N), например, создание массива, и посмотрим, как эта операция будет выглядеть в дизассемблере.

Подробнее почитать о том, сколько стоит каждая операция можно в статье «Сложность алгоритмов и операций на примере Python».

Примечание: C/C++ намного ближе к железу в отличие от высокоуровневого Python, поэтому его гораздо легче дизассемблировать. Ясно, что список в Python работает отлично от того, как работает массив в C++, но принципы их работы абсолютно одинаковы.

Чтобы создать массив из 7 элементов в C++:

int arr[] = {1, 2, 3, 4, 5, 6, 7};

нужно будет сделать 7 операций в ассемблере:

mov     DWORD PTR [rbp-32], 1 mov     DWORD PTR [rbp-28], 2 mov     DWORD PTR [rbp-24], 3 mov     DWORD PTR [rbp-20], 4 mov     DWORD PTR [rbp-16], 5 mov     DWORD PTR [rbp-12], 6 mov     DWORD PTR [rbp-8], 7

Именно это и показывает функция сложности алгоритма O(N) — сколько элементов нужно обработать, столько операций и будет проделано. Для O(N*N) — то же самое, но количество операций уже будет в квадрате. В Python для создания списка из 7 элементов также потребуется не менее семи операций:

l = [1, 2, 3, 4, 5, 6, 7]

Другой пример: чтобы записать один элемент массива в C++:

arr[0] = 111;

Требуется всего одна операция в ассемблере:

mov     DWORD PTR [rbp-32], 111

Именно поэтому эта операция имеет сложность O(1). То же самое и для Python:

l[0] = 111

Эта операция также имеет сложность O(1) по той же логике.

Теперь, когда стало ясно, откуда берётся сложность алгоритмов, можно перейти к типичным ошибкам.

Пример 1, работа с типом string

Рассмотрим простейший показательный пример, который вытекает из непонимания определения сложности алгоритма. Допустим, нам необходимо собрать строку в цикле, для этого можно написать такой код:

line = "" for i in range(10_000):     line += "i"

Казалось бы, простой и работающий код, который даёт верный результат — в данном случае строку из 10 тысяч символов «i». Время исполнения этого кода 5 мс. 

На первый взгляд это алгоритм со сложностью O(N), но если посмотреть на последнюю строчку кода, то видно, что тип string на самом деле не добавляет символ к текущему значению, а пересоздаёт значение с новым символом, так как string является неизменяемым (immutable) типом. Другими словами, только одна эта операция будет иметь сложность O(N), ведь чтобы скопировать значение в новую строку, нужно скопировать каждый элемент старой строки плюс новый символ. Кроме того, эта операция выполняется ещё и в цикле, то есть итоговая сложность этого алгоритма будет равна O(N*N). 

Примечание: учитывая, что переменная line растёт последовательно от 0 до N, правильно будет сказать, что сложность равна O(N*M), где M < N. Но для простоты будем считать, что сложность этого алгоритма O(N*N). В общем-то, это не будет большой ошибкой.

Этот алгоритм можно улучшить, если использовать операцию, сложность которой равна O(1), например append:

word = [] for i in range(10_000):     word.append("i") line = "".join(word)

Теперь алгоритм отработал за 2 мс, что в 2,5 раза быстрее чем предыдущий вариант, к тому же теперь его сложность равняется O(N).

Стоит обратить внимание, что операция append в Python выполняется на самом деле за амортизированный O(1), также как и в других языках высокого уровня, таких как Java или C#. Другими словами, крайне редко, но эта операция может выполниться за время O(N). Под капотом у списка лежит массив, в который и сохраняются элементы. Если же размера списка не хватит, то перед сохранением нового элемента он будет увеличен в два раза, именно в этом случае и будет O(N).

Рассмотрим также пример с операцией присвоения, которая уже действительно имеет сложность O(1):

N = 10_000 word = [None] * N for i in range(N):     word[i] = "i" line = "".join(word)

Время исполнения сократилось до 1,35 мс, что немного быстрее, чем с append. Оба эти алгоритма будут исполняться за примерно одно и то же время, вариант с присвоением на практике будет отрабатывать чаще совсем на чуть-чуть быстрее.

Пример 2, преобразования массивов

Возьмём очень большой список и будем в нём искать элементы:

arr = list(range(10_000_000)) matcher = [500_000, 100_000, 1000_000_000] * 10

В нашем случае массив будет состоять из 10 млн элементов, а искать мы в нём будем 30 чисел. В самом простом виде алгоритм будет выглядеть так: в цикле перебираем каждый из 30 элементов из matcher и ищем его в arr. 

for i in matcher:     if i in arr:         pass

Этот алгоритм имеет сложность O(N*N): перебор в цикле это O(N), и поиск в списке тоже O(N). Длительность его работы 1,2 секунды.

Этот код можно улучшить, ведь мы знаем, что поиск по множеству имеет сложность O(1). Как же может переписать алгоритм начинающий программист? Например, так:

for i in matcher:     if i in set(arr):         pass

Да, имея чистые помыслы, начинающий или не знающий сложности алгоритмов программист может так написать. Этот пример тоже имеет сложность O(N*N), поиск по множеству — O(1), но преобразование списка в множество — O(N). Несмотря на сложность O(N*N), как и в предыдущем примере, алгоритм выполняется теперь за 15,2 секунды. Причина в том, что поиск по списку в худшем случае даёт O(N), а вот преобразование будет всегда O(N).

Правильно было бы написать так:

arr_s = set(arr) for i in matcher:     if i in arr_s:         pass

Теперь код исполняется 0,5 секунды. Эта ошибка встречается на удивление часто, она незаметна, но может замедлить работу алгоритма и увеличить потребление памяти. Важно понимать, что ненужное преобразование массива элементов потребляет лишние ресурсы.

Типичные примеры с ошибками преобразования:

• set(list(map(str, arr))) — нужно сразу приводить к множеству: set(map(str, arr))

• list(sorted(arr)) — sorted и так возвращает список

И другие ошибки, вариаций может быть множество.

Пример 3, ошибки при объявлении переменных

Недаром говорят, что объявлять переменные желательно в начале метода. Это, конечно, рекомендация, но для начинающих она полезна. Часто неопытный программист может совершить подобную ошибку: допустим, у нас есть какой-то метод, который производит операцию деления:

def divider(a: int, b: int):     res = a / b     return res

Предположим, что QA-инженер (он же тестировщик) в команде нашёл в этом коде ошибку: заметил, что нельзя делить на ноль, выставил баг, и начинающий программист исправил код:

def divider(a: int, b: int):     try:         res = a / b     except ZeroDivisionError:         print("don't divide on zero!")     return res

Да, это довольно частая ситуация, когда баг маскируется другой ошибкой. В данном случае деление на ноль обработается корректно, но тут же возникнет ошибка: UnboundLocalError: local variable 'res' referenced before assignment, то есть обращение к несуществующей переменной, так как она не будет инициализирована в блоке try/except из-за ошибки деления.

Самый простой способ этого избежать — объявлять переменные заранее:

def divider(a: int, b: int):     res = None     try:         res = a / b     except ZeroDivisionError:         print("don't divide on zero!")     return res

Часто переменные объявляют в сегменте if, подобный код не является хорошим тоном:

def divider(a: int, b: int, flag: bool):     if flag:         res = a / b     return res

Объявить так переменную возможно в Python, а в Java или C# подобное не прокатит. Такой код в этих языках программирования вызовет ошибку на этапе компиляции.

Пример 4, входные параметры

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

def func(l: list):     l[0] = 10 l = [1, 2, 3] func(l)

Казалось бы, простой код, но что же будет лежать в списке после его выполнения? А вот что:

print(l)

[10, 2, 3]

Как же так получилось? Ведь метод ничего не возвращает, список мы в коде никак не переопределяем, только внутри метода. Рассмотрим другой пример:

def func2(a: int):     a = 10 a = 0 func2(a)

Чему же будет равна переменная:

print(a)

0

Во втором случае переменная не изменилась, отчего же так происходит? Дело в том, что объекты в Python делятся на те, что передаются по ссылке — list, set, dict, и те, что передаются по значению — int, float, str, tuple.

Рассмотрим ещё один пример:

l1 = [1, 2] l2 = l1 l1.append(3)

В этом случае оба списка будут равны, несмотря на то, что мы меняли только один из них:

print(l1, l2)

([1, 2, 3], [1, 2, 3])

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

l2 = l1[:] l2 = list(l1) l2 = l1.copy()

В этом случае ссылки будут на разные области памяти, что и решит проблему.

Пример 5, значение по умолчанию

Это, вероятно, одна из самых популярных ошибок начинающего программиста. Рассмотрим пример:

def func3(val: int, l: list = []):     l.append(val)     print(l)

Казалось бы, обычный метод, но давайте вызовем его несколько раз подряд и посмотрим, что получится:

func3(1)

[1]

func3(2)

[1, 2]

Да, в этом и подвох: новый пустой список по умолчанию не создаётся. Именно поэтому при последующих вызовах, в которых программист ожидает пустой массив, как было заложено логикой алгоритма, в массиве остаются элементы от прошлых вызовов метода. Так уж работает Python: он всегда берёт одну и ту же ссылку на список в подобном случае.

Если нужен пустой список по умолчанию, следует писать так:

def func3(val: int, l: Optional[list] = None):     if not l:         l = []     l.append(val)     print(l)

То же правило касается множества (set) и словаря (dict), их также нельзя делать пустыми в параметрах по умолчанию.

Заключение

Простыми словами и на примерах я разобрал, что такое сложность алгоритма, показал, откуда берётся это понятие, разобрал типовые ошибки, вытекающие из непонимания сложности и самые распространённые среди новичков. 

Не стоит бояться делать ошибки, если ты начинающий разработчик. Не ошибается только тот, кто ничего не делает.

Спасибо за внимание.

Репозиторий с исходным кодом — на GitHub.