Книга: Программист-прагматик. Путь от подмастерья к мастеру

Скорость алгоритма на практике

Скорость алгоритма на практике

Маловероятно, что в своей профессиональной карьере вам придется тратить много времени на написание программ сортировки. Эти программы, входящие в стандартные библиотеки, наверняка без особых усилий превзойдут написанное вами. Но основные типы алгоритмов, описанные выше, будут время от времени всплывать на поверхность. Во всех случаях, когда вы пишете простой цикл, знайте, что имеете дело с алгоритмом О(n). Если же этот цикл содержит внутренний цикл, то речь идет о О(m*n). Вы обязаны задаться вопросом: а насколько велики эти значения? Если эти значения ограничены сверху, то вы можете представить, сколько времени потребуется на выполнение программы. Если эти цифры зависят от внешних факторов (наподобие количества записей в запускаемом на ночь пакете программ или количества фамилий в списке персоналий), то стоит остановиться и изучить влияние больших чисел на время выполнения программы или объемы необходимой памяти.

Существует несколько подходов, которыми вы можете воспользоваться при решении потенциально возникающих проблем. Если есть алгоритм, являющийся O(n^2), попробуйте действовать по принципу «разделяй и властвуй», что может уменьшить время выполнения до O(nlg(n)).

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

Стоит рассмотреть и то, что происходит в самой программе. При малых значениях n простой цикл O(n^2) может работать намного лучше, чем сложный О(nlg(n)), особенно если последний содержит ресурсоемкий внутренний цикл.

Говоря о теории, не стоит забывать и о практических соображениях. При работе с небольшими массивами входных данных может показаться, что время выполнения возрастает линейно. Но если программа обрабатывает миллионы записей, то внезапно время выполнения резко увеличивается, по мере того как система начинает «буксовать». При проведении тестирования программы сортировки со случайными входными ключами вы можете удивиться ее работе с упорядоченным входным массивом. Прагматики стараются обеспечивать как теоретическую, так и практическую базу. После всех проведенных оценок единственной определяемой временной характеристикой является скорость выполнения вашей программы в реальных условиях эксплуатации и с реальными данными [38]. Из этого следует следующая подсказка.

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

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

Кроме того, необходимо опасаться преждевременной оптимизации. Перед тем как потратить ваше драгоценное время на улучшение алгоритма, всегда есть смысл убедиться, что он действительно является «узким местом».

• Оценка

• Каждый разработчик должен обладать чутьем на проектирование и анализ алгоритмов. По данному предмету Роберт Седжвик написал серию доступных книг ([Sed83, SF96, Sed92]и др.). Мы рекомендуем пополнить вашу библиотеку одной из этих книг и обязательно прочесть ее.

• Те, кто интересуется данным предметом более глубоко (по сравнению с его подачей в книге Седжвика), могут прочесть каноническую серию книг Дональда Кнута «Искусство программирования», в которых анализируются разнообразные алгоритмы [Knu97a, Knu97b, Ктш98].

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

34. Авторы книги составили набор простых программ сортировки, которые можно загрузить с их Интернет-сайта (www.pragmaticprogrammer.com). Прогоните эти программы на разных компьютерах, имеющихся в вашем распоряжении. Соответствуют ли полученные вами данные ожидаемым кривым? Какие заключения можно сделать об относительных скоростях ваших машин? Каково влияние различных установочных параметров компиляторов? Является ли поразрядная сортировка действительно линейной? (Ответ см. в Приложении В.)

35. Приведенная ниже подпрограмма выводит на печать содержимое двоичного дерева. Предполагая, что дерево сбалансировано, какой (примерно) объем стека будет использоваться подпрограммой для вывода на печать дерева, состоящего из 1000000 элементов? (Предполагается, что вызовы подпрограммы не оказывают существенной нагрузки на стек). (Ответ см. в Приложении В.)

void printTree(const Node *node) {

char buffer[1000];

 if (node) {

   printTree(node->left);

   getNodeAsString(node, buffer);

   puts(buffer);

   printTree(node->right);

 }

}

36. Существует ли способ уменьшить потребность подпрограммы, описанной в упражнении 35, в ресурсах стека (помимо уменьшения размера буфера)? (Ответ см. в Приложении В.)

37. В разделе «Оценка с точки зрения здравого смысла» утверждается, что алгоритм двоичного поиска является O(lg(n)). Можно ли это доказать? (Ответ см. в Приложении В.)

Оглавление книги