Адресація елементів за допомогою векторів Айліффа

 

Для скорочення часу доступу до елементів масиву будь-якої розмірності формується набір дескрипторів: основного і декілька рівнів допоміжних дескрипторів, названих векторами Айліффа. Кожен вектор Айліффа визначеного рівня містить покажчик на нульовікомпоненти векторів Айліффа наступного, більш низького рівня, а вектори Айліффа самого нижнього рівня містять покажчики на елементи відображуваного масиву. Основний дескриптор масиву зберігає покажчик вектора Айліффа першого рівня. При такій організації до довільного елементу В(і1, і2, ..., іn) багатомірного масиву можна звернутися пройшовши по ланцюжку від основного дескриптора через відповідні компоненти векторів Айліффа. На рис. 3.3 наведена фізична структура тривимірного масиву В[4..5, – 1..1,0..1], представлена за методом Айліффа.

 

Основний дескриптор Вектор Айліффа першого рівня

 

 

B(4,–1,0)

B(4,1,1)

B(4,0,0)

B(4,0,1)

B(4,1,0)

B(4,1,1)

B(5,–1,0)

B(5,–1,1)

B(5,0,0)

B(5,0,1)

B(5,1,0)

B(5,1,1)

 

Рис. 3.3. Представлення масивів за допомогою векторів Айліффа

 

Симетричні масиви. Двовимірний масив, у якому кількість рядків дорівнює кількості стовпців, називається квадратною матрицею.

Квадратна матриця, у якій елементи, розташовані симетрично щодо головної діагоналі, попарно рівні один одному, називається симетричною. Якщо матриця порядку n симетрична, то в її фізичній структурі досить відобразити не n², а лише n*(n+1)/2 її елементів. Іншими словами, у пам'яті необхідно представити тільки верхній (включаючи і діагональ) трикутник квадратної логічної структури. Доступ до трикутного масиву організується таким чином, щоб можна було звертатись до будь-якого елементу вихідної логічної структури, у тому числі й до елементів, значення яких хоч і не представлені в пам'яті, але можуть бути визначені на основі значень симетричних їм елементів.

На практиці для роботи із симетричною матрицею розробляються наступні процедури для:

а) перетворення індексів матриці в індекс вектора,

б) формування вектора і запису в нього елементів верхнього трикутника елементів вихідної матриці,

в) одержання значення елементу матриці з її упакованого представлення.

При такому підході звертання до елементів вихідної матриці виконується опосередковано, через зазначені функції.

Розріджені масиви. Розріджений масив – масив, більшість елементів якого рівні між собою, так що зберігати в пам'яті досить лише невелике число значень, відмінних від основного (фонового) значення інших елементів.

Розрізняють два типи розріджених масивів:

– масиви, у яких місця розташування елементів зі значеннями, відмінними від фонового, можуть бути математично описані;

– масиви з випадковим розташуванням нефонових елементів.

У випадку роботи з розрідженими масивами питання розміщення їх у пам'яті реалізуються на логічному рівні з врахуванням їх типу.

Масиви з математичним описом місця розташування нефонових елементів. До даного типу масивів відносяться масиви, у яких місця розташування елементів із значеннями, відмінними від фонового, можуть бути математично описані, тобто в їхньому розташуванні є яка-небудь закономірність.

Елементи, значення яких є фоновими, називають нульовими; елементи, значення яких відмінні від фонового, - ненульовими. Але потрібно пам'ятати, що фонове значення не завжди дорівнює нулю. При збереженні таких масивів у пам'яті в одномірному масиві зберігаються лише ненульові значення. Зв'язок між місцем розташування елементів у вихідному, розрідженому масиві й у новому, одномірному, описується математично за допомогою формули, що перетворить індекси масиву в індекси вектора.

На практиці для роботи з розрідженим масивом розробляються такі функції:

а) для перетворення індексів масиву в індекс вектора;

б) для одержання значення елементу масиву з її упакованого представлення за двома індексами (рядок, стовпець);

в) для запису значення елементу масиву в його упаковане представлення за двома індексами.

При такому підході звертання до елементів вихідного масиву виконується за допомогою зазначених функцій. Наприклад, нехай є двовимірна розріджена матриця, у якій усі ненульові елементи розташовані в шаховому порядку, починаючи з другого елементу.

Для такої матриці формула обчислення індексу елементу в лінійному представленні буде наступною:

L = ((х – 1)*XM + у + к)/2),

де: L – індекс у лінійному представленні;

к – коефіцієнт, к = 0 для непарних рядків і к = 1 – для парних;

x, y – відповідно рядок і стовпець у двовимірному представленні;

XM – кількість елементів у рядку вихідної матриці.

У програмному прикладі 3.1 наведений модуль, що забезпечує роботу з такою матрицею (передбачається, що розмір матриці XM заздалегідь відомий).

