Сложность алгоритмов и типичные ошибки в Python21.10.2024 08:15

cf4723494a24a33ae82d5b384bece2ed.png

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

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

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

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

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

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

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

1985a5b2aa0a08f6ad910d342eea0a43.png

Примечание: ассемблер настолько близок к машинному коду, что фактически одному оператору ассемблера соответствует одна машинная инструкция (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

2043d5aef7cf432304df5ccfbf4c69c0.png

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

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, преобразования массивов

7f33cd5e3ecd79a1981236138febed27.png

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

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, ошибки при объявлении переменных

9eb57f681d2c569f536940ac94c76214.png

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

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, входные параметры

b74e2fca253c1f92174fc94ee1ec2081.png

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

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, значение по умолчанию

729250825894555494c14ee7c6d59c0f.png

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

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), их также нельзя делать пустыми в параметрах по умолчанию.

Заключение

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

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

97c232c4d5bc88393d7f1313743e4b4d.png

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

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

© Habrahabr.ru