Компонента вектора, в свою очередь, может быть вектором, например, длины N. В этом случае обычной иллюстрацией (рис. E1-2) служит графическое представление массива в виде двумерной таблицы конечных размеров, нередко называемой матрицей. Соответственно, развернутую в вектор компоненту Mas2[i,*] называют строкой, поскольку в этом представлении каждую i-у компоненту именно так принято изображать в таблице.

Mas2                         0             1             ...                     Mas2[i,j]     i             ...             M-2             M-1 0 1 ... j ... N-1

Рис. 2.

Адресация элементов массива Mas2 становится "дороже" - теперь она требует указания двух индексов, а именно, внешнего (строки) и внутреннего - естественно назвать его столбцом. Обратим внимание программистов, что порядок расположения индексов строки и столбца - слева направо - продиктован принятыми для визуализации, традиционными, соглашениями. Если же вы используете такой - "дважды индексированный" - массив в тексте программы, то перечисление индексов может быть и обратным: все зависит от синтаксических правил, установленных в конкретном языке. Так, например, "паскалевская" индексация повторит ту, что приведена на рисунке, а "фортрановская" оказывается обратной.

В традиционной интерпретации обратиться к элементу Mas2[i,j] удастся, вычислив его адрес согласно формуле:

addr(Mas2[i,j])=addr(Mas2[0,0])+mem(elem)*(j+N*i)

{**}

Как видим, вычисление адреса элемента потребует уже две операции умножения и две - сложения.

"Менее популярны" массивы бОльших, чем 1 (как у Mas1) и 2 (Mas2), размерностей. Главным образом потому, что не столь уж часто встречаются задачи, нуждающиеся в использовании многомерных массивов. Но есть и другая причина: обращение к компоненте многомерного массива связано с более громоздкими вычислениями ее адреса, поэтому массовая обработка элементов может оказаться чересчур дорогостоящей. В общем случае, для заданной размерности L установить адрес элемента в массиве MasL удается по формуле:

addr(MasL[i1,...,iL])= addr(MasL[01,...,0L])+mem(elem)* (iL+NL*iL-1+ NL*NL-1*iL-2+...+ NL*NL-1*...*N2*i1)),

{***}

где i_k и N_k - соответственно, значение индекса и длина индексного диапазона по k-й размерности массива.

Как видим, только сложений требуется L, а умножений уже 1+(L-1)*L/2. Иначе говоря, трудоемкость вычислений, проводимых для адресации произвольного элемента многомерного массива, растет с квадратичной скоростью относительно его размерности. Вывод напрашивается: желательно ограничиваться массивами небольших размерностей, и поздно требовать это от программиста, если еще раньше об эффективности не позаботился алгоритмист.

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

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

Наконец, перечисляя недостатки, присущие рассматриваемой нами структуре данных, пора обратить внимание на главный из них. Мы имеем в виду фиксированные размеры массива. Что в этом плохого? - спросите вы. Дело в том, что продиктованные постановкой задачи размеры, в свою очередь, диктуют выбор параметров массива в программе и, нередко, даже выбор алгоритма обработки. Если при дальнейшей эксплуатации программы (лучше бы - при тестировании) выясняется, что входной набор не помещается в жесткие рамки выбранной структуры, то простого изменения значений параметров может оказаться недостаточно, и программу - возможно, и алгоритм - придется переписывать.

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

Обращаться за примерами к собственно компьютерной сфере нет нужды, поскольку с разнообразными таблицами фиксированного размера мы сталкиваемся довольно часто и в других предметных областях. Вот пример, проверить который по силам любому нашему читателю. Надеюсь, паспорт у вас есть и, листая его, вы найдете страничку "дети". В документе читателя, вероятно, она пока не заполнялась, но в паспорте автора пометки есть. Так вот, на одну компоненту массива отводится три строки - фамилия, имя, отчество; строк на странице - 9, страниц данной рубрикации - 2. Итого: чадолюбивому владельцу паспорта места хватает не более чем на шестерых потомков. К счастью, автор не является матерью-героиней, и его интересы указанное ограничение не затронуло. Что касается постановщика задачи, планировавшего рождаемость в нашей стране столь оригинальным способом, то отыскать его уже вряд ли возможно.

Назад