ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Ilia Kantor                          2:5020/1815.6  22 Jan 2002  21:22:34
 To : All
 Subject : ЧаВо вопpос N12
 -------------------------------------------------------------------------------- 
 

 === Cut ===
 ===========================================================================
 
 > 12. Есть большой файл. Как его отсортировать ?  Многофазная сортировка.
 
 ===========================================================================
 
   В другом вопросе описывается простейшая сортировка слиянием. Ее вполне можно
  применить к любому файлу и она будет работать.
 
   иже мы разберем серьезно улучшенный алгоритм внешней сортировки слиянием
 работающий намного быстрее.
 
                       Многофазная сортировка слиянием.
 
 Слиянием называется процесс объединения нескольких
 упорядоченных серий(т.е упорядоченных списков) в  одну.
 
  Пример для 3-х серий, слияемых на 4-ю:
 
     3 7 9      3 7 9        3 7 9          7 9             7 9
   { 2 4 6  1 { 2 4 6  1 2 { 4 6    1 2 3 { 4 6   1 2 3 4 { 6
     1 5 8      5 8          5 8            5 8             5 8
 
                7 9                7 9                 9
    1 2 3 4 5 { 6    1 2 3 4 5 6 { 8     1 2 3 5 6 7 { 8   1 2 3 4 5 6 7 8 9 {
                8
 
   Hа каждом шаге мы беpем наименьший из начальных элементов входных
 серий и перемещаем в конец выходной серии.
   Каждая операция слияния серий, очевидно, требует n пересылок
  элементов, где n - общее число элементов серий.
 
     В процессе сортировки мы будем оперировать лентами - структурами
  данных, где в каждый момент нам доступен либо первый элемент, либо
  следующий элемент после уже прочитанного.
     В реальной ситуации в качестве лент выступают односвязные
  списки или файлы.
 
     Пусть у нас имеется N лент: N - 1 входная и одна пустая. Мы будем
  слиять элементы со входных лент на выходную, пока какая-либо из них не
  опустеет. Затем она станет входной.
 
       Пример сортировки с шестью лентами, содержащими всего 65 серий. Серии
  обозначены буквами fi. Цифры - количество серий, находящихся на ленте
  в начале очередного шага.
 
             f1      f2     f3     f4     f5     f6
 
             16      15     14     12     8
             \--------\-----\-------\-----\-------|
                                                  \|/
             8       7      6      4      0       8
             \-------\------\------\------|-------/
                                         \|/
             4       3      2      0      4       4
             \-------\------\------|------/-------/
                                  \|/
             2       1      0      2      2       2
             \-------\------|------/------/-------/
                           \|/
             1       0      1      1      1       1
             \-------|------/------/------/-------/
                    \|/
             0       1      0      0      0       0
 
    Стрелки показывают процесс слияния. Hапример, на втором шаге мы
  слияем с f1, f2, f3, f4 и f6 на f5,  пока одна из лент не опустеет.
 
       В каждый момент времени слияние происходит на пустую ленту с остальных,
  поэтому число требующихся проходов приблизительно равно log n.
                                                             N
 
  Далее нам понадобятся числа Фибоначчи порядка p.
  Они определяются следующим образом:
  f_(i+1) = f_i + f_(i-1) + ... + f_(i-p) для i >=p,
  f_p = 1,
  f_i = 0 для 0 <= i < p.
 
       Очевидно, обычные числа Фибоначчи имеют порядок 1.
 
       В данном примере распределение начальных серий побрано искусственно.
  Исходные числа серий для такой идеальной многофазной сортировки должны
  быть суммами n-1 , n-2 , ... , 1 последовательных чисел Фибоначчи
  порядка n-2.
 
  Из этого следует, что наш алгоритм многофазного слияния применим только
  к таким входным данным, в которых число серий есть сумма n-1 таких сумм
  Фибоначчи.
 
  Что делать, если число начальных серий не является такой идеальной суммой?
   Ответ прост - предположим существование гипотетических пустых серий,
  таких что сумма реальных и гипотетических серий дает идеальную сумму.
  Пустые серии называются фиктивными или холостыми сериями.
 
   Холостые серии по возможности равномерно распределяются по лентам, чтобы
  реальное слияние (в котором холостые серии участвуют лишь 'в уме')
  проходило с как можно большего количества лент.
 
       Сначала все данные располагаются на одной ленте. Лента читается и
  отрезки распределяются по другим лентам, имеющимся в системе. после того,
  как созданы начальные отрезки, они сливаются, как описано выше. Один из
  методов, который можно использовать для создания начальных отрезков, состоит
  в чтении порции записей в память, их сортировке и записи результата на
  ленту. Выбор с замещением(см. другой вопрос) позволяет нам получать более
  длинные отрезки. Этот алгоритм работает с буфером, располагающимся в
  оперативной памяти. Сначала мы заполняем буфер. Затем повторяем следующие
  шаги до тех пор, пока не будут исчерпаны входные данные:
 
     * Выбрать запись с наименьшим ключом, т.е. с ключом, значение которого >=
       значения ключа последней прочитанной записи.
     * Если все "старые" ключи меньше последнего ключа, то мы достигли конца
       отрезка. Выбираем запись с наименьшим ключом в качестве первого
       элемента следующего отрезка.
     * Записываем выбранную запись.
     * Заменяем выбранную и записанную запись на новую из входного файла.
 
       Hа следующей таблице выбор с замещением иллюстрируются для совсем
  маленького файла.
 
       Hачало файла - справа. Чтобы упростить пример, считается, что в буфер
  помещается всего лишь 2 записи. Конечно, в реальных задачах в буфер
  помещаются тысячи записей. Мы загружаем буфер на шаге В и записываем в
  выходной файл запись с наименьшим номером >= 6 на шаге D. Ею оказалась
  запись с ключом 7. Теперь мы заменяем ее на новую запись из входного файла -
  с ключом 4. Процесс продолжается до шага F,  где мы оказывается, что
  последний записанный ключ равен 8 и все ключи меньше 8. В этот момент мы
  заканчиваем формирование текущего отрезка и начинаем формирование
  следующего.
 
                       Шаг    Вход     Буфер     Выход
                        A  5-3-4-8-6-7
                        B  5-3-4-8     6-7
                        C  5-3-4       8-7   6
                        D  5-3         8-4   7-6
                        E  5           3-4   8-7-6
                        F              5-4   3 | 8-7-6
                        G              5     4-3 | 8-7-6
                        H                    5-4-3 | 8-7-6
 
       Обратите внимание мы храним записи в буфере до тех пор, пока не
  наступит время записать их в выходной файл. Если вход случаен, средняя длина
  отрезков равна примерно удвоенной длине буфера. Однако, если данные хоть
  как-то упорядочены, отрезки могут быть очень длинными. Вот почему этот
  метод, вообще говоря, более эффективен промежуточных, частичных сортировок.
 
  Прочитав из входного файла очередную запись, мы ищем наименьший ключ,
  который >= последнего считанного. При этом мы, конечно, можем просто
  сканировать записи в буфере. Однако, если таких записей тысячи, время поиска
  может оказаться недопустимо большим. Если на этом этапе использовать
  двоичные деревья, нам понадобится всего лишь log n сравнений.
 
                                   Реализация
 
  В реализации внешней сортировки на ANSI-C функция makeRuns вызывает readRec
  для чтения очередной записи. В функции readRec используется выбор с
  замещением (с двоичными деревьями) для получения нужной записи, а makeRuns
  распределяет записи согласно ряду Фибоначчи. Если количество отрезков
  оказывается вне последовательности Фибоначчи, в начало каждого файла
  добавляются пустые отрезки(холостые серии). Затем вызывается функция
  mergeSort, которая производит многофазное слияние отрезков.
 
 -----------------------------------------------------------
   Пpилагающиеся исходники смотpи в основном FAQ'е, запостенном несколько дней
 назад.
 
  === Cut ===
 
             Закрой за мной дверь, я ухожу.. [Team Кино]
 --- GoldEd 3.00.Alpha4+
  * Origin: http://algolist.da.ru - Мир Алгоритмов (2:5020/1815.6)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор