Работающий программист

Статья
07/03/2015

Наука о компьютерах

Исходный код можно скачать по ссылке.

Ted Neward В течение многих лет я слышу от коллег, как они позиционируют себя «компьютерными учеными». Мне также доводилось слышать, что «любая область исследований, в название которой приходится включать слово "наука", на самом деле таковой не является». Определенно весьма большое количество людей, занимающихся тем же, что и я, не проходили формального обучения в компьютерных науках, а еще одна немалая часть с отвращением смотрит на работы, выходящие из стен университетов, — и не без оснований, между прочим. Когда это куча греческих символов, описывающих систему типов, помогла вам создать и вывести в рабочий режим хоть какое-нибудь бизнес-приложение?

Я знаком с некоторыми невероятно умными людьми, и один из них — Джо Хаммел (Joe Hummel), который с полным правом может называть себя ученым в области компьютерных наук, имеет ученое звание и прочее. Я попросил его присоединиться ко мне в написании этой статьи, чтобы исследовать мир компьютерных наук. Я подумал, что было бы интересно начать с каких-то более простых частей компьютерных наук и показать, как понимание теорий, стоящих за некоторыми из этих частей, может чуточку облегчить жизнь программисту-работяге.

В этой статье мы энергично вклинимся в классическую дискуссию «Big O» (О большое), суть которой — в поиске согласованного способа описания простой концепции: сколько ресурсов (времени, памяти, электроэнергии и прочего) понадобится компьютеру для выполнения данной программы? Это определение называют анализом алгоритмов. Он предназначен для того, чтобы отнести некий алгоритм к конкретной математической категории. Зачем? Чтобы вы могли выбрать лучший алгоритм в конкретной ситуации. Категорий много, и каждая последующая категория характеризуется скачком в потреблении ресурсов. Мы сосредоточимся на времени выполнения и только первых трех категориях: O(1), O(lgN) и O(N). По традиции, N обозначает число элементов данных, обрабатываемых алгоритмом. Сводную иллюстрацию того, куда мы идем со всем этим, см. на рис. 1, где показано время выполнения, которое можно ожидать в каждой категории по мере роста N.

Execution Times as the Number of Items Processed (N) Grows
Рис. 1. Время выполнения в зависимости от роста количества обрабатываемых элементов (N)

A Few of the Big O Categories (slower growth is better)	Несколько категорий О большого (чем медленнее рост, тем лучше)
Time	Время

A Few of the Big O Categories (slower growth is better) Несколько категорий О большого (чем медленнее рост, тем лучше) Time Время

Алгоритм N-ого порядка пишется как O(N), произносится как «Big O of N» и также называется линейным. При N количестве элементов данных алгоритм O(N) требует порядка N временных отрезков. Алгоритм порядка log N пишется как O(lgN), произносится как «Big O of log N» и называется логарифмическим. При N количестве элементов данных алгоритм O(lgN) требует порядка log2(N) временных отрезков (намного меньше). Наконец, алгоритм первого порядка пишется как O(1), произносится как «Big O of 1» и называется постоянным. При N количестве элементов данных алгоритм O(1) требует постоянного числа временных отрезков (еще меньше). Давайте вернемся к рис. 1. О чем еще говорит этот график? Например, обратите внимание на то, что при удвоении N линейный алгоритм выполняется в два раза дольше.

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

List<string> suspicious = BuildList(); /* шаг 0 */
foreach (string line in logfile)
{
  string ipaddr = parse(line);         /* шаг 1 */
  if (suspicious.Contains(ipaddr))     /* шаг 2 */
    matches++;                         /* шаг 3 */
}

К какой категории следует отнести временную сложность этого алгоритма? Предположим, что в журнале M строк, а в списке N подозрительных IP-адресов. Формирование несортированного списка из N элементов (шаг 0) повлечет за собой разовые издержки O(N). Цикл выполнит M итераций, поэтому издержки цикла составят O(M * издержки одной итерации). Каждая итерация требует выполнения трех основных шагов.

Разбор строки.
Поиск по списку.
Приращение числа совпадений, если совпадение найдено.

Начинаем анализировать

