Погрузитесь в анализ времени выполнения, быстрый и грязный взгляд на большой вопрос

Приветствую вас, коллеги по Интернету, сегодня я хотел бы затронуть тему, которая, как мне кажется,
невероятно важна, но также туманна по своей природе. Эта тема: пытаемся найти большую сложность вашей программы! Мне кажется, что споры о временной сложности алгоритма - это стереотип, который часто приписывают программистам высокого уровня. Однако каждый может что-то выиграть, зная, как сократить время выполнения своих программ! Поскольку область разработки программного обеспечения растет и все больше людей начинают программировать, один из самых простых способов отличить программистов - это то, насколько оптимальны их решения. Разве вы не предпочтете нанять того, кто пишет эффективный код, а не того, кому все равно (при условии, конечно, что оба решения верны?)

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

Итак, с чего начать? Для простоты давайте оставим наш объем небольшим. Допустим, вы пытаетесь найти сложность скорости написанного вами простого метода. Мы также будем игнорировать сложность памяти. На какую часть вашего метода вам нужно обратить внимание, чтобы рассчитать время выполнения? Ну все! Каждая часть вашего метода, которую компьютер должен проанализировать и выполнить, потребует некоторой вычислительной мощности и, как следствие, потребует некоторого времени.
Хотя было бы неплохо иметь возможность выделить определенное количество времени для каждый расчет, который никому не нужен. Это связано с тем, что скорость простого действия, такого как привязка переменной или добавление двух небольших
целых чисел, на самом деле зависит от самого оборудования. Это происходит по разным причинам (включая выделение памяти, небольшие различия в схемах, доступность процессора и т. Д.). Вы можете вычислить 1 + 1
миллион раз, и для каждого из этих вычислений потребуется немного разное количество времени, даже если только на одну триллионную долю секунды. Таким образом, при вычислении временной сложности вы на самом деле хотите максимально обобщить и абстрагировать многие из этих операций, чтобы они занимали такое же количество времени. Хотя ваш компьютер определенно может вычислить 1 + 1 быстрее, чем 100000 * 100000, для простоты мы предполагаем, что они занимают такое же количество времени.

Давайте поговорим об обозначениях! Временная сложность Big O часто представляется как O (x), где x является функцией входного размера n. Есть и другие способы обозначить это, например способ показать среднее время или время наихудшего случая, но мы будем рассматривать только O (x). В моей школе мы использовали тета-знак вместо О, но я не думаю, что это обязательно стандарт.

Таким образом, любое простое вычисление, такое как сложение целых чисел или привязка переменной, можно упростить до времени O (1). Мы используем 1, потому что он постоянный. Он постоянен, потому что мы можем рассчитывать на то, что наш компьютер всегда завершит
это вычисление примерно за одно и то же время. Другие вещи, которые требуют постоянного времени, - это такие вещи, как вызовы методов и доступ к элементам массива по индексу. Давайте посмотрим на пару методов для анализа! (Честное предупреждение, это не мой код. Этот код был написан Даниэлем Померанцем на Java. Все, что я сделал, это преобразовал его в Ruby.)

Оба эти метода вычисляют n-ю цифру последовательности Фибоначчи. Если вы не знаете, что такое последовательность Фибоначчи, ничего страшного! Быстрое объяснение состоит в том, что это последовательность чисел, где n-е число
равно сумме двух предыдущих чисел. Первые два числа последовательности - 1. Третье число в последовательности - это сумма первых двух чисел, поэтому это 2. Для тех, кто предпочитает понимать визуально, вот первые 10 цифр последовательности: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. Как видите, каждое число равно сумме двух чисел перед ним.

Какой метод лучше? Я сделал это очевидным с помощью названий, но я думаю, что многие люди поначалу подумают, что первый метод «лучше». Это потому, что это более чистый метод, который выполняет работу с меньшим количеством строк кода.
Второй метод немного уродлив, поскольку ему приходится отслеживать несколько переменных через цикл while. Однако они имеют совершенно разные сложности Big O, и я покажу вам, почему второй вариант лучше.