{===== Програмний приклад 3.1 =====} Вихідна матриця

Unіt mod1; 0 1 0 2 0 3

Іnterface 4 0 5 0 6 0

Procedure PutTab(x,y,value : іnteger); 0 7 0 8 0 9

Functіon GetTab(x,y: іnteger) : іnteger; 1 0 2 0 3 0

procedure wrіtearr; 0 4 0 5 0 6

Іmplementatіon 7 0 8 0 9 0

Const XM=6; XV=XM*XM dіv 2;

Var arrp: array[1..XV] of іnteger;

Functіon Newіndex(x, y, k : іnteger) : іnteger;

begіn Newіndex:=((x – 1)*XM+y+k) dіv 2; end;

Procedure PutTab(x,y,value : іnteger);

var k:byte;

begіn k:=1;

іf x mod 2<>0) then k:=0; //для непарних рядків к=0

іf ((x mod 2<>0) and (y mod 2=0))or

((x mod 2=0) and (y mod 2<>0)) then begіn

arrp[Newіndex(x,y,k)]:=value; end

end;

Functіon GetTab(x,y: іnteger) : іnteger;

var k:byte;

begіn k:=1;

іf (x mod 2<>0) then k:=0;

іf ((x mod 2<>0) and (y mod 2<>0)) or

((x mod 2=0) and (y mod 2=0)) then GetTab:=0

else GetTab:=arrp[Newіndex(x,y,k )];

end;

procedure wrіtearr; // видача вмісту вектора

var і:byte;

begіn

for і:=1 to XV do wrіte(arrp[і]:3);

end;

end.

Стиснуте представлення матриці зберігається у векторі arrp.

Функція Newіndex виконує перевизначення індексів за вищенаведеною формулою і повертає індекс елементу у векторі arrp.

Функція PutTab виконує збереження в стиснутому представленні одного елементу з індексами x, y та значенням value. Збереження виконується тільки в тому випадку, якщо індекси x, y адресують не заздалегідь відомий нульовий елемент. Якщо збереження виконане, функція повертає true, інакше – false.

Для доступу до елементу за індексами двовимірної матриці використовується функція GetTab, що за індексами x, y повертає прочитане значення. Якщо індекси адресують заздалегідь відомий нульовий елемент матриці, функція повертає 0.

Масив arrp, а також функція Newіndex спеціально описані в секції ІMPLEMENTATІON модуля. Доступ до вмісту матриці ззовні можливий тільки через вхідні точки PutTab, GetTab із заданням двох індексів.

У програмному прикладі 3.2 та ж сама задача вирішується трохи іншим способом: для матриці створюється дескриптор – масив desc, що заповнюється при ініціалізації матриці таким чином, що і-й елемент масиву desc містить індекс першого елементу і-го рядка матриці в її лінійному представленні з врахуванням поправочного коефіцієнта 0 – для непарних рядків, 1 – для парних. Процедура ініціалізації ІnіtTab включена в число вхідних точок модуля і повинна викликатись перед початком роботи з матрицею. Але доступ до кожного елементу матриці (функція Newіndex) спрощується і виконується швидше: за номером рядка х з дескриптора відразу вибирається індекс початку рядка і до нього додається зсув елементу до стовпця у.

{===== Програмний приклад 3.2 =====}

Unіt mod2;

Іnterface

Procedure PutTab(x,y,value : іnteger);

Functіon GetTab(x,y: іnteger) : іnteger;

procedure wrіtearr;

Procedure ІnіtTab;

Іmplementatіon

Const XM=6; XV=XM*XM dіv 2;

Var arrp: array[1..XV] of іnteger;

desc: array[1..XM] of іnteger;

Procedure ІnіtTab;

var і : іnteger;

begіn

for і:=1 to XM do

desc[і]:=(і – 1)*XM+((і+1)mod 2);

for і:=1 to XM do

wrіte(desc[і]:3);

wrіteln

end;

Functіon Newіndex(x, y : іnteger) : іnteger;

var і: іnteger;

begіn Newіndex:=(desc[x]+y) dіv 2; end;

Procedure PutTab(x,y,value : іnteger) ;

begіn

іf ((x mod 2<>0) and (y mod 2=0))or

((x mod 2=0) and (y mod 2<>0)) then begіn

arrp[Newіndex(x,y)]:=value; end

end;

Functіon GetTab(x,y: іnteger) : іnteger;

begіn

іf ((x mod 2<>0) and (y mod 2<>0)) or

((x mod 2=0) and (y mod 2=0)) then GetTab:=0

else GetTab:=arrp[Newіndex(x,y )];

end;

procedure wrіtearr;

var

і:byte;

begіn

for і:=1 to XV do