Интеллектуальный аспект анализа алгоритма заключается в учете того, что надо учитывать, и игнорировании того, что надо игнорировать. Например, хотя разбор строки (возможно, с помощью регулярного выражения или разбиения строки на лексемы), может оказаться дорогостоящим, это занимает постоянное время относительно данных. Иначе говоря, время, необходимое на разбор строки, остается совершенно неизменным, сколько бы строк ни было в файле журнала — M или 2M. Никак не повлияет на него и количество подозрительных IP-адресов — N или 2N. Таким образом, мы говорим, что шаги 1 и 3 занимают c (constant) времени. Однако шаг 2 (поиск по списку) действительно зависим от количества подозрительных IP-адресов:

if (suspicious.Contains(ipaddr))

Метод Contains выполняет линейный поиск, начиная с первого элемента и продолжая до тех пор, пока не найдет совпадение или не будет достигнут конец списка. (Откуда мы смогли об этом узнать? Одним из трех способов: мы тестировали, смотрели на исходный код или читали документацию в MSDN Library.)

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

Поскольку константы отбрасываются при вычислении порядка, поиск представляется как O(N) в любом случае, давая для цикла сложность O(M * N). В свою очередь это позволяет получить общую алгоритмическую сложность:

= O(build + loop)
= O(N + M * N)
= O( (1 + M) * N )
= O(M * N)

Итак, первая версия нашего решения требует O(MN) времени.

Дайте мне данных, да побольше!

Первый вопрос, который следует задать самим себе: «Нужен ли нам более эффективный алгоритм?». M — обычно большое значение, исчисляемое в миллионах (возможно, миллиардах) строк. С этим вы ничего особенного сделать не можете, потому что при поиске нужно проверять каждую строку. Если N, число подозрительных IP-адресов, невелико (скажем, N < 100), то ваша работа закончена. На нынешних быстрых компьютерах вы практически не заметите разницы между M и 100M временных отрезков. Однако с ростом значения N (например, когда N >> 100, или значительно больше 100), стоит подумать о других алгоритмах поиска. (Кроме того случаях, когда у вас по-настоящему очень большой бюджет на закупку оборудования; иногда бывает и так.)

Более эффективный алгоритм — двоичный поиск, при котором вы прыгаете в середину, а затем идете влево или вправо в зависимости от того, меньше или больше элемент, который вы ищете, чем элемент в середине. Каждый раз деля пополам пространство поиска, алгоритм показывает поведение O(lgN). Что это означает на практике? При N=1000 элементов в худшем случае для двоичного поиска потребуется порядок 10 временных отрезков (2¹⁰ ≈ 1000), тогда как линейный поиск — 1000. При N = 1 000 000 разница будет еще радикальнее — на порядок 20 временных отрезков против миллиона. Основной недостаток в том, что для двоичного поиска данные должны быть отсортированы по порядку. Вот программа поиска по файлу журнала, переписанная под использование двоичного поиска (изменения выделены полужирным):

List<string> suspicious = BuildList();      /* шаг 0 */
suspicious.Sort();                          /* шаг 0.5 */
foreach (string line in logfile)
{
  string ipaddr = parse(line);               /* шаг 1 */
  if (suspicious.BinarySearch(ipaddr) >= 0)  /* шаг 2 */
    matches++;                               /* шаг 3 */
}

Сортировка списка suspicious (шаг 0.5) дает разовые издержки O(NlgN), тогда как издержки каждой итерации уменьшаются с O(N) до O(lgN) с учетом большей эффективности двоичного поиска (шаг 2). В итоге общая алгоритмическая сложность такова:

= O(build + sort + loop)
= O(N + N * lgN + M * lgN)
= O(N * (1 + lgN) + M * lgN)
= O(N * lgN + M * lgN)
= O((N + M) * lgN)

В нашем сценарии, где M >> N, N выступает скорее в роли малой константы, когда добавляется к M, и поэтому вторая версия нашего решения требует примерно O(MlgN) времени. И что? При N = 1000 подозрительных IP-адресов мы только что сократили время выполнения от порядка 1000M шагов до 10M, что быстрее в сто с лишним раз.

Попробуем хеширование

