|
Проблемы оптимизации работы с матрицами давно
волнуют создателей компиляторов. В то далекое
время, когда решения задач электродинамики и
вообще краевых задач матфизики еще интересовали
влиятельных людей нашей страны (скорее, научные
авторитеты убеждали их, что такие задачи следует
решать), мы, используя язык PL/I или FORTRAN,
конечно же, хранили и обрабатывали матрицы в
одномерных массивах. Дело в том, что выбор
одного элемента из более естественного для
матриц двухмерного массива обходился дорого.
Выработалась особая техника работы с одномерными
массивами, хранящими матрицы (обычно
разреженные). В языке C++ операция выбора
элемента из двухмерного динамического массива не
намного дороже, чем из одномерного (да и
скорости изменились), поэтому острота проблемы
спала. Тем не менее проблема экономии времени
при решения сложных краевых задач не ушла в
прошлое.
STL имеет пару
вспомогательных классов: slice и gslice, которые
созданы для того, чтобы было удобно работать со
срезами (сечениями) одномерных массивов. Если вы
храните двухмерную матрицу в последовательности
типа valarray, то элементы одной строки матрицы
или одного ее столбца можно представить в виде
сечения, то есть определенной части всей
последовательности. Конструктор класса slice
определяет закономерность, в соответствии с
которой будут выбираться элементы
последовательности, чтобы образовать срез.
Например, объект slice s(0, n , 2); представляет
собой сечение из п элементов последовательности.
Элементы выбираются начиная с нулевого, через
один, то есть с шагом 2. Если вы храните матрицу
пхп в последовательности типа valarray и при
этом она упорядочена по строкам (сначала первая
строка, затем вторая, и т. д.), то третью строку
матрицы можно выбрать с помощью сечения:
slice s (2*n, n ,
1);
Действительно, параметры указывают, что надо
пропустить 2*n элементов, затем выбрать n
элементов с шагом по одному. Если матрица
хранится a la FORTRAN, то есть по столбцам, то
для выбора той же строки надо определить
сечение:
slice s (2, n , n);
Пропускаются два элемента, затем выбирается n
элементов с шагом п. Вы, конечно, поняли, как
создать сечение, но не поняли, какое отношение
оно имеет к последовательности valarray, так как
она не фигурирует в приведенных выражениях. Да,
синтаксис, связывающий срез с valarray,
несколько необычен, хотя вполне логичен:
int
n = 5, // Размерность матрицы n (размером пхп)
пп = п*п;
// Размерность
valarray
//=== Создаем матрицу (одномерную
последовательность)
valarray<double> a
(nn);
//=== Генерируем ее элементы по закону f (Пока
его нет)
generate (&a[0], &a[nn], f) ;
//====== Создаем сечение
slice s (0, n , 1);
//====== Выделяем сечение (первую строку,
//====== если матрица хранится по строкам)
valarray<double> v
= a[s];
Вы видите, что объект s класса slice помещается
в то место, куда мы обычно помещаем
целочисленный индекс массива или
последовательности. Такая интерпретация операции
[ ] непривычна. Вы, вероятно, догадались, что
роль объекта s в приведенном фрагменте является
чисто эпизодической. Можно обойтись и без него,
заменив его временным безымянным объектом,
который создаст компилятор. При этом конструкция
выражения будет более эффективной, но и более
головоломной. Последние две строки фрагмента
можно заменить одной строкой:
valarray<double>
v = afslice (0, n , 1);
Подведем итоги. В этом уроке мы оценили
возможности библиотеки STL и сделали вывод, что
она, очевидно, имеет гораздо больше достоинств,
чем недостатков. Необходимо регулярно
тренировать технику ее использования. В этой
задаче может помочь сеть Интернет, в которой
появляется все больше сайтов, уделяющих внимание
STL. Кроме того, мы:
-
вспомнили, как создавать шаблоны функций и
шаблоны классов;
-
узнали, что стандартные контейнеры делятся
на последовательности и ассоциативные
контейнеры;
-
узнали, как пользоваться предикатами и
функциональными объектами;
-
познакомились с возможностями связывателей,
адаптеров и отрицателей;
-
узнали, как шаблоны пар помогают работать с
ассоциативными контейнерами типа тар;
-
получили представление об использовании
очередей и стека;
-
оценили возможности текстовых строк типа
string;
-
научились пользоваться итераторами
различного типа, в том числе и для
управления потоками ввода-вывода;
-
узнали о наличии большого количества
полезных констант;
-
поработали с последовательностями типа
valarray и их сечениями;
-
опробовали некоторые алгоритмы управления
последовательностями.
|