Основы программирования



              

Представление матриц и многомерных массивов - часть 2


Каждая строка состоит из n элементов, следовательно, индекс элемента строки i и столбца j в линейном массиве равен

i * n + j

(действительно, поскольку индексы начинаются с нуля, то i равно количеству строк, которые нужно пропустить, i * n - суммарное количество элементов в пропускаемых строках; число j равно смещению внутри последней строки). Таким образом, элементу матрицы в строке i и столбце j соответствует выражение

a[i * n + j]

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

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

double **a; // Адрес массива указателей int m, n; // Размеры матрицы: m строк, n столбцов int i; . . . // Захватывается память под массив указателей a = (double **) malloc(m * sizeof(double *));

for (i = 0; i < m; ++i) { // Захватывается память под строку с индесом i a[i] = (double *) malloc(n * sizeof(double)); }

После этого к элементу a ij можно обращаться с помощью выражения

a[i][j]

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

Многомерные массивы реализуются аналогично матрицам. Например, вещественный трехмерный массив размера 4 ? 4 ? 2 описывается как

double a[4][4][2];

обращение к его элементу с индексами x, y, z осуществляется с помощью выражения

a[x][y][z]

Многомерные массивы переменного размера с числом индексов большим двух встречаются в программах довольно редко, но никаких проблем с их реализацией нет: они реализуются аналогично матрицам. Например, пусть надо реализовать трехмерный вещественный массив размера m ? n ? k. Захватывается линейный массив вещественных чисел размером m * n * k:

double *a; . . . a = (double *) malloc(m * n * k * sizeof(double));

Доступ к элементу с индексами x, y, z осуществляется с помощью выражения

a[(x * n + y) * k + z]




Содержание  Назад  Вперед