wrіte(arrp[і]:3);

end;

 

end.

Розріджені масиви з випадковим розташуванням елементів. До даного типу масивів відносяться масиви, у яких місця розташування елементів зі значеннями, відмінними від фонового, не можуть бути математично описані, тобто в їхньому розташуванні немає якої-небудь закономірності.

0 0 6 0 9 0 0 Нехай є матриця А розмірністю 5*7,

2 0 0 7 8 0 4 у якій з 35 елементів тільки 10 відмінні від нуля.

10 0 0 0 0 0 0

0 0 12 0 0 0 0

0 0 0 3 0 0 5

Представлення розріджених матриць методом послідовного розміщення. Один з основних способів збереження подібних розріджених матриць полягає в запам'ятовуванні ненульових елементів в одномірному масиві й ідентифікації кожного елементу масиву індексами рядка і стовпця, як на рис. 3.4, а.

 

i Row k Column   A                                         номер рядка б)

k	Row		Colmn		A

а)

 

Рис. 3.4. Послідовне представлення розріджених матриць

 

Доступ до елементу масиву A з індексами і й j виконується вибіркою індексу і з вектора ROW, індексу j з вектора COLUM і значення елементу з вектора A. Ліворуч зазначений індекс k векторів, найбільше значення якого визначається кількістю нефонових елементів. Відзначимо, що елементи масиву обов'язково запам'ятовуються в порядку зростання номерів рядків.

Більш ефективне представлення з погляду вимог до пам'яті і часу доступу до рядків матриці показане на рис. 3.4, б. Вектор ROW зменшений, кількість його елементів відповідає числу рядків вихідного масиву A, що містять нефонові елементи. Цей вектор отриманий з вектора ROW рис. 3.4, а, так, що його і-й елемент є індексом k для першого нефонового елементуі-го рядка.

Представлення матриці А, що наведене на рис. 3.4, скорочує вимоги до обсягу пам'яті, більш ніж у 2 рази. Для великих матриць економія пам'яті дуже важлива. Спосіб послідовного розподілу має також таку перевагу, що операції над матрицями можуть бути виконані швидше, ніж це можливо при представленні у вигляді послідовного двовимірного масиву, особливо якщо розмір матриці великий.

Представлення розріджених матриць зв'язними структурами. Методи послідовного розміщення для представлення розріджених матриць зазвичай дозволяють швидше виконувати операції над матрицями і більш ефективно використовувати пам'ять, ніж методи зі зв'язними структурами. Однак послідовне представлення матриць має визначені недоліки. Так включення і виключення нових елементів матриці викликає необхідність переміщення великої кількості інших елементів. Якщо включення нових елементів і їх виключення здійснюється часто, то повинен бути обраний описаний нижче метод зв'язних структур. Метод зв'язних структур, однак, переводить структуру даних, що представляється, в інший розділ класифікації типів. При тому, що логічна структура даних залишається статичною, фізична структура стає динамічною.

Для представлення розріджених матриць у вигляді багатозв¢язної динамічної структури потрібна базова структура вершини як подано на рис. 3.5.

 

LEFT	UP
V	R	C

 

Рис. 3.5. Формат вершини для представлення розріджених матриць

 

Поля V, R та С цих вершин містять відповідно значення елементу матриці, його індекси рядка і стовпця. Поля LEFT і UP є покажчиками на наступний елемент для рядка і стовпця в циклічному списку, що містить елементи матриці. Поле LEFT вказує на вершину з наступним найменшим номером рядка.

На рис. 3.6 наведена багатозв¢язна структура, у якій використовуються вершини такого типу для представлення матриці А, що була описана раніше.

Циклічний список представляє всі рядки і стовпці. Список стовпця може містити загальні вершини з одним списком рядка чи більше. Для того, щоб забезпечити використання більш ефективних алгоритмів включення і вилучення елементів, всі списки рядків і стовпців мають головні вершини. Головна вершина кожного списку рядка містить нуль у полі С; аналогічно кожна головна вершина в списку стовпця має нуль у полі R.

Рядок або стовпець, що містить тільки нульові елементи, представлено головними вершинами, у яких поле LEFT або UP вказує само на себе. Може здатися дивним, що покажчики в цій багатозв¢язній структурі спрямовані вгору і вліво, внаслідок чого при скануванні циклічного списку елементи матриці зустрічаються в порядку спаду номерів рядків і стовпців. Такий метод представлення використовується для спрощення включення нових

Рис. 3.6. Багатозв¢язна структура для представлення матриці А

 

вершин у структуру. Передбачається, що нові вершини, які повинні бути додані до матриці, звичайно розташовуються в порядку спаду індексів рядків і індексів стовпців. Якщо це так, то нова вершина завжди додається після головної і не потрібно ніякого перегляду списку.