Claw.ru | Рефераты по информатике, программированию | Экономические информационные системы Экономические информационные системы | Категория реферата: Рефераты по информатике, программированию | Теги реферата: менеджмент, бесплатные доклады скачать | Добавил(а) на сайт: Rybakov. Предыдущая страница реферата | 1  2  3  4 | Следующая страница реферата B	E	A	C	D
0100	0100	0140	0140	0220
0220	0140	0220	0240
	0240

Путем первого просмотра основного массива выполняется разметка памяти. Фиксируются адреса полей и значения ключей в каждой группе. В таблице они изображены столбцами, в каждом из которых имеются значение ключа и 4 адреса.

Затем основной массив просматривается второй раз от записи к записи. Во всех его записях проверяется наличие ключей, значения которых зафиксированы ранее в инвертированном массиве, и на этой основе заполняются адреса в группах. Именно поэтому в таблице группы не упорядочены по ключу. Последняя операция—сортировка групп по значениям ключа и уплотнение инвертированного массива.

При первом просмотре основного массива производится р пересылок значений ключей в поле памяти V1. Во время второго просмотра в инвертированный массив пересылаются М адресов записей основного массива. Сортировка групп методом слияния потребует времени tplog2p. Наконец, уплотнение инвертированной структуры данных означает пересылку байт за байтом всего поля за исключением первой группы. Общее время формирования инвертированного массива составляет:

T = t1(pl + Ml' + V1)+ tplog2p,

где t1 — время пересылки байта, l — средняя длина ключа, l' — длина адреса, р — число разных значений ключей.

Это время, как правило, превышает время формирования упорядоченной последовательной структуры данных.

Среднее число сравнений, необходимое для построения бинарного дерева, равно: С=1,39М log2М, если М достаточно велико. Формирование бинарного дерева требует больших затрат времени и памяти, чем формирование строчной структуры данных.

Построение неуплотненной табличной структуры данных заключается в создании вектора описания записей, вектора описания ключей и матрицы значений ключей. При этом выполняются пересылки адресов и ключей. Время формирования неуплотненной табличной структуры из m строк и п столбцов составляет:

T = t1(l'(m + n) + l mn).

Для формирования табличной структуры данных с логической шкалой необходимо иметь вектор описания записей и вектор описания ключей. Создание логической шкалы для одной строки требует п сравнений признаков и п пересылок битов. С учетом этого общее время формирования табличной структуры данных с логической шкалой равно:

T = t1l'(m + n) + mn(t + t1) + tdlmn, К

где t — время одного сравнения и d = — — плотность ненулевых

тп

значений ключевого признака (К — число ненулевых значений ключевого признака).

Первое слагаемое описывает построение вектора описания записей и вектора описания ключей. Второе слагаемое относится к формированию всех логических шкал структуры Третье слагаемое учитывает время пересылки ненулевых значений ключевого признака в уплотненные строки таблицы.

Для формирования табличной структуры данных, уплотненной методом индексных пар, ключевые признаки каждой записи последовательно сравниваются с нулем. Ненулевые ключи сопровождаются номерами их строки и столбца в матрице и помещаются в массив групп. Номера строки и столбца ключевого признака формируются путем прибавления 1 после каждого сравнения к номеру столбца, а при смене строки — к номеру строки. Время этих операций составляет:

T = t1l'(m + n) + mn (t + t2) + t1dmn(l + 21"),

где t2 — время одной операции сложения, а 1"— длина поля, хранящего номер строки или столбца.

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

Уплотнение табличной структуры данных с помощью логической шкалы эффективнее по времени формирования структуры, чем метод индексных пар, так как t1 < t2 и l < l + 2l".

Рекомендуем скачать другие рефераты по теме: новейшие рефераты, изложение по русскому 9 класс.