Моделирование представления в памяти таблиц
Краткое сожержание материала:
Размещено на
Лабораторная работа №1
Тема: Моделирование представления в памяти таблиц
Цель: Приобретение и закрепление навыков размещения в памяти таблиц. Получение начальных представлений о модульности программы с точки зрения обрабатываемых данных.
Задание: Разработать способ экономного размещения в памяти заданной разреженной таблицы. Разработать процедуры/функции, обеспечивающие доступ к элементам таблицы по номерам строки и имени столбца. В контрольной программе обеспечить запись и чтение всех записей таблицы. Произвести хронометраж выполнения операций чтения и записи элементов в массивы.
Описание алгоритма работы программы
1. Индивидуальное задание.
Все нулевые элементы расположены в шахматном порядке, начиная со
2-го элемента 1-й строки
2. Выбор метода.
Во внутреннем представлении нет необходимости хранить элементы, нулевые по определению:
M[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
NewIndex:=round(d+(x/2 + 0.1))
где x, y - номера столбца и строки соответственно;
XM - число элементов в строке.
3. Описание переменных
Переменные, глобальные для всего модуля:
*matrix - массив, представляющий матрицу традиционным образом, используется для сравнения времен доступа;
*arrp - массив, представляющий сжатую матрицу;
*XM - размер матрицы
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;
uses crt, dos;
Var
arrp: array[1..5050] of integer;
matrix: array[1..100, 1..100] of integer;
XM : integer;
start, finish, x1, x2: longint;
hour, min, sec, ssec: word;
Function NewIndex(y, x : integer) : integer;
var i, j: integer;
d: real;
begin
d:=0;
if XM mod 2 = 0 then
d:= (y-1)*(XM/2)
else
for i:=1 to y-1 do
begin
if i mod 2 = 0 then
d:=d+(XM-1)/2
else
d:=d+(XM+1)/2;
end;
NewIndex:=round(d+(x/2 + 0.1));
end;
Function PutTab(y,x,value : integer) : integer;
begin
if (x+y) mod 2 <> 0 then PutTab:=0
else begin
arrp[NewIndex(y,x)]:=value;
PutTab:=value;
end;
end;
Function GetTab(y,x: integer) : integer;
begin
if (x+y) mod 2 <> 0 then
GetTab:=0
else GetTab:=arrp[NewIndex(y,x)];
end;
Function time: longint;
begin
Gettime (hour, min, sec, ssec);
time:= sec*100+min*6000+ssec
end;
Var
x, y : integer;
k, h: integer;
begin clrscr;
clrscr;
XM:=20;
k:=1;
for y:=1 to XM do
for x:=1 to XM do
begin
h:=PutTab(y,x,k);
k:=k+1;
end;
writeln('====Массив====');
start:= time;
for y:=1 to XM do begin
for x:=1 to XM do
begin
write(GetTab(y,x):3);
end;
writeln;
end;
finish:= time;
x1:=finish - start;
writeln;
k:=0;
for y:=1 to XM do
for x:=1 to XM do
begin
k:=k+1;
if (x+y) mod 2 <> 0 then
matrix[y][x] := 0
else
matrix[y][x] := k;
end;
writeln('====Матрица после обработки====');
start:= time;
for y:=1 to XM do begin
for x:=1 to XM do
write(matrix[y][x]:3);
writeln;
end;
finish:= time;
x2:=finish - start;
writeln('time1 = ', x1);
writeln('time2 = ', x2);
writeln('<< >>');
for y:=1 to round(XM*XM/2+0.1) do
write(arrp[y]:4);
writeln; writeln;
readln;
end.
<<матрица выборки из сжатого представления массива>>
1 0 3 0 5 0 7 0 9 0
0 12 0 14 0 16 0 18 0 20
21 0 23 0 25 0 27 0 29 0
0 32 0 34 0 36 0 38 0 40
41 0 43 0 45 0 47 0 49 0
0 52 0 54 0 56 0 58 0 60
61 0 63 0 65 0 67 0 69 0
0 72 0 74 0 76 0 78 0 80
81 0 83 0 85 0 87 0 89 0
0 92 0 94 0 96 0 98 0100
<< матрица >>
1 0 3 0 5 0 7 0 9 0
0 12 0 14 0 16 0 18 0 20
21 0 23 0 25 0 27 0 29 0
0 32 0 34 0 36 0 38 0 40
41 0 43 0 45 0 47 0 49 0
0 52 0 54 0 56 0 58 0 60
61 0 63 0 65 0 67 0 69 0
0 72 0 74 0 76 0 78 0 80
81 0 83 0 85 0 87 0 89 0
0 92 0 94 0 96 0 98 0100
time1 = 4
time2 = 4
===== Матрица (внутр.представление) =====
1 3 5 7 9 12 14 16 18 20 21 23 25 27 29 32 34 36 38 40
41 43 45 47 49 52 54 56 58 60 61 63 65 67 69 72 74 76 78 80
81 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.
Размещено на Allbest.ru
...Современные представления о функционировании памяти
Память как психологическая категория. Исследование подходов к изучению памяти в отечественной и зарубежной психологии. Роль памяти в жизни и деятельно...
Понятие памяти человека
Общие представления, виды, особенности, индивидуальные различия памяти у людей. Теории и законы, формирование и развитие памяти. Эффективность запомин...
Статистические таблицы и их использование
Значение статистических таблиц, основные правила их построения и оформления. Рациональная форма представления результатов статистической сводки и груп...
Табличный процессор MS Excel
Применение алгебры высказываний в информатике. Надстройки Microsoft Excel. Применение формул, таблиц, диаграмм. Моделирование реальных систем массовог...
Пиктограмма как средство для эффективного запоминания
Общие представления о памяти, ее материальные основы и структура. Представление информации в памяти, структура знаний и событий, процесс запоминания....