Моделирование представления в памяти таблиц

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

Рубрика Программирование, компьютеры и кибернетика
Вид лабораторная работа
Язык русский
Дата добавления 22.12.2011
Размер файла 678,8 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Лабораторная работа №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


Подобные документы

  • Универсальная подпрограмма по записи элементов и атрибутов из таблицы XML в различные массивы, в зависимости от раздела. Алгоритм трехмерной визуализации. Классы разбора таблицы XML по элементам и атрибутам. Алгоритмы работы с двухмерными объектами.

    дипломная работа [425,9 K], добавлен 06.03.2013

  • Сравнительный анализ статической и динамической памяти. Быстродействие и потребление энергии статической памятью. Объем памяти микросхем. Временные диаграммы чтения и записи памяти. Микросхемы синхронной и асинхронной памяти. Режимы модулей памяти.

    презентация [114,2 K], добавлен 27.08.2013

  • Объем двухпортовой памяти, расположенной на кристалле, для хранения программ и данных в процессорах ADSP-2106x. Метод двойного доступа к памяти. Кэш-команды и конфликты при обращении к данным по шине памяти. Пространство памяти многопроцессорной системы.

    реферат [28,1 K], добавлен 13.11.2009

  • Стратегии размещения информации в памяти. Алгоритмы распределения адресного пространства оперативной памяти. Описание характеристик модели и ее поведения, классов и элементов. Выгрузка и загрузка блоков из вторичной памяти. Страничная организация памяти.

    курсовая работа [708,6 K], добавлен 31.05.2013

  • Схема распределения памяти, соответствующая пользовательской трактовке распределения памяти. Перемещение с помощью таблицы сегментов. Аппаратная поддержка сегментного распределения памяти. Сегментно-страничная организация памяти с двухуровневой схемой.

    лекция [1,5 M], добавлен 24.01.2014

  • Объявление, выделение, освобождение памяти под динамические массивы. Обращение к элементам. Решение задач с использованием динамических массивов на языке C++. Разработка и реализация программы для формирования и обработки динамического двумерного массива.

    курсовая работа [813,4 K], добавлен 13.06.2014

  • Проектирование микропроцессорного устройства для записи и чтения данных из памяти flash-типа и осуществления взаимодействия с персональным компьютером посредством универсальной последовательной шины (USB). Программное обеспечение для устройства.

    курсовая работа [868,3 K], добавлен 23.12.2012

  • Особенности инициализации регистров для дисковых операций чтения, записи и верификации. Анализ метода доступа к дисковой памяти, поддерживающей использование оглавления, блокирование и разблокирование записей. Обеспечение адресации дисковых секторов.

    лабораторная работа [43,4 K], добавлен 20.11.2012

  • Средства машинного хранения данных, используемые в персональных компьютерах. Особенности механизмов чтения-записи. Контроль достоверности хранимых в памяти данных. Уровни кэш-памяти. Политика записи при кешировании, сравнение производительности.

    презентация [2,7 M], добавлен 10.08.2013

  • Методы расчета, схемотехнического проектирования и конструирования элементов и блоков ЦВМ. Разработка регистра, схемы записи и считывания из оперативной памяти. Применение макроопределений при моделировании устройств и построении принципиальных схем.

    курсовая работа [1,1 M], добавлен 12.02.2013

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.