Кэширование вычислений. Преподсчёт

Идея кэширования вычислений заключается в следующем. Пусть нам потребовалось вычислить какое-то значение, и есть вероятность, что это нам потребуется сделать и в будущем. Тогда сохраним данное значение в памяти, и в следующий раз его не придётся считать повторно. Для примера решим такую задачу: нужно написать функцию, которая находит сумму цифр целого неотрицательного числа, не превосходящего 10⁶.

В простейшем варианте функция будет выглядеть так:

 

// Пример 9.2.11 - сумма цифр

int sum_digits(int n)

{

assert(n>=0 && n<=1000000);

int sum = 0;

while (n > 0)

{

sum += n % 10; n /= 10;

}

return sum;

}

 

Однако, если функцию вызвать несколько раз с одним и тем же аргументом, она будет каждый раз вычислять значение заново. Чтобы этого избежать, добавим в функцию статический массив res:

 

// Пример 9.2.12 - сумма цифр с кэшированием вычислений

int sum_digits(int n)

{

assert(n>=0 && n<=1000000);

static int res[1000001];

if (res[n] == 0)

{

int sum = 0;

while (n > 0)

{

sum += n % 10; n /= 10;

}

res[n] = sum;

}

return res[n];

}

 

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

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

Например, для нашей задачи с суммой цифр можно было бы при запуске программы сформировать всю таблицу res целиком − тогда любой последующий запрос будет обработан максимально быстро. Однако, при этом будет наблюдаться некоторая задержка при запуске программы. Можно использовать компромиссный вариант − например, заполнить массив для первых 1000 чисел. Тогда, чтобы получить ответ для числа n до 10⁶, нужно разбить его на две половинки, взять в массиве ответы для этих половинок и сложить.

 

Оптимизация циклов

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

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

Существует целый ряд других подходов к оптимизации циклов − перестановка вложенных циклов местами, объединение, размыкание, развёртывание, расщепление циклов и др. Однако, современные компиляторы в основном умеют самостоятельно применять многие способы оптимизации циклов, поэтому подробно останавливаться на них мы не будем.

 

Использование языка более низкого уровня

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

Для примера рассмотрим следующую задачу: требуется написать максимально быстро работающую функцию, возвращающую количество нулей, которыми оканчивается двоичное представление числа. Существуют разные подходы, как это сделать. Для процессоров x86 один из наиболее эффективных способов состоит в использовании специальной инструкции bsfl. Код с ассемблерной вставкой для компилятора g++ выглядит так:

 

inline unsigned int bsf(unsigned int x)

{

__asm("bsfl %0, %0": "+r"(x));

return x;

}

 

ЗАКЛЮЧЕНИЕ

 

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

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

 

 

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

 

1. AntiPatterns [Электронный ресурс]. – Режим доступа: https://sourcemaking.com/antipatterns.

2. Приемы объектно-ориентированного проектирования. Паттерны проектирования / Э. Гамма, Р. Хелм, Р. Джонсон, Д. Влиссидес. – Санкт-Петербург: Питер, 2016. – 366 с.

3. Введение в паттерны (шаблоны) проектирования [Электронный ресурс] // CPP-reference. – Режим доступа: http://cpp-reference.ru/patterns/introduction/.

4. ISO/IEC 14882:2011 Information technology -- Programming languages -- C++ [Электронный ресурс]. – Режим доступа: https://www.iso.org/standard/50372.html.

5. Мейерс, С. Эффективный и современный С++: 42 рекомендации по использованию С++ 11 и С++14 / С. Меййерс. – Москва: Вильямс, 2016. – 304 с.

6. C++ 11 FAQ от Бьярна Страуструпа [Электронный ресурс]. – Режим доступа: http://sergeyteplyakov.blogspot.ru/2012/05/c-11-faq.html.

7. C++11 - the new ISO C++ standard [Электронный ресурс]. – Режим доступа:

http://www.stroustrup.com/C++11FAQ.html.

8. Александреску, А. Современное проектирование на C++ (серия C++ in Depth) / А. Александреску. – Москва: Вильямс, 2008. – 336 с.

9. Влиссидес, Д. Применение шаблонов проектирования. Дополнительные штрихи / Д. Влиссидес. – Москва: Вильямс, 2003. – 144 с.

10. Кериевски, Д. Рефакторинг с использованием шаблонов / Д. Кериевски. – Москва: Вильямс, 2006. – 400 с.

11. Макконнелл, С. Совершенный код. Мастер-класс / С. Макконнелл. – Москва: Русская редакция, 2010. – 896 с.

12. Эккель, Б. Философия C++. Введение в стандартный C++ / Б. Эккель. – 2-е изд. – Санкт-Петербург: Питер, 2004. – 572 с.

13. Страуструп, Б. Программирование: принципы и практика с использованием C++ / Б.Страуструп. – 2-е изд. – Москва: Вильямс, 2016. – 1328 с.

14. Страуструп, Б. Язык программирования C++. Специальное издание. / Б. Страуструп. – Москва: Бином, 2011 г. – 1136 с.