Нелинейная организация данных. Методы ускоренного доступа к данным

1. Отбросив внешние скобки, перенумеруем оставшиеся скобки в данном списке:

2. Из списка выделяются три элемента, обозначим их:
• сложный элемент, Подсписок 1 - (b, (a, (c, (n)), b), (b, a));
• простой элемент – a;
• сложный элемент, Подсписок 2 - (b, (a, ( ))).
3. На первом уровне проставим три звена связи для этих элементов (рис. 2.8).
4. На втором уровне раскроем сложные элементы:

• Подсписок 1 содержит три элемента:

• простой элемент – b;
• сложный элемент, Подсписок 3 - (a, (c, (n)), b);
• сложный элемент, Подсписок 4 - (b, a).

• Подсписок 2 содержит два элемента:

• простой элемент – b;

• сложный элемент, Подсписок 5 - (a, ( )).

Таким образом, на втором уровне в  графической интерпретации будут  звенья связи трех элементов из Подсписка 1 и двух элементов из Подсписка 2 (всего 5).

5. На третьем уровне раскроем Подсписок 3, Подсписок 4 и Подсписок 5:

• Подсписок 3 содержит три элемента:

• простой элемент – a;
• сложный элемент, Подсписок 6 - (c, (n));
• простой элемент – b.

• Подсписок 4 содержит два элемента:

• простой элемент – b;

• простой элемент – a.

• Подсписок 5 содержит два элемента:

• простой элемент – a;

• сложный элемент, Подсписок 7 - ( ).

На третьем уровне в графической интерпретации будут звенья связи трех элементов из Подсписка 3, двух элементов из Подсписка 4 и Подсписка 5 (всего 7).

6. На четвертом уровне раскроем Подсписок 6, он содержит два элемента:
• простой элемент – с;
• сложный элемент, Подсписок 8 - (n).

На четвертом уровне в графической  интерпретации будут звенья связи  двух элементов из Подсписка 6.

7. На пятом уровне раскроем Подсписок 8, он содержит один простой элемент – n.

На пятом уровне в графической  интерпретации будет звено связи  одного элемента из Подсписка 8.

8. На шестом уровне проставим собственные значения записей: a, b, c, n.
9. Далее, адреса связей каждого звена по уровням соединяются с соответствующими элементами, им подчиненными.

Графическая интерпретация списка ((b, (a, (c, (n)), b), (b, a)), a, (b, (a, ( )))) представлена на рисунке 2.8.

Рисунок 2.8 – Графическая интерпретация списка

 

 

3. МЕТОДЫ УСКОРЕННОГО ДОСТУПА К ДАННЫМ
1. Адресные функции

Ускорение доступа к данным достигается  применением принципиальных методов  размещения информации и ее поиска либо путем создания массивов вспомогательной информации о хранимых данных. Расстановка записей происходит в соответствии с адресными функциями двух видов: i = A – c и i = ОСТ(A/m).

Адресной функцией называется зависимость i = f(А), где i – номер (адрес) записи; А – значение ключевого атрибута.

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

Простейшая адресная функция имеет вид: i = А – с, где с – константа.

Необходимо определить минимальное  значение ключевого атрибута А_min и максимальное значение А_max. Тогда с = А_min – 1. Необходимый участок памяти для данных должен иметь размер [А_max – А_min + 1] – запись. Записи-синонимы связываются в цепочки с помощью адресов связи, они занимают дополнительную (резервную) память.

Недостатком адресной функции вида i = А – с является большой объем неиспользуемой памяти, если А_max – А_min много больше, чем количество записей М исходного массива.

Задание 4. Построить адресную функцию вида i = A – c, согласно выбранному варианту.

34, 36, 21, 27, 33, 37, 30, 38, 39, 28, 36, 29, 37, 29, 30, 35, 32

Рассмотрим размещение записей  согласно адресной функции i = A – c. Для этого определим минимальное значение ключевого атрибута A_min и максимальное значение A_max.

A_min = 21, A_max = 39.

Так как c = A_min – 1, тогда получаем c = 21 – 1 = 20, следовательно, i = A – 20.

Необходимый участок памяти для  данных должен иметь размер [A_max - A_min + 1] - запись: [A_max - A_min + 1] = 39 – 21 + 1 = 19 записей.

Определим размещение записей  согласно адресной функции, i = A – с:

 

i = 34 – 20 = 14

i = 36 – 20 = 16

i = 21 – 20 = 1

i = 27 – 20 = 7

i = 33 – 20 = 13

i = 37 – 20 = 17

i = 30 – 20 = 10

i = 38 – 20 = 18

i = 39 – 20 = 19

i = 28 – 20 = 8

i = 36 – 20 = 16

i = 29 – 20 = 9

i = 37 – 20 = 17

i = 29 – 20 = 9

i = 30 – 20 = 10

i = 35 – 20 = 15

i = 32 – 20 = 12

 

 

Организация данных записей изображена на рисунке 3.1.

Рисунок 3.1 – Организация записей в соответствии с адресной функцией вида i = A – с

 

Указанного выше недостатка (большой  объем неиспользуемой памяти) лишена адресная функция вида i = ОСТ (А/m), где m – целое число; ОСТ – остаток от деления А на m.

Значение m принимается равным простому числу, которое непосредственно больше либо меньше числа записей М: m = М ± 1. Выделяются две зоны памяти – основная и резервная. Основная зона содержит m записей. Резервная зона предназначена для размещения записей–синонимов. При формировании данных согласно адресной функции сначала производится заполнение основной зоны. Если при этом позиция основной зоны, полученная при вычислении, уже занята, то текущая запись помещается в резервную зону и адресуется из позиции основной зоны. В дальнейшем при такой ситуации наращивается цепочка записей в резервной зоне.

