Сбалансированное многопутевое слияние.

В основе метода внешней сортировки сбалансированным многопутевым слиянием

является распределение серий исходного файла по m вспомогательным файлам B 1, B 2,...,

B m.. Затем производится их слияние первых серий каждого файла в файл C1, вторых серий

– в файл C2 и т.д. На следующем шаге производится слияние файлов C 1, C 2,..., C m в файлы

B 1, B 2,..., B m и т.д., пока в B 1 или C 1 не образуется одна серия.

 

Простой пример трёхпутевого слияния:

 

 

Многофазная сортировка

При использовании рассмотренного выше метода сбалансированной многопутевой

внешней сортировки на каждом шаге примерно половина вспомогательных файлов

используется для ввода данных и примерно столько же для вывода сливаемых серий. Идея

многофазной сортировки состоит в том, что из имеющихся m вспомогательных файлов

(m-1) файл служит для ввода сливаемых последовательностей, а один - для вывода

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

использовать для вывода серий, получаемых при слиянии серий нового набора (m-1)

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

распределяются по m-1 вспомогательному файлу, а затем выполняется многопутевое

слияние серий из (m-1) файла с записью в файл m, пока один из них не станет пустым..

 

Метод трехфазной внешней сортировки дает желаемый результат и работает

максимально эффективно (на каждом этапе сливается максимальное число серий), если

начальное распределение серий между вспомогательными файлами описывается суммами

соседних числел Фибоначчи.

 

 

19) Понятие хеширования. Построение хеш функции. Разрешение коллизий, линейное рехеширование, случайное рехеширование, квадратичное рехеширование, метод цепочек (списковое и матричное представление)

 

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

 

Хеш-таблица – это обычный массив с необычной адресацией, задаваемой хеш-

функцией.

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

 

Если входной поток информации абсолютно случаен, то в качестве хеш-функции можно использовать, например, функцию:

h (a)= code (a) mod N

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

функция вычисляет один и тот же адрес: ki ≠ kj; h(ki) = h(kj). Данный случай носит

название коллизия, а такие ключи называются ключи-синонимы.

 

Разрешение коллизий достигается путём рехеширования – специального алгоритма,

который используется при размещении новой записи или при поиске существующей.

 

h(a)=(B code(a) +C) mod N, где B и C – константы

При большом количестве элементов с одинаковым значением адреса будет получены

кластеры (блоки) - последовательности подряд идущих записей, соответствующих

одному и тому же адресу.

Методы разрешения коллизий: