- Регистрация
- 23 Август 2023
- Сообщения
- 2 819
- Лучшие ответы
- 0
- Реакции
- 0
- Баллы
- 51
Offline
Предлагаю разобраться, как правильно оценить код с точки зрения его скорости выполнения.
Прежде всего надо выяснить, что мы понимаем под эффективным алгоритмом. Попробую дать авторское определение: эффективный алгоритм - код, который выполняется с минимальным использованием вычислительных ресурсов процессора. Соответственно, неэффективный алгоритм, наоборот, требует больше ресурсов и, соответственно, больше времени для выполнения.
Давайте рассмотрим, что же такое «хороший» и «плохой» алгоритм, на примере простой задачи с leetcode.
Условие: на вход поступает массив целых чисел. На выходе необходимо вывести массив, в котором все нули расположены в конце, а остальные числа сохраняют свой порядок.
Пример
Вход: 7 0 1 15 0 0 3 9 0 25
Выход: 7 1 15 3 9 25 0 0 0 0
«Плохое» решение:
def solution1(nums):
i = 0
n = len(nums)
while i < n:
if nums == 0:
ind = i
for j in range(ind + 1, len(nums)):
nums[ind], nums[j] = nums[j], nums[ind]
ind += 1
n -= 1
else:
i += 1
return nums
Идея первого решения заключается в том, чтобы последовательно сдвигать каждый ноль по отдельности вправо, пока все нули не окажутся в конце массива.
«Хорошее» решение:
def solution2(nums):
i = 0
for j in range(len(nums)):
if nums[j] != 0:
nums, nums[j] = nums[j], nums
i += 1
return num
В основе второго решения лежит метод двух указателей, в котором nums указывает на ноль. Если nums[j] не указывает на ноль, то значения указателей меняются местами, и нули перемещаются в конец массива.
Измерим время выполнения каждого алгоритма на одинаковых входных данных с помощью встроенной библиотеки timeit. Важно уточнить, что считается среднее время 1 000 000 итераций кода.
Время выполнения первого решения: 0.00000422994859999744 сек.
Время выполнения второго решения: 0.00000132772239999031 сек.
Несмотря на то, что второе решение выполнилось быстрее первого, оба алгоритма работают весьма за оптимальное время. Но что будет, если размер входных данных увеличится в 10^4 раза? Давайте проверим. На этот раз возьмем среднее арифметическое 10 итераций.
Время выполнения первого алгоритма: 84.48735556000028168455 сек.
Время выполнения второго алгоритма: 0.01210930999950505724 сек.
Легко заметить, что при масштабировании входных данных первый алгоритм резко деградировал, а второй всё также сохранил свою эффективность.
Проверять каждый раз эффективность алгоритма, замеряя время выполнения программы, неудобно и не совсем точно. Чтобы избежать лишних сложностей, обратимся к О-большому (Big O Notation). Это математическая нотация, которая помогает определить сложность алгоритма от размера входных данных без необходимости замерять время. О-большим принято оценивать сложность алгоритма в худшем случае. Рассмотрим на примере.
Допустим у нас есть три массива с одинаковым размером. Нужно написать алгоритм, который находит число 256 и выводит YES, если число есть, иначе NO
Входные данные
nums1 = [1, 3, 5, 17, 29, 10, 256]
nums2 = [1, 3, 5, 555, 17, 29, 10]
nums3 = [256, 1, 3, 5, 17, 29, 10]
def solution(nums):
for x in nums:
if x == 256:
return 'YES'
return 'NO'
Анализ трех массивов показывает, что программа с nums1 и nums2 займет больше всего времени и, соответственно, выполнит больше действий, так как искомое число в первом случае находится в конце, а во втором отсутствует. Быстрее всего выполнится код с nums3, так как 256 находится в начале массива.
Вывод: несмотря на то, что скорость выполнения при nums3 быстрее, чем при nums1 или nums2, в общем случае алгоритм описывается по наихудшему сценарию, то есть O
- линейная сложность.Еще один пример квадратичной сложности
nums = [8, 1, 5, 2, 7, 4, 9, 0, 3, 6]
for x in range(len(nums)):
nums.remove(x)
O(1) — Доступ к элементу массива
O(log n) — Бинарный поиск
O — Линейный проход по массиву
O(n log n) — Быстрая сортировка
O(n²) — Два вложенных цикла
O(2^n) — Перебор всех подмножеств множества
Нужно ли оценивать сложность алгоритма на постоянной основе? Это важно, но не всегда необходимо. Нужно понимать, что оценивать сложность алгоритма и оптимизировать надо с умом. Например, если вы пишете код для работы с небольшим количеством данных, можно этим пренебречь. Но если вы разрабатываете высоконагруженный сервис, то без оценки сложности далеко не уедешь.