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

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

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

Ниже приводится один из способов реализации функции f indCubicleNumber; при этом объект тар взят из стандартной библиотеки шаблонов (Standard Template Library - STL, см. правило 35) и используется в качестве местного кэша:

int findCubicleNumber(const strings employeeName) {

Определите статический объект map (имя служащего, номер комнаты) . Этот объект - локальный кэш данных, typedef map<string, int> CubicleMap; static CubicleMap cubes;

Попытайтесь найти пункт employeeName в кэше; затем итератор STL it укажет на найденную ячейку, если она существует (см. подробности в правиле 35) .

CubicleMap::iterator it = cubes.find(employeeName);

Значение it будет равно cubes.end(), если ячейка не найдена

(это стандартная реакция STL). В таком случае обратитесь

за номером комнаты, затем добавьте его в кэш.

if (it == cubes.end()) {

int cubicle =

результат поиска номера ячейки employeeNames в базе данных;

cubes [employeeName] = cubicle; Добавьте пару

(employeeName, cubicle) в кэш.

return cubicle; }

else {

it указывает на корректный элемент кэша (имя сотрудника, номер комнаты). Вам нужен только второй компонент, то есть компонент second.

return (*it).second;

* В июле 1995 года комитет ISO/ANSI по стандартизации языка С++ добавил требование, согласно которому большинство итераторов STL должны поддерживать оператор->, так что выражение it-> second должно теперь работать. Однако некоторые реализации STL не соответствуют данному требованию, поэтому пока чаще используется конструкция {*it) .second.

Постарайтесь не углубляться в подробности кода STL (которые будут более ясными после того, как вы прочитаете о правиле 35). Вместо этого сконцентрируйтесь на общей стратегии данной функции. Она состоит в том, чтобы использовать локальный кэш для замены сравнительно дорогих запросов из базы данных дешевым поиском в структуре данных, находящейся в оперативной памяти. Если предположение о том, что номера комнат будут запрашиваться часто, верно, то использование кэша в функции f indCubicleNumber должно привести к сокращению средних затрат на определение номера комнаты служащего.

(Один нюанс кода все же требует объяснения. Последний оператор возвращает (* it) . second вместо обычного it->second. Почему? Это связано с соглашениями, которым следует STL. В двух словах, итератор it является объектом, а не указателем, поэтому нет гарантии, что оператор -> может применяться Kit*. Спецификации STL требуют, чтобы операции . и * были допустимы для итераторов, так что конструкция (* it) . second, буд5и синтаксически громоздкой, гарантированно работает.)

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

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

template<class Т> Шаблон для динамических

class DynArray {...); массивов.

DynArray<double> а; Пока только а[0]

является правильным

элементом массива. а[22] = 3.5; Массив а автоматически

расширяется:

допустимые индексы 0-22. а[32] = 0; Массив а расширяется снова;

теперь допустимы индексы а[0]-а[32] .

Как же объект DynArray расширяется? Можно было бы просто выделить столько дополнительной памяти, сколько необходимо, например, так:

template<class Т>

Т& DynArraY<T>::operator[](int index) {

if (index < 0) { поднять исключения; II Отрицательные индексы

} все еще недопустимы,

if (index > текущего ыа.кси1ла.льното значения индекса) ( Вызов new, для того чтобы выделить достаточный объем дополнительной памяти и тем самым сделать индекс допустимым; }

return элемент массива с индексом index; }

При таком подходе оператор new вызывается каждый раз, когда требуется увеличить размер массива, но запросы new вызывают функцию operator new (см. правило 8), а вызовы функций operator new (и operator delete) достаточно дороги . Дело в том, что они обычно приводят к системным вызовам, которые выполняются медленнее, чем вызовы функций внутри процесса. Поэтому лучше сократить число системных вызовов до минимума.

Стратегия сверхэнергичного вычисления опирается на следующее рассуждение: если необходимо увеличить размер массива для того, чтобы он соответствовал индексу i, то по принципу локальной взаимосвязанности, вероятно, придется увеличивать его и в будущем, чтобы он соответствовал какому-либо другому индексу, немного большему, чем i. Избежать затрат на выделение памяти во время второго (ожидаемого) увеличения можно, если сразу сделать размер массива DynArray настолько большим, чтобы последующие увеличения оказались в пределах предусмотренного диапазона. Например, можно записать DynArray: : operator [ ] следующим образом:

template<class Т>

Т& DynArray<T>::operator[](int index) {

if (index < 0) сгенерировать исключение;

if (index > текущего максимального значения индекса) { int dif f = index - текущее максимальное значение индекса; вызов new, чтобы предоставить достаточно дополнительной памяти и тем самым сделать index+diff действительным; }

return элемент массива с индексом index; }

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