Понедельник, Июль 5th, 2010

«ТЭИС» Великанова

Под организацией значений данных понимают относительно ус-тойчивый порядок расположения записей данных в памяти ЭВМ и способ обеспечения взаимосвязи между записями.
Организация значений данных может быть линейной и нелинейной.
Среди линейных методов выделяются последовательная и цепная организации данных. При последовательной организации дан-ных записи располагаются в памяти строго одна за другой, без про-межутков, в той последователь-ности, в которой они обрабаты-ваются. Последовательная органи-зация данных обычно и соответст-вует понятию «массив» (файл).
Адреса промежуточных записей фиксированной длины в массиве задаются формулой :
A(i)=A(1)+(i-1)*L,
где А(1) — начальный адрес первой записи; A(i) — начальный адрес i-й записи; L — длина одной записи.
Последовательная организация данных (на примере массива) :
Условие упорядоченности записей в массиве (и вообще для линейной организации данных) выглядит сле-дующим образом:
p(i) <= p(i + 1) — упорядоченность по возрастанию; р(i) >= p(i + 1) — упорядоченность по убыванию.
Поэтому для каждого метода орга-низации данных требуется анализи-ровать следующие величины:
? время формирования данных, т.е. время создания в памяти ЭВМ так или иначе упорядоченного представления данных (упорядочение способно ускорить выполнение алгоритмов поиска данных);
? время поиска данных. Как известно, условия поиска (выборка) на практике могут быть достаточно разнообразные. Анализируются обычно простейший и наиболее распростра-ненный случаи (поиск по совпадению) — «Найти записи, у которых значение ключевого атрибута равно заранее известной величине q»;
? время корректировки данных. Из всех воз-можных вариантов корректировки учитывается включение или исключение одной;
? объем дополнительной памяти, расходуемой под служебную информацию (например, адреса связи).
При анализе алгоритмов необходим еще ряд допущений, обеспечивающих использование равномер-ного распределения вероятностей для всех случайных величин, описывающих работу алгоритма. В том числе :
? распределение значений ключевых атрибутов в массиве из М записей— равномерная, некоторая заранее известная величина;
? значение q при поиске по совпадению выбрано случайно, это означает, что поиск с одинаковой вероятностью 1/М может закончиться на любой записи массива;
? положение включаемой (исключаемой) записи при корректировке определяет-ся теми же вероятностями, что и при поиске.
Процедура упорядочения состоит из серии сравнений ключевых атрибутов и тех или иных перераспределений запи-сей по результатам сравнения.
Минимальное число сравнений, необходимое для упорядочения массива из М записей, определяется как С = logM! (где С – число сравнений, М – число записей в массиве), что соответствует минимально возможному числу вопросов о состоянии массива с возможными ответами типа «да — нет». Условимся, что фун-кция log обозначает логарифм по основанию 2.

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

Категория: Лекции