Бауэр Ф.Л., Гооз Г. Информатика. Том 1

Подождите немного. Документ загружается.

3.6. Массивы

251

3.6.2.3

Многомерные массивы легко приводят к большим затратам

памяти. Квадратная матрица с и = 2

= 512 строками содер-

згос

as ([

n] var

real

vi *

[[]

n] var

real

с;

var

real

sum;

for

from

I to и

sum

—

for

from

to и

sum

=«

vum +

sm(pixixj/{n

V$)x.xV\

c[i\"sum/sqrt{(fl+iy2)

for;

from

1 to я

v[/] —c[i] od

od.

od,

Рис

procedure

/((var v array

[1..«]

of m>

var с:

array

[ 1,,

of real;

ltd'

teal;

7,y: integer;

fc-i

-1 tow

~egsn

suffr=0;

foo''-sl

to «

Jwm

—sum

sin(pi*i*j/(it

'\))*x\j

c[i]

"Sum/sqttifr + X)/!)

end,

for

/= 1 to и

x[i]:-e[i]

pnd

133.

жит 2

262000

элементов. Если эти элементы достаточна

просто вычисляются, как, скажем, в случае

a[l,j]

sin(n

X i X l/(n +

l)/sqrt((n

+ l)/2)

(„численное преобразование Фурье"), то рекомендуется вообще

не заводить для них массива, а непосредственно вводить соот-

ветствующие значения в вычисления (рис. 133').

3.6.3.

Сведение

многомерных

массивов

одномерным

Многомерные массивы индексированных переменных тре-

буют

больших затрат на организацию доступа к элементам.

В этом разделе мы покажем, как „избавляются" от многомер-

ных массивов, сводя их к одномерным. Число индексированных

переменных r-мерного (г ^ 2) массива а сорта

>п

<,...,

i..

] var k,

(, . ..

,>/n

<] of к

соответственно

var

array

\>m

{

<..

i,>m

равно

где

—

nit

+ 1

ft—от

Fourier transformation (преобразование Фурье). —

Прим

перев*.

252

Гл. 3.

Машинно-ориенгированные алгоритмические языки

—

длина

массива

по i-му

измерению. Столько

же

элементов

имеет одномерный массив

сорта

1(] var

с произвольно выбранным первым индексом

>т<,

получающийся

.путём последовательного „вытягивания" исходного массива,

именно

последовательным выстраиванием

друг

за

другом

(г— 1)-мерных массивов сорта

.. ,)m

{..)n

(]

var I,

каждый

из

которых

свою очередь получается последователь-

иым

выстраиванием

—2)-мерных массивов сорта

[)т

(..)п

{,...,)т

.)n

(] var I,

Т. Д.

При

этом

между

отдельными элементами наших массивов

устанавливается следующее соответствие:

a[i

, ..., i

]<=>d[j],

где

. . . k

(г,

— m

) + k

. . . k

{k — m,) + . . .

• • •

[

— m

)-\-{i, — m

) + m.

Если

ввести вспомогательную линейную функцию

/ по

формуле

, .... х

) =

{

... k, +

... k

+ ...

.. •

+ x

или

(в

виде, отвечающем

схеме

Горнера)

(х

, .. ., х

) = (...

((x

{

+ х

) k

)kt+

...

. • •

_i)k

+ X

то предыдущее равенство можно переписать

так:

= f(h — Щ, i

— щ, ..., i

— m

) + ih

/(«i, h<

••

•>

О +

const,

где

const

= m — / (m

Функцию

называют

функцией выборки или функцией разме-

щения в

памяти.

Пример.

Для

[1.

.5,1. .5] var real а,

соотв.

var a: array [1.

.5,1.

.5] of real

имеем

= 5, k

= 5, K = 25.

Если

описание массива

заменить

на

[6.

.30] var real а,

соотв.

var a: array [6. .30] of real,

3.6. Массивы 253

то формулы

a[i + k,t-k],

a[i,i],

a[t,k]

a[k,t]

следует

заменить на

d[6X' +

4X*J.

Й[6Х'Ъ

d[5Xi

+ k] +

d[5Xk

+ t].

Таким образом, описание многомерного массива заменяется на

соответствующее

описание одномерного массива, а каждая

(многократно) индексированная переменная заменяется на со-

ответствующую

переменную получаемого таким образом одно-

мерного массива, для чего, в частности, и необходимо знать

длины многомерного массива по измерениям.

При

этом в индексных позициях

могут

стоять, вообще го-

воря,

и более сложные формулы. Однако линейные выражения

в индексных позициях переходят при рассмотренной замене

снова в линейные выражения.

3.6.4.

Статическое

распределение

памяти

3.6.4.1

После сведения многомерных массивов к одномерным мож-

но

сделать

ещё один шаг в направлении линеаризации памяти

объединить все параметры-переменные некоторой процедуры

(для простых переменных и одномерных массивов индексиро-

ванных переменных) в один-единственный массив индекси-

рованных переменных, который в этом

случае

называют па-

мятью

процедуры. Сюда же целесообразно включить и описан-

ные в процедуре локальные переменные и массивы — в паскале

на

это намекает уже и способ записи, поскольку все эти опи-

сания

следуют

непосредственно за заголовком процедуры.

Кроме того, обыкновенные параметры, а также локально

•описанные обозначения промежуточных

результатов

можно за-

менить на неизменные переменные и

тоже

включить в эту

память.

Пример.

Для процедуры

matrixappt

из

3.6.2.2

при п = 50

возможен следующий вариант распределения памяти с исполь-

зованием массива

[1..2601]

var real Q (если не

учитывать

i, /):

[1..

50,

1.. 50] var real a **

..2500]

var real Q 1

[1..50]varreal6

~ [2501 ..2550] var

real

Q J

ла

аА1ет

ьг

..50] var

real

с « [2551 ..2600] var

real

лш<альнь|!

var

real

sum ** [2601 ..2601] var

real

Q )

параметры

*l*i

• .

,№»»0

0'0*»000

. . , t >Л 1Л "Л , » ,5\QO

NnfN(NfNrMMriM(N И N rN (N

ГЧГЧГЧ

254 Гл. 3. Машинно-ориентированные алгоритмические языки

Тем самым каждой процедуре соответствует некоторый подмас-

сив,

элементы которого (если только они не отвечают чистым

параметрам-результатам или локальным величинам) запол-

няются

должным образом перед вызовом процедуры (и в

ходе

исполнения

замещаются новыми значениями, если только это>

us входные или обыкновенные параметры). Правда, когда

взаимодействует сразу несколько процедур, при таком простом

образе действий потребуются изрядные затраты, связанные с

удалением и возвратом значений в память.

Отдельные индексы введенной таким образом памяти назы-

ваются

(относительными)

адресами,

и соответственно мы гово-

рим

об

адресуемой

памяти.

случае

рекурсивных процедур вроде

quicksort

для каждого-

воплощения

потребуется своё собственное место в памяти —

для локально описанных промежуточных результатов, перемен-

ных, массивов, а также обыкновенных параметров. Необходимое

для этого „динамическое распределение памяти", включающее

себя некоторую специальную обработку

('call

reference'

)

упоминавшихся в 3.6.1 вычисляемых переменных, мы обсудим

лишь

в гл. 5.

Применение

же описанного выше

статического

распределе-

ния

памяти

ограничивается случаем итеративных программ и.

массивов с постоянным диапазоном индексов. Оно часто исполь-

зуется для малых машин.

3.6.4.2

Более эффективный способ распределения памяти, который

не

только сокращает издержки на переброски в памяти, но п

экономит

сами элементы памяти, основан па совместном поль-

зовании

памятью из окружения вызова—он принимает в рас-

чёт паразитический характер параметров-переменных (см.

3.5)..

Соответствующая машинная реализация организует при вызове

процедуры передачу фактических значений параметров особым

переменным процедуры. А именно, в

случае

обыкновенных па-

раметров значения в форме объектов передаются обыкновен-

ным

переменным, а в

случае

параметров-переменных значения.

форме

ссылок,

т. е. адресов, передаются специальным пере-

менным,

называемым

переменными

связи.

Предусматриваются

особые меры для того, чтобы возможным было присваивание

такой индексированной переменной, индекс которой вычис-

ляется, т. е. переменной, которая является значением некоторой

переменной

связи

(косвенная

адресация,

X. Шехер, 1955 г.).

„Вызов ссылкой" (англ.). —

Прим.

перев.

3.7. Декомпозиция формул 255

Аналогично рассматриваются также (одномерные и много-

мерные) массивы с постоянным диапазоном индексов; переда-

ваемой ссылкой

служит

при этом некоторый адрес-ссылка, как

например т в

разделе

3.6.3.

Подробнее обо всём этом

будет

сказано в гл. 5 при обсуждении динамического распределения

памяти.

"R4.3

При

технической реализации памяти применяют преимуще-

ственно носители с возможностью обновления содержимого.

точки зрения работы с вычислительными формулярами это

означает использование карандаша и

резинки

с целью

сэконо-

мить место для размещения результатов. В конце вычислений

такой формуляр уже не

отражает

полностью весь ход проделан-

ных вычислений, он „забывает предысторию". На ход вычисле-

ний

это

никак

не влияет, а вот на возможности перепроверки

выполненных вычислений, на возможности обозреть их с по-

мощью формуляра, конечно, сказывается.

Отдельные программные переменные реализованной описан-

ным

способом памяти называются

переменными

памяти.

3.7.

Декомпозиция

формул

Формулы машинно-ориентированного языка элементарны,

т. е.

содержат

не более одного знака операции. Таким образом,

помимо обозначений

вроде

true,соотв.

true

"ледокол", соотв. 'ледокол'

хо

холост

допускаются только одноместные элементарные формулы, та-

кие

как

- 17

холост, соотв. not холост

abs а, соотв. abs(a)

Изучение этого раздела можно отложить до гл. 5.

256 Гл 3 Машинно-ориентированные алгоритмические ячнки

двуместные элементарные формулы типа

17 + 4

а\Ь, соотв. а * b

"ледо" + "кол", соотв.

сопс

('ледо'/кол')

a div 2

(в

предположении что все основные операции не более чем

двуместны). Более сложные формулы нужно разлагать на эле-

ментарные,

вводя вспомогательные обозначения для промежу-

точных результатов. Запись формул при этом становится длин-

нее—

с точки зрения читателя-человека информация становится

чересчур „разжиженной". В

результате

получается весьма близ-

кая

к машине нотация, которая и характеризует в первую оче-

редь облик „языков ассемблера".

3.7.1.

Декомпозиция

по

принципу

магазина

Пример.

Пусть

а,Ь — обозначения констант вида int, соотв.

integer,

х,г

— переменные вида var

real,

соотв. var

real.

Формулу

abs(12X*

—

z/a)<bX

Uo~

> соотв.

abs (12 *x — z/a) <b*\E — 8,

можно разложить в последовательность иерарахически опираю-

щихся

друг

на

друга

(групповых или линеаризованных) описа-

ний

промежуточных результатов, завершающуюся искомым ре-

зультатом:

["(real

hi, real /г2)н=(12 X

x,z/a);

real

h3 = hi - h2\

(real

h4, real /z5) = (abs h3 ,b X

— 8);

bool

h6^h4<h5;

h6 J,

которая

отражает

структуру

вычислительного формуляра, а

также порождаемого им дерева Канторовича для этой формулы

(рис.

134).

Теперь в максимальной мере может быть реализована воз-

можность параллельного исполнения. Результат, вырабатывае-

мый

формулой, доставляется последней строчкой последователь-

ности;

таким образом, из формулы получилось предложение.

Аналогичным образом описание промежуточного результата

или

присваивание с формулой в правой часги преобразуется в

3.7.

Декомпозиция

формул

257

иерархию описаний промежуточных результатов, соответственно

з (иерархически построенный) оператор.

Л5

Рис.

134. Дерево

Канторовича

для формулы abs(12X* —

г/а)<ЬХ

1ю — 8.

При

ориентации на машины последовательного действия

получающееся предложение придётся линеаризовать, напри-

мер так:

begirt

М:геаЫ\%*х\

h2:real=z/a;

h3ireal~hl-h2\

h4:real=abs{h3);

h5:rea1~b*lE-8;

h6:

Boolean

=*h4<h5;

Ггеа1

ЬЫ\

real

теа\

= hl-h2;

real

Ыsabs h3;

end

Эта специальная последовательность соответствует правилу

вычислений „по принципу магазина", описанному в 2.3.3 для

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

при

движении

слева

направо

выполнение

операций

откла-

дывается

лишь

случае

необходимости,

отложенные

опе-

рации

выполняются

сразу,

как

только

это

становится

воз-

можным.

При

этом приоритет „отложенных" операций выражается

с помощью явной расстановки скобок или с помощью правил

старшинства операций (см.

2.2.2.1).

Одну из „линейных" форм вычисления для данной формулы

можно получить, записывая в одну строчку ее дерево Канто-

ровича с сохранением его топологической структуры.

9 Ф. Л. Бауэр, Г. Гооз

258 Гл. 3. Машинно-ориентированные алгоритмические языки

На

рис. 135 изображено дерево Канторовича для приведён-

ной

выше формулы, „линейно упорядоченное" в соответствии

с принципом магазина.

' hi

Рис.

135. Топологически упорядоченное

дерево

Канторовича в линейной

записи.

Рис.

136. Дерево Канторовича для формулы

(а

X b +(a + d)X c)l(a + 6 X 6).

Другим примером может служить формула

(аХ b +(а + d)X с)/(а + b

(её дерево Канторовича изображено на рис. 136), для которой

по

принципу магазина получается следующая линеаризация:

real

hl^axb;

real

h2 = a+d;

real

h3 =

h2xc;

real

h4 =

hl+h3;

real

h5 =

real

h6s ;

tea\h7sh4/h6;

begin

hi:

real = a*b;

h2:

real=a + d;

h3:

real=h2*c;

h4:real=>hl+b3;

h5:real

= b*b;

h6:real-a

+ h5;

h7:real=*h4/h6;

>Res< «Л7

end

3.7.

Декомпозиция

формул

259

Промежуточные результаты, возникающие при декомпозиции

собственно формул, характеризуются тем, что они используются

всего один раз '.

3.7.2.

Использование

магазина

промежуточных

результатов

„Многие

же

будут

первые

послед-

ними

последние

первыми."

Евангелие от Матфея, 19, 30

Использование

принципа магазина для линеаризации осо-

бенно

выгодно, когда экономно используются обозначения про-

межуточных результатов, т. е. вместо них употребляются (вспо-

могательные) переменные.

Такую переменную, употребленную вместо обозначения про-

межуточного результата, можно задействовать повторно после

того, как она однажды уже была использована. Максималь-

ное

число

требуемых

при этом переменных в общем

случае

намного

меньше количества имеющихся промежуточных резуль-

татов.

Для последнего из приведённых в предыдущем разделе при-

меров при использовании массива индексированных перемен-

ных мы получаем, что переменная h[l] последовательно игра т

роль hi, h4, hi, а переменная /i[2] —роль h2, h3, h5 и h6:

begin

A[2]:=/i[2]xc:

Л[2]:=д+/;[2];

НЧ J

h[2]:=b*b;

APJI-Л+АИ:

end

Этот пример показывает, что при работе по принципу магазина

первой доступной для употребления

всегда

становится та пе-

ременная,

куда

значение было помещено последним (англ.:

'last

—first

out'

Эш справедливо лишь до тех пор, пока мы не задаёмся целью (ис-

ходя

»з соображений эффективности и с использованием совместности) вы-

числять

каждую

много раз встречающуюся подформулу тлько один раз и

тем самым выходим за рамки собственно формул.

' Дословно: „последний в — первый из". —

Прим.

перев.

260 Гл. 3. Машинно-ориентированные алгоритмические языки

Память,

организованная по такому принципу, называется

магазинной

памятью

или просто

магазином

(англ.:

pushdown

store,

pushdown

). Массив, который работает в таком режиме,

называется

пульсирующей

памятью. Индекс последней исполь-

зованной

магазинной переменной, или указатель верхушки

пульсирующей памяти („конец занятой памяти"), изменяется

зависимости от того, сколько (вспомогательных) переменных

встречается в правой части присваивания; а именно, он

— увеличивается на 1,

если

там нет

магазинных

переменных;

—

остаётся

неизменным,

если

там

ровно

одна

магазинная пе-

ременная;

—

уменьшается

на 1,

если

там две

магазинные

переменные

Тем самым наш последний пример можно теперь записать в

следующей форме с использованием глобального указателя

верхушки i:

J"co{«Qco

l]:=bxb;

Л[/-1]:=Л[|-1]/ЛИ;

/:=f-l;

со /«=1 со

После

исполнения формулы вырабатываемый ею результат на-

ходится всегда в переменной Л[1], т. е. справедливо равенство

i=l

(контроль!). В результате выполнения последующего

присваивания

или описания промежуточного результата мага-

зин

полностью освобождается, т. е., как и в начале, мы имеем

; =

о.

3.7.3.

Перевод

трёхадресную

форму

Если

уж мы используем магазин или пульсирующую память,

то естественно возникает мысль не применять для выполнения

арифметических операций никаких других переменных, кроме

В оригинале Keller (см. подстрочное примечание к „принципу магази-

на"

в разделе 2.3.3). — Прим. изд. ред.

Термин „Keller" был введён Бауэром и Замельзоном в [западногер-

манской.—

Перев.]

патентной заявке от 30 марта 1С57 г

Push down буквально означает „проталкивать вниз", store — склад,

магазин. — Прим.

перев.

Однако если бы мы захотели сохранить совместность, то одного ма-

газина оказалось бы недостаточно Для каждой „ветви" совместного испол-

нения

понадобился бы свой собственный ыа1азин. См. также

3.7.5.