Сложность алгоритмов и типичные ошибки в 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.