![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Многофазная сортировка
При использовании рассмотренного выше метода сбалансированной многопутевой внешней сортировки на каждом шаге примерно половина вспомогательных файлов используется для ввода данных и примерно столько же для вывода сливаемых серий. Идея многофазной сортировки состоит в том, что из имеющихся 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 – константы При большом количестве элементов с одинаковым значением адреса будет получены кластеры (блоки) - последовательности подряд идущих записей, соответствующих одному и тому же адресу. Методы разрешения коллизий:
|