Задание 5. Построить адресную функцию вида i = ОСТ(A/m), согласно выбранному варианту.

77, 89, 20, 41, 82, 36, 56, 45, 89, 22, 26, 82, 37, 82, 57, 83, 42

Рассмотрим исходный массив, значение m принимается равным простому числу, которое непосредственно больше либо меньше числа записей M: .

Определим число записей M и значение m: M = 17, m =17 – 1 = 16.

Таким образом, адресная функция примет вид: i = ОСТ(A/16).

Определим размещение записей  согласно адресной функции, i = ОСТ(A/m):

 

i = ОСТ(77/16) = 13

i = ОСТ(89/16) = 9

i = ОСТ(20/16) = 4

i = ОСТ(41/16) = 9

i = ОСТ(82/16) = 2

i = ОСТ(36/16) = 4

i = ОСТ(56/16) = 8

i = ОСТ(45/16) = 13

i = ОСТ(89/16) = 9

i = ОСТ(22/16) = 6

i = ОСТ(26/16) = 10

i = ОСТ(82/16) = 2

i = ОСТ(37/16) = 5

i = ОСТ(82/16) = 2

i = ОСТ(57/16) = 9

i = ОСТ(83/16) = 3

i = ОСТ(42/16) = 10

 

Организация записей в соответствии с адресной функцией вида i = ОСТ(A/m) показана на рисунке 3.2.

Рисунок 3.2 - Организация записей в соответствии с адресной функцией вида i = ОСТ(A/m)

 

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

 

2. Способы организации индексируемого массива

Индексом называется набор адресов и ключей записей, которые выбираются из основного массива по определённому закону. Отдельный элемент набора индексов также называется индексом, хотя это не соответствует значению слова index—список.

Существует несколько различных способов организации индексируемого массива. Рассмотрим два из них – это индексно-последовательный массив и рандомизированный индекс.

Индексно-последовательный массив представляет собой последовательный массив индексов, в который из основного массива выносится информация о записях, номера которых образуют арифметическую прогрессию с шагом d > 1, причем первый индекс адресует первую запись. Основной массив, дополненный таким индексом, обычно называется индексно-последовательным.

Индексы такого типа называются К – индексами (от слова «ключ»). Шаг арифметической прогрессии для К – индексов равен: , где M – количество элементов в исходном массиве.

Рандомизированный индекс. Если ключи записей, информация о которых выносится в индекс, приближенно образуют арифметическую прогрессию, получаем ситуацию с адресной функцией для индекса (рандомизация индекса), причём первый индекс адресует первую запись.

Индексы такого типа называются А – индексами (от слова «адрес»).

Точное описание рандомизированного индекса состоит в следующем. А – индекс с номером i хранит адрес записи основного массива, ключ которой равен или непосредственно больше значения: , где z – константа (шаг арифметической прогрессии), р₁ – значение ключа первой записи основного массива.

Точной формулы для шага арифметической прогрессии z для А – индексов не существует, используют формулу: , где p_i – значение ключа i-й записи.

Задание 6. Построить А – и К – индексы. Вставку провести с учетом значения 55 и удаление с учетом значения 36.

25, 52, 33, 66, 29, 36, 34, 41, 38, 37, 23, 34, 29, 33, 24, 57, 35

Упорядочим по возрастанию исходный массив. Массив будет иметь следующий  вид (рис. 3.3, а). Для построения А – и К – индексов вычислим шаг арифметической прогрессии d, z.

Вычислим шаг арифметической прогрессии для К – индексов:

M = 17, . Получаем К – индексы (рис. 3.3. б).

Вычислим шаг арифметической прогрессии для А – индексов:

max(52 – 41) = 11, .

Определим А – индексы, используя формулу , где p_i – значение ключа i-й записи, p₁ – значение ключа первой записи, z - шаг арифметической прогрессии:

z = 22;

p₁ = 23, А₁ = 0100;

(т.к. в исходном массиве такого значения ключа нет, то выберем следующее большее, т.е. 52), А₂ = 0114. Получаем А – индексы (рис. 3.3. в).

Рисунок 3.3 – Основной массив организации данных (а);

К – индексы с учетом корректировки (б); А – индексы с учетом корректировки (в)

 

При корректировке записей индексы  также должны изменяться: всегда К – индексы и реже А – индексы. При включении новой записи с ключом q определяем К – индекс, такой, что K_i–1 £ q < K_i, где i – номер К – индекса. Затем всем К – индексам с номером i и больше присваиваем значения ключей и адресов тех записей, которые непосредственно предшествуют ранее зафиксированным в этих индексах записям основного массива. Аналогично при удалении записи с ключом q всем К – индексам с номером i и больше присваиваем значения ключей и адресов тех записей, которые непосредственно следуют за ранее указанными в этих индексах записями основного массива. При корректировке массива изменяются меньше значений А – индексов, чем К – индексов. Значения К – и А – индексов представлены с учетом изменений на рисунке 3.3 (б, в).

Таким образом, А – индексы целесообразнее К – индексов – они характеризуются меньшим объемом памяти, необходимым для их размещения, а также более быстрым поиском при достаточно большом количестве элементов в массиве.

 

4. ЗАКЛЮЧЕНИЕ

При выполнении курсового проекта  были изучены теоретические основы методов и средств описания экономических информационных систем.

Про нелинейную организацию данных необходимо отметить, что по критерию времени формирования данных бинарное дерево имеет определенные преимущества перед последовательным массивом, несмотря на то, что процессы формирования описываются одинаковыми формулами. По времени поиска последовательный массив и бинарное дерево предпочтительнее списка. Минимальное время корректировки характерно для бинарного дерева, а минимальный объем памяти – для последовательного массива.