Моделирование представления в памяти таблиц
Лабораторная
работа №1
Тема:
Моделирование представления в памяти таблиц
Цель: Приобретение
и закрепление навыков размещения в памяти таблиц. Получение начальных
представлений о модульности программы с точки зрения обрабатываемых данных.
Задание: Разработать
способ экономного размещения в памяти заданной разреженной таблицы. Разработать
процедуры/функции, обеспечивающие доступ к элементам таблицы по номерам строки
и имени столбца. В контрольной программе обеспечить запись и чтение всех записей
таблицы. Произвести хронометраж выполнения операций чтения и записи элементов в
массивы.
Описание алгоритма работы программы
. Индивидуальное задание.
Все нулевые элементы расположены в шахматном
порядке, начиная со
-го элемента 1-й строки
2. Выбор метода.
Во внутреннем представлении нет необходимости
хранить элементы, нулевые по определению:
[x,y] = 0 при x + y mod 2.
Если исключить нулевые элементы из хранения и
представить матрицу в виде одномерного массива, то формула перехода от
двухкоординатного обращения к однокоординатному запишется как:
Если XM
mod 2=0 то d:=
(y-1)*(XM/2) в другом случае цикл от 1 до у-1
Если i mod 2=0 то d:=d+(XM-1)/2, иначе
d:=d+(XM+1)/2
:=round(d+(x/2 + 0.1))
где x, y - номера столбца и строки
соответственно;- число элементов в строке.
3. Описание переменных
Переменные, глобальные для всего модуля:
•matrix
- массив, представляющий матрицу традиционным образом, используется для
сравнения времен доступа;
•arrp - массив, представляющий сжатую матрицу;
4. Описание программы
Функция NewIndex
реализует вычисления по формуле (1).
Функция PutTab
проверяет условие нахождения элемента по заданию
(x+y
mod 2).
Если это так, функция возвращает 0, в противном случае при помощи функции NewIndex
вычисляется индекс в массиве arrp,
производится запись в arrp
и возврат value.
Функция GetTab
проверяет условие нахождения элемента. Если это так, функция возвращает 0, в
противном случае при помощи функции NewIndex
вычисляется индекс в массиве arrp,
и возвращаемое значение выбирается из arrp.
Алгоритм основной программы может быть разбит на
2 части.
Часть 1 предназначена для проверки правильности
формирования сжатого представления матрицы. Она работает с матрицей размера
20х20, поэтому в начале этой части задается XM:=20.
Далее формируется содержимое матрицы таким образом, чтобы в ненулевые элементы
записывались последовательно возрастающие числа. Затем проверяется правильность
доступа к матрице - при всех возможных значениях x
и y выводятся на
печать значения, возвращаемые функцией GetTab.
И наконец проверяется сжатое представление матрицы - последовательно выводится
на печать массив arrp.
Блок-схема программы
Блок-схема программы приведена в Приложении.
Текст
программы
Program LAB2;crt, dos;:
array[1..5050] of integer;: array[1..100, 1..100] of integer;: integer;,
finish, x1, x2: longint;, min, sec, ssec: word;NewIndex(y, x : integer) :
integer;i, j: integer;: real;:=0;XM mod 2 = 0 then:= (y-1)*(XM/2)i:=1 to y-1
doi mod 2 = 0 then:=d+(XM-1)/2:=d+(XM+1)/2;;:=round(d+(x/2 +
0.1));;PutTab(y,x,value : integer) : integer;(x+y) mod 2 <> 0 then
PutTab:=0begin[NewIndex(y,x)]:=value;:=value;;;GetTab(y,x: integer) :
integer;(x+y) mod 2 <> 0 then:=0GetTab:=arrp[NewIndex(y,x)];;time:
longint;(hour, min, sec, ssec);:= sec*100+min*6000+ssec;, y : integer;, h:
integer;clrscr;;:=20;:=1;y:=1 to XM dox:=1 to XM
do:=PutTab(y,x,k);:=k+1;;('====Массив====');:= time;y:=1 to XM do
beginx:=1 to XM do(GetTab(y,x):3);;;;:= time;:=finish - start;;:=0;y:=1 to XM
dox:=1 to XM do:=k+1;(x+y) mod 2 <> 0 then[y][x] := 0[y][x] := k;
end;('====Матрица
после обработки====');
start:= time;y:=1 to XM do beginx:=1
to XM do(matrix[y][x]:3);;;:= time;:=finish - start;('time1 = ', x1);('time2 =
', x2);('<< >>');y:=1 to round(XM*XM/2+0.1) do(arrp[y]:4);;
writeln;
readln;.
<<матрица
выборки из сжатого представления массива>>
0
3 0 5 0 7 0 9 0
12
0 14 0 16 0 18 0 20
0
23 0 25 0 27 0 29 0
32
0 34 0 36 0 38 0 40
0
43 0 45 0 47 0 49 0
0
63 0 65 0 67 0 69 0
72
0 74 0 76 0 78 0 80
0
83 0 85 0 87 0 89 0
92
0 94 0 96 0 98 0100
<< матрица
>>
0
3 0 5 0 7 0 9 0
12
0 14 0 16 0 18 0 20
0
23 0 25 0 27 0 29 0
32
0 34 0 36 0 38 0 40
0
43 0 45 0 47 0 49 0
52
0 54 0 56 0 58 0 60
0
63 0 65 0 67 0 69 0
72
0 74 0 76 0 78 0 80
0
83 0 85 0 87 0 89 0
92
0 94 0 96 0 98 0100= 4= 4
=====
Матрица (внутр.представление) =====
3
5 7 9 12 14 16 18 20 21 23 25 27 29 32 34 36 38 40
43
45 47 49 52 54 56 58 60 61 63 65 67 69 72 74 76 78 80
83
85 87 89 92 94 96 98 100
Поскольку
по данным результатам нельзя определить вывод, какой матрицы осуществляется
быстрей (матрицы, которая восстанавливается из сжатого представления массива
или просто матрицы которая хранится в памяти) я повторил исследование, увеличив
размер матрицы до 30х30 и повторил вывод каждой матрицы по 10 раз. Таким
образом, я получил большое время выполнение операций, и за счет этого я узнал
разницу между выполнением операций. 1 матрица вывелась за 1091 сс, а 2 - 1295
сс. Следует вывод, что матрица в сжатом виде распечатывается быстрей.
память таблица хронометраж
Во
время выполнения лабораторной работы я приобрел и закрепил навыки размещения в
памяти таблиц. Получил начальные представления о модульности программы с точки
зрения обрабатываемых данных.
Приложение
Рис. 1 - блок-схема главной
программы
Рис. 2 - блок-схема подпрограммы
NewIndex.
Рис. 3 - блок-схема подпрограммы
PutTab.
Рис. 4 - блок-схема подпрограммы
GetTab.
Рис. 5 - блок-схема подпрограммы
time.