25.Последовательный массив. Поиск в последовательном массиве.

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

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

Простейшим условием поиска является поиск по совпадению, т.е. равенство значения ключевого атрибута i-й записи p(i) и некоторого заранее заданного значения q.

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

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

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

C=M/(2*d1)+d1/2.

При n-ступенчатом поиске заранее выбираются константы n и S. На первом этапе ключевые атрибуты для сравнения с искомым ключом q выбираются из массива по закону арифметической прогрессии, начиная с р(1) и шагом dl=M/S (округление в меньшую сторону). Когда будет впервые достигнут ключ p(k)>q, выбирается шаг d2 = dl/S и организуются сравнения с этим шагом, начиная с p(k-dl). Описанные действия повторяются n раз, причем шаг на последней ступени поиска dn=l.

Минимальное число сравнений достигается при S=M^(l/n), и, кроме того, существует оптимальное n=ln(М).

Ступенчатый поиск имеет частный вариант - бинарный поиск, когда S=2.

Во всех трех случаях время поиска является функцией от числа записей М.

Конкретные выражения составляют:

• для последовательного поиска Т1~М или Т1=k1*М;

• для двухступенчатого поиска T2~SQR(M) или T2=k2(SQR(M));

• для бинарного поиска ТЗ~logM или T3=k3*logM.

26.Сравнение методов поиска данных в последовательном массиве. Корректировка последовательного массива.

Во всех трех случаях время поиска является функцией от числа записей М. Конкретные выражения составляют:

• для последовательного поиска Т1~М или Т1=k1*М;

• для двухступенчатого поиска T2~SQR(M) или T2=k2(SQR(M));

• для бинарного поиска ТЗ~logM или T3=k3*logM.

Очевидно, что функция логарифма растет с увеличением М медленнее, чем две другие функции (для Т1 и Т2), как это показано на рис.3.2.

Поэтому можно утверждать даже при неизвестных коэффициентах kl, k2, k3, что при достаточно большом числе записей М бинарный метод поиска выполняется, безусловно, быстрее двух остальных. Значения kl, k2, k3 влияют на граничную величину М, выше которой преимущество бинарного поиска безусловно.

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

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

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

При объединении основного массива с массивом изменений выполняются следующие операции (алгоритм слияния):

• ключ очередной записи основного массива сравнивается с ключом очередной записи массива изменений, и запись с меньшим значением ключа добавляется в новый массив (результат слияния);

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