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

Cтраница 1

Идеальное распределение серии по двум последовательностям. [1]

Многофазная сортировка более эффективна, чем сбалансированная, поскольку она имеет дело с N-1 - путевым слиянием, а не с N / 2-путевым, если она начинается с N последовательностей. Ведь число необходимых проходов приблизительно равно logN п, где п - число сортируемых элементов, а N - степень операции слияния - это и определяет значительное преимущество нового метода. [2]

Принцип многофазной сортировки. Здесь 31 сортируемая элементарная строка сортируется на 4 устройствах. Числа в таблице указывают количество строк на устройстве при данном просмотре. Индексы - указывают длины строк в группах элементарных строк. [3]

При многофазной сортировке одно устройство остается свободным, а на других в виде строк различной длины распределяется с помощью ряда внутренних сортировок весь набор данных. Длины строк, размещенных на отдельных устройствах, зависят от общего количества элементарных строк и могут быть-вычислены в виде так называемых чисел Фибоначчи. Процесс слияния строк на свободном устройстве продолжается до тех пор, пока не окажется, что. Затем слияние снова продолжается, причем в качестве выходного устройства используется только что освободившееся, а другие устройства - в качестве входных. И далее каждый раз, когда одно из устройств освобождается, оно начинает использоваться в качестве выходного. Процесс заканчивается, когда будут слиты все строки. [4]

Оценку производительности многофазной сортировки можно получить из табл. 2.15, где указано максимальное число начальных серий, которые можно отсортировать за заданное число частичных проходов ( уровней) с заданным числом ( N) последовательностей. [5]

Общий анализ многофазной сортировки, выполненный Кнутом ( Knuth) и другими исследователями в шестидесятых-семидесятых годах, - сложное и пространное исследование, выходящее за рамки данной книги. Коэффициент 1 / 0 используется в случае, когда на каждой фазе используется именно эта часть данных. Мы подсчитываем число эффективных проходов как количество считанных данных, деленных на общее количество данных. Некоторые результаты общего анализа вызывают удивление. [6]

При четырех блоках классический алгоритм многофазной сортировки изменяется. [7]

Многофазное слияние. [8]

На рис. 5.5.3 показан пример многофазной сортировки при использовании четырех устройств. Мы рассмотрим эту сортировку применительно к ленточным устройствам, для которых она получила наибольшее распространение. Здесь представлен этап сортировки, выполняемой после получения утилитой ЯУЗ и описания сортировки. Предполагается, что принято решение об использовании многофазной сортировки. Внутренняя сортировка включает распределение. Пусть число поставляемых записей и размеры буферных областей позволяют получить ровно 31 подфайл упорядоченных записей. Число получаемых каждым устройством подфайлов и их порядок определяются алгоритмически. [9]

Какие изменения следует произвести в алгоритме внешней многофазной сортировки, чтобы он мог обойтись тремя файлами вместо четырех. Как такие изменения повлияют на число сравнений и операций чтения блоков. Указание: В новом варианте нельзя переключаться от одной пары файлов к другой и обратно. [10]

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

Детальное рассмотрение составных слияний выходит за рамки данной книги, поэтому мы лишь кратко-остановимся на многофазной сортировке. [12]

Если для промежуточного хранения выделено только три ленты, то программа автоматически выбирает более эффективный в данном случае метод многофазной сортировки. [13]

Чтение данных большими блоками происходит значительно быстрее, чем поэлементное чтение. Поэтому эффективнее всего многофазная сортировка слиянием работает при чтении записей большими блоками. Но в любом случае число операций чтения значительно влияет на эффективность. [14]

Идеальное распределение серий по пяти последо-вэкмыюстям. [15]

Страницы: 1 2