Что такое “анализ алгоритмов”?¶

Студенты-первокурсники ИТ-специальностей очень часто сравнивают плоды своих трудов с другими. Вы могли замечать, что быть похожими друг на друга - общее свойство многих компьютерных программ, особенно простых. В связи с этим возникает интересный вопрос: если две программы решают одну и ту же задачу, но выглядят по разному, то как понять, что одна из них лучше?

Чтобы на него ответить, нам нужно вспомнить о важном различии между собственно программой и алгоритмом, который она воплощает. Как мы говорили в главе 1, алгоритм - это универсальная пошаговая инструкция по решению задачи. Это метод для решения любого частного её случая, который при заданных входных значениях всегда выдаёт требуемый результат. С другой стороны, программа - это то, как алгоритм переложен на некий язык программирования. Может существовать множество программ, реализующих один и тот же алгоритм в зависимости от программиста и языка, который он использует.

Для дальнейшего исследования этого различия рассмотрим функцию в ActiveCode 1. Она решает всем знакомую задачу вычисления суммы первых \(n\) целых чисел. Алгоритм использует идею переменной-аккумулятора, которая инициализируется нулём. В процессе решения перебираются \(n\) чисел, каждое из которых прибавляется к аккумулятору.

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

В заданном ранее вопросе мы спрашивали: как понять, что одна функция лучше другой? Ответ будет зависеть от выбранных критериев. Функция sumOf, естественно, лучше, чем foo, если вы беспокоитесь о читабельности. Фактически, вы, возможно, видели множество подобных примеров в ваших вводных курсах по программированию, поскольку одной из их целей является желание помочь вам научиться писать программы, которые легко читать и понимать. Однако, в этом курсе мы заинтересованы в том, чтобы охарактеризовывать алгоритм сам по себе. (Но мы всё равно надеемся, что вы продолжите бороться за хорошо читаемый и понимаемый код.)

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

На данный момент становится важным поразмыслить над тем, что же мы подразумеваем под “вычислительными ресурсами”. Существует два различных подхода к этому вопросу. Первый рассматривает объём пространства или памяти, требуемый алгоритму для решения задачи. Эта величина обычно зависит от её конкретного частного случая. Однако, часто встречаются алгоритмы, имеющие специфические требования к объёму, и тогда нам надо очень аккуратно подходить к объяснению вариантов.

Альтернативой требований к пространству является анализ и сравнение алгоритмов по времени, которое необходимо им для вычислений. Эту величину иногда называют “временем выполнения” алгоритма. Одним из способов измерить время выполнения функции sumOfN является проведение сравнительного анализа. Он подразумевает, что мы засечём реальное время, требуемое программе на вычисление результата. В Python можно проделать эту операцию, отметив время начала и время окончания работы программы относительно используемой нами системы. В модуле time есть функция time, которая возвращает текущее системное время в секундах, прошедшее с некоторого произвольно выбранного начального момента. Вызвав эту функцию дважды - в начале и в конце, - и затем посчитав разницу, мы получим точное количество секунд (дробное в большинстве случаев), затраченных на выполнение.

Листинг 1

import time

def sumOfN2(n):
   start = time.time()

   theSum = 0
   for i in range(1,n+1):
      theSum = theSum + i

   end = time.time()

   return theSum,end-start

Листинг 1 демонстрирует оригинальную функцию sumOfN с вызовами времени, встроенными до и после суммирования. Она возвращает кортеж, состоящий из результата и количества затраченного на вычисления времени (в секундах). Если мы выполним пять вызовов функции, в каждом из которых будет вычисляться сумма первых 10000 целых чисел, то мы получим следующее:

>>>for i in range(5):
       print("Sum is %d required %10.7f seconds"%sumOfN(10000))
Sum is 50005000 required  0.0018950 seconds
Sum is 50005000 required  0.0018620 seconds
Sum is 50005000 required  0.0019171 seconds
Sum is 50005000 required  0.0019162 seconds
Sum is 50005000 required  0.0019360 seconds

Мы выяснили, что результат хорошо повторяем и что на выполнение кода затрачивается примерно 0,0019 секунд. Что, если теперь мы сложим первые 100000 целых?

>>>for i in range(5):
       print("Sum is %d required %10.7f seconds"%sumOfN(100000))
Sum is 5000050000 required  0.0199420 seconds
Sum is 5000050000 required  0.0180972 seconds
Sum is 5000050000 required  0.0194821 seconds
Sum is 5000050000 required  0.0178988 seconds
Sum is 5000050000 required  0.0188949 seconds
>>>

Снова времена, необходимые для каждого запуска, лежат близко друг к другу, но становятся длиннее - примерно в десять раз. Для n, равной 1000000 мы получим:

>>>for i in range(5):
       print("Sum is %d required %10.7f seconds"%sumOfN(1000000))
Sum is 500000500000 required  0.1948988 seconds
Sum is 500000500000 required  0.1850290 seconds
Sum is 500000500000 required  0.1809771 seconds
Sum is 500000500000 required  0.1729250 seconds
Sum is 500000500000 required  0.1646299 seconds
>>>

Среднее значение вновь выросло примерно в десять раз, по сравнению с предыдущим.

А теперь рассмотрим ActiveCode 3, демонстрирующий другой способ решения задачи суммирования. Эта функция, sumOfN3 использует преимущество замкнутой формулы \(\sum_{i=1}^{n} i = \frac {(n)(n+1)}{2}\) для вычисления суммы первых \(n\) целых без выполнения итераций.

Если мы проведём аналогичные контрольные замеры для sumOfN3, используя пять различных значений для n (10 000, 100 000, 1 000 000, 10 000 000 и 100 000 000), то получим следующие результаты:

Sum is 50005000 required 0.00000095 seconds
Sum is 5000050000 required 0.00000191 seconds
Sum is 500000500000 required 0.00000095 seconds
Sum is 50000005000000 required 0.00000095 seconds
Sum is 5000000050000000 required 0.00000119 seconds

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

Но о чём этот тест говорит нам в действительности? Интуитивно мы догадываемся, что итеративное решение будет выполнять больше работы из-за повторения некоего набора программных шагов. Это, скорее всего, причина, по которой оно занимает больше времени. Так же похоже, что время, требуемое итеративному решению, возрастает при увеличении значения n. Тут, однако, возникает проблема. Если мы запустим одну и ту же функцию на разных компьютерах или используем различные языки программирования, то вполне вероятно, что получим разные результаты. Вычисление sumOfN3 займёт тем больше времени, чем старше компьютер.

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