Давайте пройдемся по первому методу построчно. Сначала мы вызываем метод, набирая slow_fibonacci (n) (n должно быть целым числом).
Когда мы вызываем метод, компьютер должен найти адрес памяти, в котором определена эта программа. Это требует O (1) время. Далее у нас есть условное! Метод сравнивает значение n с 2. Это также делается за время O (1).
Если условие истинно, мы возвращаем 1, что также выполняется в O (1).
Однако, если условие ложно, мы вызываем два новых экземпляра метода! Таким образом, для каждого вызова метода мы должны вызывать сам метод еще два раза. Если n очень велико, это означает, что мы вызываем метод
примерно 2 ^ n раз! Таким образом, наши общие вычисления составляют O (3), выполненные 2 ^ n раз. Это оценивается как O (3 * 2 ^ n), что может быть приближено к O (2 ^ n). Мы можем сделать это приближение, потому что, когда n очень велико, не будет большой
разницы, умножаем ли мы его на 3 или, например, на 2 или 4. Проницательные читатели могут сказать: «Но подожди, Исаак! Количество вызовов новой функции не будет равно 2 ^ n в точности, поскольку мы уменьшаем n с каждым вызовом
функции! » И это правда. Фактическое число, которое мы должны использовать во время выполнения, называется золотым сечением и эквивалентно примерно 1,6. Но ради этого поста я округлю его до 2. (я знаю, что мы много обобщали,
, абстрагировали и приближали, но это необходимо для того, чтобы сделать проблему более управляемой). Таким образом, наша сложность скорости для медленного метода в среднем составляет O (2 ^ n). Это прекрасная скорость, когда n довольно мало,
но подумайте, насколько огромной она может стать, когда n приближается к бесконечности! Я даже не хочу об этом думать, мозг болит :(.

Теперь попробуем вычислить время работы более быстрого метода. Сначала у нас есть вызов метода fast_fibonacci (n). Это, как и раньше, занимает время O (1).
В следующих 4 строках мы создаем переменные и привязываем их к значениям. Каждый из них занимает O (1) раз, всего O (4) раз. Однако, как и раньше, это время O (4) будет обобщено до времени O (1). Далее у нас есть цикл while! Каждый раз, когда мы вызываем цикл while, мы должны проверять условие, что занимает O (1) раз. Затем мы должны присвоить 4 переменным новым значениям, что занимает O (4) - ›O (1) раз. Сделаем это примерно n раз, так как цикл повторяется n - 2 раза. Таким образом, мы выполняем операцию за O (1) n - 2 раза! Это займет у нас время O (n - 2), что приблизительно равно времени O (n). Мы называем этот тип скорости линейной, так как зависимость между скоростью O (n) и n может быть построена на
прямой. Что я и сделал ниже!

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

Как видим, сюжеты практически идентичны! Таким образом, мы можем видеть, что, когда n очень мало, два метода работают с относительно одинаковой скоростью. Однако мы можем видеть, что очень быстро более медленный метод начинает занимать значительно более длительный период времени. Я перестал собирать данные примерно при n = 46, так как
медленный метод начал вычислять больше минуты, а я нетерпеливый бездельник.

При этом я надеюсь, что это был показательный пример того, как можно попробовать анализ времени выполнения!

Я приветствую других попробовать то же самое с их собственными программами и проверить в Интернете, может быть, есть более быстрый способ сделать это! Спасибо за чтение, друзья: ^).

Используемые ресурсы:
- https://matplotlib.org/users/pyplot_tutorial.html (используется для создания моих графиков)
- https://pythonprogramming.net/loading-file-data- matplotlib-tutorial / (по той же причине, что и выше)
- https://stackoverflow.com/questions/13440020/big-o-for-various-fibonacci-implementations (используется для подтверждения моего анализа,
Боже, я бы чувствовал себя глупо, если бы ошибался, ха-ха.)

Дополнительная литература:
- http://bigocheatsheet.com/ (отлично подходит для кодирования интервью)
- https://medium.freecodecamp.org/my-first-foray-into-technology- c5b6e83fe8f1
- https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/ (два блога с отличным содержанием)