Когда вам что-то известно о данных, по которым вы выполняете поиск, вы можете (и должны) создавать хеш-таблицу. Хеширование сокращает среднее время поиска до O(1) — и добиться лучшего результата уже попросту нельзя. Делается это сопоставлением единственного значения с элементами, хранящимися в таблице, и это значение создается хеш-функцией. Основное требование для хеширования — наличие хорошей хеш-функции, которая сопоставляет данные поиска через диапазоны целых чисел с небольшим количеством коллизий (дублированными сопоставлениями). Очередная (третья) версия нашей программы используцет преимущества встроенной поддержки эффективного хеширования строк в Microsoft .NET Framework (изменения выделены полужирным):

Dictionary<string, int> suspicious = BuildHashTable();  /* step 0 */
foreach (string line in logfile)
{
  string ipaddr = parse(line);              /* шаг 1 */
  if (suspicious.ContainsKey(ipaddr))       /* шаг 2 */
    matches++;                              /* шаг 3 */
}

Создание хеш-таблицы (шаг 0) влечет разовые издержки O(N). Это дает общую алгоритмическую сложность:

= O(build + loop)
= O(N + M * 1)
= O(N + M)

Предполагая, что в нашем сценарии M >> N, версия 3 является самым быстрым решением, требуя на выполнение примерно O(M) времени. При N = 1000 подозрительных IP-адресов мы только сократили время выполнения еще на один порядок (в 10 раз), что в тысячу с лишним раз быстрее исходной версии. Что примечательно в этом подходе — даже при больших значениях N (скажем, 10 000 или 100 000) время выполнения остается тем же, на порядке M временных отрезков.

Так в чем же подвох? С версией 2 и двоичным поиском все просто: список IP-адресов нужно сначала отсортировать. В версии с хешированием есть три вопроса, которые следует продумать: создание эффективной хеш-функции, издержки предварительного конструирования и больший объем используемой памяти. Главный из них — хеш-функция. Эффективная хеш-функция распределяет данные по таблице с минимальным количеством коллизий, исключая необходимость в дополнительном поиске после начального хеширования в таблицу. Такая функция обеспечивает издержки предварительного конструирования в O(1) на каждую единицу данных, или O(N), что идентично издержкам линейного поиска. Однако такая эффективность, как правило, включает коэффициент нагрузки (load factor) приблизительно в 10%, т. е. данные занимают лишь 10% таблицы. Таким образом, хеширование требует в десять с лишним раз больше памяти, чем линейный и двоичный поиск, хотя формально этот алгоритм все равно относится к категории O(N), как и другие.

И зачем мы все это делаем?

После всей этой псевдоматематики у выпускника университета, не имеющего отношения к компьютерным наукам, могло сложиться впечатление, что мы проделали уйму теоретической работы, но, пока мы думали, что ищем эффективное решение, мы наверняка отбросили много констант. И это подводит нас к вопросу на миллион долларов: «А окупится ли на практике наш теоретический анализ?». Хороший вопрос, особенно если вспомнить о конечной цели этой статьи: подтолкнуть читателей к использованию анализа алгоритмов (если вы еще не занимались им) для оценки конкурирующих подходов перед реализацией одного из них в коде.

Сколько раз мне доводилось сиживать за столом и наблюдать, как инженеры часами (а то и днями) спорят о том, какой подход лучше — A или B. И редко кто берет салфетку со стола и по-быстрому делает прикидки с помощью алгоритмического анализа.

Так что теперь, когда мы покончили с анализом, давайте-ка прогоним кое-какие тесты и посмотрим, что будет на практике. Для этого мы случайным образом сгенерировали файлы журналов с M записей, а затем провели поиск по этим файлам с применением случайным образом сгенерированных списков из N количества IP-адресов. (Полный исходный код и входные файлы доступны по ссылке bit.ly/srchlogfiles.)

Напомню, что, предполагая M >> N, мы получили алгоритмические сложности, показанные в табл. 1.

Табл. 1. Алгоритмические сложности, если M >> N

	Время (t)
Версия 1: линейный поиск	O(M * N)
Версия 2: двоичный поиск	O(M * lgN)
Версия 3: использование хеширования	O(M)

Для наших тестов мы выбрали M, равным миллиону, и удваивали N для каждого теста: 128, 256, 512 и т. д. Удваивание N наглядно высвечивает рабочие характеристики алгоритмов поиска. Если наш анализ точен, то при каждом удваивании N время выполнения должно изменяться, как показано в табл. 2.

Табл. 2. Предсказываемое изменение во времени выполнения при удваивании N

	Время для 2N
Версия 1	O(M * 2 * N) => 2 * O(M * N) => 2t
Версия 2	O(M * lg(2N)) => O(M * (lg2 + lgN)) => O(M * (1 + lgN) => O(M + M * lgN) => M + O(M * lgN) => M + t
Версия 3	O(M) => t

Иначе говоря, версия 1 должна выполняться в два раза дольше (2t), версия 2 должна потребовать другие M временных отрезков (t + M), а версия 3 вообще не должна потребовать дополнительного времени (t). Реально зафиксированное время (в секундах) показано в табл. 3.

Табл. 3. Реальное время выполнения (в секундах)

M	N	Версия 1	Версия 2	Версия 3
1 000 000	128	3,81	2,88	2,15
	256	5,65	2,98	2,15
	512	9,39	3,11	2,17
	1024	16,78	3,23	2,19
	2048	31,52	3,36	2,19
	4096	61,18	3,49	2,28
	8192	120,63	3,68	2,39
	16 384	238,86	3,95	2,54
	32 768	473,91	4,34	2,89

Как видно из табл. 3, в версии 1, основанной на линейном поиске, время выполнения действительно удваивается при удваивании N. По-видимому, в большинстве ситуаций это плохо.

Версия 2, основанная на двоичном поиске, выполнялась на порядки быстрее версии 1, и время ее выполнения росло гораздо медленнее. Скорость этого роста (или замедления) труднее оценить количественно, так как она зависит от времени TM, необходимого для выполнения M операций, которое может произвольно варьироваться в пределах 0,1–0,3 секунд. Согласно нашему анализу, время выполнения версии 2 должно увеличиваться с постоянной скоростью TM по мере удваивания N, но на деле это было не так; это может быть результатом возрастающего давления на кеш (и соответственно большего числа промахов кеша) по мере увеличения N.

Наконец, табл. 3 подтверждает, что версия 3 — действительно самый быстрый алгоритм, причем время выполнения слабо зависит от N (хотя оно и не является константой).

Поиск баланса

С прагматической точки зрения, не совсем очевидно, что улучшение в версии 3 по сравнению с версией 2 стоит особых усилий, несмотря на экономию более секунды. Потенциальная экономия на практике не дает заметной разницы, пока вы не имеете дела с действительно большими значениями M или N (учитывайте, что хеширование может потребовать под хранение IP-адресов в десять с лишним раз больше памяти). И это подводит нас к последнему принципу: всегда вовремя останавливайтесь в поиске оптимизаций. Поиск абсолютно быстрейшего алгоритма выполнения какой-либо операции может быть интересным и захватывающим для программиста, но, если эта операция не выполняется прямо перед носом пользователя, время, проведенное в попытках выжать еще чуток скорости, зачастую можно потратить гораздо продуктивнее на какую-нибудь другую работу. Скачок в производительности между версиями 1 и 2 явно стоит потраченного времени (экономия достигает примерно 10000%), но во всем остальном программист должен искать баланс. Иногда теория должна уступить дорогу практике, но чаще она все же подсказывает, на чем стоит сосредоточить свои усилия в практической работе.

Удачи в кодировании!

Тэд Ньюард (Ted Neward) — консультант по архитектуре в компании Neudesic LLC. Автор и соавтор многочисленных книг, в том числе «Professional F# 2.0» (Wrox, 2010), более сотни статей, часто выступает на многих конференциях по всему миру; кроме того, имеет звание Microsoft MVP в области C#. С ним можно связаться по адресу ted@tedneward.com, если вы заинтересованы в сотрудничестве с его группой. Также читайте его блог blogs.tedneward.com.

Джо Хаммел (Joe Hummel) — частный консультант, сотрудник инженерно-технического отдела в Pluralsight LLC, тренер в MVP-Training.net, а также приглашенный научный сотрудник на факультете компьютерных наук в Университете Калифорнии (Ирвин). Получил в этом университете звание кандидата наук в области высокопроизводительных вычислений и интересуется всем, что связано с параллельными вычислениями. Живет в окрестностях Чикаго, и, когда он не занимается парусным спортом, с ним можно связаться по адресу joe@joehummel.net.