Анализ сложности

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

Под процессами можно понимать реализуемые алгоритмы. Алгоритм в свою очередь можно определить как совокупность операций. Приведем пример алгоритма.

Предположим, что вы играете в прятки с другом. Начитается игра, вы ведете отсчет, а затем начинаете искать своего друга. В первую очередь вы спрашиваете себя: "Как мне быстрее найти друга? Подняться наверх в спальню или сначала проверить чулан на кухне?" Вы можете использовать поуровневый алгоритм, проверив сначала комнаты на первом, а потом на втором этаже; либо использовать покомнатный алгоритм, просто проверяя по пути каждую комнату, от первой до последней, шаг за шагом. Вы можете попытаться прислушаться к звукам, которые, возможно, издает ваш друг.

Предположим, что цель игры – выбрать максимально эффективный алгоритм поиска друга. Поэтому вернитесь на шаг назад и подумайте, какие подходы к решению этой задачи у вас имеются. Какой подход будет самым быстрым? Какой потребует больше времени? Почему один подход лучше или хуже, чем другие? Сколько всего подходов имеется? Как мы определяем один подход и как отличить его от другого? Можем ли мы определить некоторые характеристики каждого подхода, которые позволят нам сказать, что этот подход лучше, чем другие? Если да, каковы эти характеристики? Время? Значение, обратное количеству энергии, необходимой для того, чтобы обойти весь дом? Важно ли нам максимально быстро завершить игру, или можно просто исключить какие-то комнаты из поиска, а потом пойти перекусить? Есть ли какие-то другие факторы, которые мы не учли? Например, что будет, если в самый разгар игры мама позовет нас обедать? Как этот внешний фактор влияют на оценку каждого подхода? Как видим, при измерении производительности нужно учитывать множество разных факторов.

Параметры сравнения процессов

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

  • Полнота: позволяет ли алгоритм гарантированно прийти к решению, если нам известно, что решение существует?

    В приведенном выше примере известно, что наш друг спрятался где-то в доме. Мы ограничили свою задачу простым поиском друга. Но, применяя любой подход для поиска нашего друга, знаем ли мы, что, используя его, мы со 100%-ой гарантией найдем нашего друга? Например, что если, выполняя поиск по этажам, мы не станем заглядывать в страшный и темный подвал? Тогда мы не сможем найти друга, если он спрятался в подвале. Можно будет сказать, что "поэтажный (поуровневый) подход к поиску с исключением страшного подвала" является неполным. Другой вариант: что если наш друг выпрыгнул из окна на улицу? В таком случае, границы нашего поиска будут слишком узки, и друга мы в доме не найдем.

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

  • Время: сколько времени нужно для нахождения решения? Мы можем измерить это время в секундах, миллисекундах или других единицах. Если мы знаем, какие отдельные шаги (или операции) необходимы для выполнения алгоритма, и при этом можем сказать, что знаем, или можем точно оценить время каждого шага, то можно говорить о том, что время – производная от количества шагов, следовательно, свойство "Время" иногда можно понимать как "Количество шагов".

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

  • Пространство: сколько ресурсов нужно для того, чтобы выполнить процесс? Оценка может быть дана на какой-то конкретный момент времени в ходе выполнения процесса, либо это может быть некое агрегированное значение, например, общий объем необходимых ресурсов, либо средний объем необходимых ресурсов. Применительно к компьютерам эта величина чаще всего измеряется тем, сколько виртуальной памяти требует процесс. Виртуальная память обычно понимается как RAM – оперативная память. Общий объем оперативной памяти позволяет определить, сколько процессов можно выполнять одновременно. Если вы выполняете один процесс, который использует всю доступную оперативную память, то компьютер не сможет выполнять другие процессы одновременно, сначала придется дождаться завершения одного процесса, а затем начинать следующий. Ресурс виртуальной памяти, как правило, ограничен исходными техническими характеристиками компьютера. При оценке процесса важно рассчитывать, сколько места этот процесс будет занимать, чтобы определить, сколько еще процессов можно выполнить одновременно, и имеется ли достаточно памяти для того, чтобы одновременно выполнить хотя бы еще один процесс.

    В нашем примере с игрой в прятки можно провести следующую аналогию: насколько занят был наш мозг в тот момент, когда мы выполняли поиск. Предположим, что нас беспокоило бы то, что мы еще не закончили домашнюю работу, или в процессе поиска мы постоянно думали бы о том, как научиться играть на пианино. В таком случае наш мозг был бы занят другими задачами, кроме поиска друга. В нашем мозгу не было бы достаточно памяти, чтобы выполнить задачу по поиску друга. Возможности нашего внимания не безграничны. Если бы поиск не требовал от нас так много внимания и концентрации, мы могли одновременно решать и другие задачи (без ущерба для игры). Но поиск требует от нас максимум внимания, поэтому мы вряд ли сможем решать и другие задачи. Возможно, нам придется на время забыть об игре на пианино, чтобы найти друга. Поскольку до начала какого-либо процесса мы редко можем оценить, сколько внимания нам потребуется, то мы скорее предпочтем процессы, которые не требуют много внимания. Логично, что в процессе поиска решений мы обычно выбираем алгоритмы, требующие минимум внимания.

  • Оптимальность: является ли результатом процесса нахождение наилучшего решения при наличии нескольких решений? Если мы бродим по дому в поисках друга и находим его картонный макет, заканчиваем ли мы игру, заявляя, что нашли его, и считаем ли мы, что это – "достаточно удачное" решение? Оптимальность может предполагать сравнение выбранного подхода с идеальным подходом. Идеального подхода может и не быть, однако, предположим, что он существует.

    Предположим, что наш идеальный подход позволит нам найти друга за 10 шагов (или за 1 минуту, или в пределах другого значения в других единицах измерения). Предположим, что поуровневый подход позволяет нам найти друга за 12 шагов (2 минуты). Это больше и дольше в сравнении с идеальным подходом, т.е. наш подход менее оптимален. Однако предположим, что не знаем идеальное значение (10 шагов, 1 минута). Допустим, у нас есть еще несколько поисковых стратегий, которые занимают больше времени, чем поуровневый подход. Можно сказать, что в этом случае поуровневый подход оптимален, поскольку он настолько близок к идеальному, насколько это возможно.

  • Интуитивность: насколько хорошо мы понимаем процесс (насколько хорошо мы представляем себе, как выполняется процесс)? Этот параметр не является каким-то формальным показателем, который используется в теории и на практике, но его важно учитывать. Например, вспомним упомянутый выше поуровневый подход. Что если я расскажу вам о другом подходе, который называю подходом "черного ящика"? Я не скажу, как он работает, просто утверждаю, что с помощью этого подхода вы точно найдете своего друга. Я даже могу заявить, что это оптимальный подход. Но помните, что это черный ящик, в который вы не сможете заглянуть. Это может быть и робот, которого мы посылаем на поиск (но принцип работы этого робота также не раскрывается). Если вам нужно сравнить простой поуровневый подход с "черным ящиком", что бы вы предпочли? Понятный вам подход? Ответ зависит от ситуации. Иногда "черный ящик" является более приемлемым подходом. Если вы знаете, как жульничать в казино (независимо от того, насколько это неэтично и нелегально), важно ли вам на самом деле знать, как именно работает та или иная хитрая схема? Это субъективный подход, поскольку он зависит от знаний/опыта человека, принимающего решения. Обычно мы предпочитаем объективные меры при выполнении процесса, которые не зависят от того, кто именно выполняет наблюдение. Поэтому это свойство часто игнорируется.

Итак, мы определили некоторые основные характеристики процессов. На практике для обозначения этих характеристик или свойств процесса часто используется термин "измерения". Следовательно, мы можем сказать, что мы рассматриваем производительность процесса с точки зрения измерений полноты (completeness), времени (time), пространства (space) и оптимальности (optimality) (C.T.S.O.). Переставив буквы в этой аббревиатуре, получаем знакомое "COST". Мы сравниваем процессы по COST-свойствам.

Понимание взаимосвязи различных COST-свойств

В зависимости от различных COST-свойств, процессы имеют различные качества. Например, один процесс может быть очень быстрым и завершаться через небольшой промежуток времени. Однако для этого ему может требоваться значительный объем оперативной памяти компьютера. Другими словами, по сравнению с неким абстрактным среднестатистическим процессом, который требует среднее количество времени и ресурсов, он оптимальнее по времени, но при этом он более ресурсоемкий. Как правило, более быстрые процессы требуют больше ресурсов, и наоборот, более медленные процессы требуют меньше ресурсов. Увеличение одного измерения сокращает другое измерение. В ходе проектирования процесса мы можем использовать этот факт так, чтобы итоговый процесс максимально соответствовал нашим задачам. Если нам редко приходится выполнять несколько процессов одновременно, ресурсоемкость процессов не настолько важна для нас. Следовательно, для выполнения нашей задачи можно использовать высокоскоростной процесс, задействующий большой объем оперативной памяти.

Таким образом, обычно справедливы бывают следующие утверждения:

  • При увеличении полноты реализации процесса увеличивается его время ресурсоемкость:

    Уровень важности конечного результата (найти друга) в игре в прятки пропорционально увеличивает количество времени, которое мы должны потратить на поиск. Если для нас не важно, найдем мы друга или нет, мы можем просто прекратить игру сразу после того, как закончим считать. Результат будет неполным, но сам процесс будет очень быстрым.

  • При уменьшении времени увеличивается ресурсоемкость процесса:

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

  • По мере сокращения времени и ресурсоемкости процесса снижается и его интуитивность. Более эффективные алгоритмы, как правило, менее интуитивны. Как бы это ни противоречило нашей с вами логике, на практике бывает именно так. В конце концов, понятно, почему программисты предпочитают использовать Java-скрипт, вместо того, чтобы использовать перфокарты.

  • При увеличении времени увеличивается оптимальность процесса:

    Чем больше времени мы тратим на поиск друга, тем больше шансов его найти (поскольку дом не увеличивается в размерах, его площадь остается постоянной, т.е. дом – это не переменный ресурс).

Подумайте о том, какие последствия будет иметь преобладание одного из измерений. Чем меньше времени мы тратим на какой-то процесс, тем поверхностнее его результат. Предпочитая одно измерение другому, убедитесь, что вы четко представляете себе, как это отразится на других измерениях эффективности процесса.

Анализ сложности

Практики попытались разработать формализованный подход для измерения производительности процессов. Наиболее важных результатов в этой области добились P.G.H. Bachmann, Cook и Karp. Задача по выбору таких формальных метрик предполагает выявление критериев для сравнения. Этот процесс также называется анализом сложности, т.е. изучением того, как можно решить те или иные задачи.

С точки зрения анализа сложности процессов, выделяют два класса задач: P и NP:

  • Задачи класса сложности P – это задачи, которые могут быть решены за полиномиальное время.

    Например, наблюдение за тем, как время, необходимое для решения задачи, связано с количеством шагов, которое нужно предпринять. Если количество времени – y, функция – попытка найти решение, x – число шагов, то формула y=f(x) – это и есть пример задачи класса P. Если x = 1, а f – это функция, например, f(x)=x*1, то y=1*1, следовательно, y=1.

  • Класс NP включает недетерминируемые полиномиальные проблемы разрешимости.

    Проще говоря, в данном случае можно рассматривать ту же формулу, что и выше, но теперь f(x) = x возводится в степень 1 миллиард, или до другого большого количества экспоненциальных шагов. Независимо от технических различий важно отметить, что важно понимать разницу между простым отношением, например, y=n и y=n^2. y=n^2 гораздо медленнее, чем y=2n или y=n. Выражаясь более простыми терминами, существуют алгоритмы (процессы), которые настолько медленные, что иногда очень сложно или вообще невозможно их завершить, в то время как некоторые алгоритмы выполняются достаточно быстро.

В специальной литературе о производительности процессов вы можете встретить распространенное обозначение О (большое О). Например, O(n) означает, что время (или пространство) находится в линейной зависимости от n – числа шагов, необходимых для завершения работы алгоритма.

Другими словами, возвращаясь к примеру с игрой в прятки, если мы знаем, что для одного шага требуется 2 секунды, и если мы выполняем поиск по всему дому, то для завершения процесса поиска требуется O(2n) секунд.

Теперь изменим исходные данные. Предположим, что у нас имеется ограниченный объем энергии, поскольку мы плохо завтракали утром. С каждым шагом мы расходуем нашу энергию; следовательно, для каждого следующего шага требуется больше времени. Допустим, что каждый шаг выполняется в два раза дольше предыдущего. Наш первый шаг занимает 2 секунды, второй – 4, третий – 8 и так далее. 2,4 и 8 – это числа, кратные 2. Это можно представить как 2^1 + 2^2 + 2^3. Время увеличивается в 2^n раз, где n – число шагов. Таким образом, мы можем сказать, что для нашего поиска требуется O(n^2) шагов. Сравним это со сценарием в O(2n) шагов. Во втором случае время увеличивается экспоненциально, а не линейно. После 10 шагов в первом случае мы берем 2*10 секунд (20 секунд), а во втором случае – 2^10 секунд (1024) секунд. 1024-20 равно 1004 секунды. Получаем разницу между требуемыми объемами времени в 1004 секунды. Экспоненциальные задачи занимают значительное количество времени. При каждом следующем шаге расстояние увеличивается. Очевидно, что мы предпочтем процессу O(n^2) процесс O(2n), особенно если мы не уверены, что означает n в начале процесса (до совершения первого шага). В следующий раз, когда вам встретится большое О, вы сможете представить себе масштаб величин.

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