2. Критерии и методы оценки вычислительных алгоритмов.

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

Упорядоченная структура эффективна для организации быстрого поиска информации. Выходные документы, выводимые на печать, полученные на основе отсортированных данных, удобны для дальнейшего использования человеком. Многие алгоритмы задач управления вообще рассчитаны на использование только упорядоченных последовательных структур данных. Отсортиро­ванные данные позволяют организовать быструю обработку нескольких массивов.

Преимущества упорядоченных последовательных структур данных, в частности, хорошо видны на примере с операцией пере­сечения двух массивов, определяемой как выбор записей с ключе­вым признаком, значение которого есть и в первом и во втором массиве. Если исходные массивы длиною М записей каждый не отсортированы по указанному признаку, то пересечение массивов потребует выполнения С=КМ2 сравнений пар признаков, где 0,5£К£1. Когда массивы отсортированы, С»2М.

Эти обстоятельства делают сортировку данных обязательной операцией, которая сплошь и рядом предшествует собственно об­работке данных.

Время сортировки данных, которые можно в известной мере считать и трудоемкостью формирования упорядоченной последо­вательной структуры, пропорционально числу сравнений пар при­знаков различных записей (С), в свою очередь зависящему от ко­личества записей в массиве (М). Лучший по времени метод сор­тировки — метод слияния — характеризуется числом сравнений

С = М log2М

и временем сортировки

T = t ´ C = tM log2M,

где t—константа с размерностью времени.

Метод слияния использует для сортировки резерв памяти дли­ной в половину массива.

Другие методы упорядочения последовательных структур дан­ных уступают методу слияния в быстродействии.

Метод слияния применим и для упорядочения строчных струк­тур данных, причем здесь не требуется резерва памяти, посколь­ку вместо пересылки записей производятся манипуляции с адреса­ми связи.

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

Путем первого просмотра основного массива выполняется раз­метка памяти. Фиксируются адреса полей и значения ключей в каждой группе. В таблице они изображены столбцами, в каждом из которых имеются значение ключа и 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"— длина поля, хра­нящего номер строки или столбца.