Орловский государственный университет
Санкт-Петербургский институт
информатики и автоматизации РАН
*****@
Шаблоны c++ — эффективное средство разработки и реализации решений математических задач
Шаблоны — одна из наиболее мощных возможностей, предоставляемых C++ программисту, которая позволяет быстро и эффективно решать сложные задачи. Основное преимущество шаблонов (с точки зрения программирования) заключается в возможности повторного использования кода [1]. Говоря другими словами, наличие этого средства делает стиль программирования на C++ гораздо более близким к математике (как теоретической науке), в сравнении с другими языками программирования, где такое средство недоступно. Поясним сказанное на примерах.
Пусть на множестве 
определено отношение полного порядка 
. Тогда мы можем определить функцию (описать алгоритм) 
нахождения максимума из двух элементов K:
Реализация этой функции на большинстве языков программирования будет заключаться в фиксировании множества . То есть если требуется работать с несколькими множествами, придется писать несколько функций, а программирование сведется к рутинному дублированию кода. На C++ мы можем написать шаблон для функции max, получающей два аргумента некоторого типа, реализовав его в предположении, что для данного типа определена операция . Далее, мы можем использовать 
с аргументами любого типа, а компилятор будет сам дублировать код по шаблону.
При реализации математических моделей часто приходится вводить сложные структурированные типы данных и описывать их функционирование. Используя шаблоны классов, можно определить не конкретный тип данных, а множество типов (параметризированный тип), элементы которого зависят от нескольких параметров. Фиксируя параметры, мы можем без дополнительных усилий получить тип данных для решения конкретной задачи.
Например, комплексное число можно реализовать шаблоном как пару чисел типа 
. Выбрав в качестве тип, реализующий множество действительных чисел, мы получим обычное комплексное число. Выбрав тип, соответствующий целым рациональным (простым) числам, получим гауссово целое (простое) комплексное число. Выбрав натуральный тип, получим целые числа (по К. Вейерштрассу).
Стоит отметить, что зачастую строгая реализация (при помощи шаблонов) решений многих задач требует использования особых трюков, и код получается намного сложнее, нежели в «нешаблонной» реализации. Однако шаблоны C++ — это бурно развивающаяся область. Постоянно ведутся работы по улучшению и формализации языка. Этот факт и уже имеющиеся преимущества указывают на перспективность использования шаблонов для реализации решений математических задач [2].
Еще одним важным моментом является соотношение скорость/пере-носимость. Максимальная переносимость достигается при использовании стандартизированных языков высокого уровня; при этом (в зависимости от языка) страдает скорость выполнения. Максимальная производительность достигается при программировании на ассемблере за счет полного расставания с переносимостью программы. В сложных вычислительных системах основные, часто используемые операции обычно реализуют на ассемблере (выпускается набор библиотек для поддержки наиболее распространенных платформ), а все остальное на каком-либо языке высокого или среднего уровня.
Относительно переносимости использование шаблонов обладает одним недостатком. Он заключается в том, что большинство компиляторов на данный момент не поддерживают стандарт C++ полностью (в основном в области, касающейся шаблонов). Однако на практике эта проблема разрешима.
С точки зрения производительности, код с использованием шаблонов в сочетании с механизмами встраиваемых функций, статического полиморфизма плюс хорошие оптимизирующие возможности современных компиляторов обладает прекрасными показателями. Они, конечно же, не сравнятся с кодом, непосредственно написанном на ассемблере. Сочетание ассемблерного кода с шаблонами в контексте C++ программы предоставило бы программисту огромные возможности по оптимизации. Это, к сожалению, невозможно, так как использование ассемблерных вставок в шаблонах функций и встраиваемых функциях запрещено.
Однако шаблоны могут быть полезны для исследования и разработки алгоритмов, которые впоследствии планируется реализовать на ассемблере с целью достижения максимальной эффективности.
Реализовав некоторое понятие или алгоритм в обобщенном виде при помощи шаблонов, мы можем (не модифицируя кода): оценить скорость работы алгоритмов, подсчитав число проделанных элементарных операций; подобрать опытным путем более эффективный тип данных; использовать код в программах, требующих платформенной переносимости.
Более подробно рассмотрим применение шаблонов (и сопутствующие выгоды) для реализации понятия «целое число» (реализация, в которой диапазон значений не фиксирован, а зависит от доступных машинных ресурсов). Соответствующий тип данных является базовым для всех математических вычислений в области компьютерной алгебры.
Будем использовать подход [3, с. 237], в котором:
- целое число 
представляется в системе счисления по основанию 
единственной последовательностью цифр 
в виде
;
- цифры являются 
-целыми: 
, где 
(*);
- нуль представляется одной цифрой 
;
- цифры хранятся в списке, начиная с 
.
Для реализации в общем виде целого в таком представлении формализуем его. Зададим множество представлений 
, где:
- 
— множество цифр (вида (*));
- 
— множество операций над цифрами;
- 
— некоторый абстрактный тип данных, представляющий список;
- 
— множество операций над списком.
Множество 
реализуется на С++ как шаблон класса.
Для эффективно работающей реализации приходится детально выделять большое число операций. Укажем некоторые из них, например, для цифр:
- сложение двух цифр с получением суммы и переноса;
- сложение двух цифр с переносом с получением суммы и переноса;
- умножение цифр с получением произведения и переноса (1);
- умножение двух цифр с получением двузначного произведения (2).
Для списков:
- вставка элемента после данного;
- вставка заданного числа элементов в начало;
- удаление всех элементов кроме первого;
- слияние (к концу одного списка подсоединяется другой, начиная с некоторого элемента).
Если какое-либо действие применяется несколько раз, оно выделяется в отдельную операцию. Впоследствии, когда все операции будут выделены (для списка), мы сможем подобрать и использовать реализацию списка, которая выполняет их наиболее эффективно.
За счет параметров и мы получаем возможность варьировать основание системы.
На начальных этапах разработки, когда операции умножения и деления еще не реализованы, невозможно выполнить преобразование из одной системы счисления в другую. То есть невозможен ввод и вывод в десятичной системе (в общем виде). Выбрав 
мы непосредственно работаем с десятичной системой, что значительно облегчает тестирование алгоритмов. Впоследствии, выбрав в качестве наибольшее множество, которое помещается в машинное слово, и реализовав соответствующим образом набор операций , мы получим одно из наиболее эффективных представлений целого числа.
Добавив набор счетчиков и вставив в код функций, реализующих операции из и , их увеличение, мы получаем возможность подсчитать число элементарных операций, требуемых для выполнения операции над целыми. Эти оценки могут использоваться для облегчения высоко - и среднеуровневой оптимизации алгоритмов.
В качестве примера подсчета числа операций рассмотрим реализацию умножения классическим способом (в столбик) и по методу Карацубы [3]. Ниже приведены графики функций от двух аргументов — число значащих цифр первого и второго множителя, значением которых является число операций, потребовавшихся при выполнении умножения (рис. 1 — операция (1), рис. 2 — (2)). Левый график соответствует умножению в столбик, правый — методу Карацубы.
Рис. 1.
Рис. 2.
Список литературы
1. Джосаттис C++: справочник разработчика / Пер. с англ. — М.: Вильямс, 2003.
2. Кнут программирования. Т. 2: Получисленные алгоритмы / Пер. с англ. 3-е изд. — М.: Вильямс, 2003.
3. Компьютерная алгебра: Символьные и алгебраические вычисления / Пер. с англ.; Под ред. Б. Бухбергера, Дж. Коллинза, Р. Лооса. — М.: Мир, 1986.
