Эндрю Хант - Программист-прагматик. Путь от подмастерья к мастеру

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

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

Ответ: Программа printTree использует приблизительно 1000 байт стекового пространства для буферной переменной. Для движения вниз по древовидной схеме она рекурсивно вызывает саму себя, и каждый вложенный вызов добавляет еще 1000 байт к стеку. Она также вызывает саму себя, когда добирается до вершин, но заканчивает работу сразу, как только обнаружит, что переданный указатель обнулен. Если глубина дерева равна D, то максимальный объем, необходимый стеку, составляет (грубо) 1000 x(D+ 1).

Сбалансированное двоичное дерево содержит вдвое больше элементов на каждом уровне. Дерево глубиной D содержит 1+2+4+8 +… +2^(D-1), или 2^D – 1 элементов. Следовательно, дереву, состоящему из миллиона элементов, будет необходимо [lg(1000001], или 20 уровней.

Поэтому мы рассчитываем, что наша подпрограмма будет использовать примерно 21000 байт стекового пространства.

Ответ: На ум приходит несколько процедур оптимизации. Программа printTree вызывает саму себя на вершинах дерева лишь для того, чтобы закончить работу при отсутствии потомков. Этот вызов увеличивает максимальную глубину стека примерно на 1000 байт. Можно также исключить рекурсию хвоста (второй рекурсивный вызов), хотя это и не будет затрагивать использование стека в наихудшем случае.

while (node) {

if (node->left) printTree(node->left);

getNodeAsString(node, buffer);

puts(buffer);

node = node->right;

}

Но самая большая выгода возникает при назначении одного-единственного буфера, доступ к которому осуществляется при всех обращениях к printTree. Если передать этот буфер в виде параметра для рекурсивных обращений, то будет назначено всего 1000 байт вне зависимости от глубины рекурсии.

void printTreePrivate(const Node *node, char *buffer) {

if (node) {

printTreePrivate(node->!eft, buffer);

getNodeAsStringfnode, buffer);

puts(buffer);

printTreePrivate(node->right, buffer);

}

}

void newPrintTree(const Node *node) {

char buffer[1000];

printTreePrivate(node, buffer);

)

Ответ: Это можно сделать двумя путями. Один из них заключается в том, чтобы перевернуть проблему с ног на голову. Если в массиве есть лишь один элемент, мы не осуществляем итерации в цикле. Каждая дополнительная итерация удваивает размер массива, в котором можно осуществлять поиск. Отсюда общая формула размера массива: n = 2^m, где m – число итераций. Если прологарифмировать обе части с основанием 2, получим выражение lg(n) = lg(2^m), которое из определения логарифма превращается в lg(n) =m.

Ответ: Здесь мы могли бы предложить весьма умеренную реструктуризацию: убедитесь, что каждый тест выполняется лишь один раз, и сделайте все вычисления стандартными. Если выражение 2*basis (…)* 1.05 появляется в других местах программы, то, вероятно, его стоит сделать функцией. В данном случае мы этого делать не стали.

Мы добавили массив rate_lookup, инициализированный таким образом, что элементам, отличным от Texas, Ohio и Maine, присвоено значение 1. Этот подход облегчает добавление значений для других штатов в будущем. В зависимости от ожидаемой схемы использования мы могли бы сделать поле points также средством поиска в массиве.

rate = rate_lookup[state];

amt = base * rate;

calc = 2*basis(amt) + extra(amt)*1.05;

if (state == OHIO)

points = 2;

Ответ: Когда вы видите, что кто-либо использует перечислимые типы (или эквивалентные им в языке Java), для того чтобы провести различие между вариантами некоего типа, во многих случаях вы можете улучшить программу за счет создания подклассов: