Специальные методы сортировки a

Рис. 11.17. Сравнение затрат на сбалансированное и полифазное слияние
Количество проходов, выполняемых сбалансированным слиянием с 4 устройствами (вверху), всегда больше, чем количество эффективных проходов, выполняемых полифазным слиянием с 3 лентами (внизу). Представленные графики получены для функций из свойств 11.4 и 11.6, для N/M от 1 до 100. Из-за наличия фиктивных отрезков истинная производительность полифазного слияния имеет более сложный характер, чем показано данной ступенчатой функцией.
Доведя эту точку зрения до крайности, заметим, что многие современные вычислительные системы предоставляют программисту виртуальную память - более абстрактную модель доступа к внешним устройствам, чем использованная нами. В виртуальной памяти можно разместить огромное количество записей, оставив системе вопросы пересылки адресуемых данных с внешних запоминающих устройств в оперативную память; при этом доступ к данным так же удобен, как и прямой доступ к оперативной памяти. Однако эта иллюзия несовершенна: если программа обращается к участкам памяти, расположенным рядом с участками, к которым она недавно обращалась, то потребность в передаче данных с внешних устройств в оперативную память возникает нечасто, и производительность виртуальной памяти вполне удовлетворительна. (Например, в эту категорию попадают программы, осуществляющие последовательный доступ к данным.) Но если данные, к которым производится доступ, разбросаны в разных местах, то система виртуальной памяти начнет " дергаться " (thrash), т.е. тратить все время на доступ к внешним данным - с катастрофическими результатами.
Не следует игнорировать виртуальную память как возможную альтернативу для сортировки очень больших файлов. В этом случае можно непосредственно реализовать сортировку-слияние, или, еще проще, воспользоваться методом внутренней сортировки, наподобие быстрой сортировки или сортировки слиянием. Эти методы внутренней сортировки заслуживают пристального внимания в среде с хорошо реализованной виртуальной памятью. Однако такие методы, как пирамидальная сортировка или поразрядная сортировка, в которых ссылки разбросаны по памяти, скорее всего, не подойдут, т.к. система начнет дергаться.
С другой стороны, использование виртуальной памяти может привести к недопустимым затратам ресурсов, так что расчет на собственные явные методы (подобные рассмотренным выше) может оказаться наилучшим способом выжать все, на что способны высокопроизводительные внешние устройства. Одна из основных характеристик изученных выше методов заключается в том, что они разработаны так, чтобы максимально возможное количество независимых частей вычислительной системы работало с максимальной эффективностью, и ни одна из частей не простаивала. Если в качестве этих независимых частей рассматривать процессоры, мы приходим к идее параллельных вычислений - теме раздела 11.5.
Упражнения
11.45. Покажите, какие отрезки порождаются выборкой с замещением, использующей очередь с приоритетами размером 4, для ключей E A S Y Q O U E S T I O N.
11.46. Как отразится использование выборки с замещением для файла, порожденного с помощью выборки с замещением из заданного файла?
11.47. Определите эмпирически среднее число отрезков, порожденных выборкой с замещением, в которой используется очередь с приоритетами размером 1000, для случайно упорядоченных файлов размером N = 10³, 10⁴, 10⁵ и 10⁶ .
11.48. Каким будет количество отрезков в худшем случае при использовании выборки с замещением для генерации начальных отрезков из файла, содержащего N записей, с использованием очереди с приоритетами размером M, при M < N?
11.49. Покажите, в стиле рис. 11.15, как с помощью полифазного слияния выполняется сортировка ключей E A S Y Q U E S T I O N W I T H P L E N T Y O F K E Y S.
11.50. В примере полифазного слияния на рис. 11.15 два фиктивных отрезка были помещены на магнитную ленту с 7 отрезками. Найдите другие способы распределения фиктивных отрезков по лентам и выберите среди них такой, который обеспечивает минимальную стоимость слияния.
11.51. Составьте таблицу, соответствующую рис. 11.13, для определения максимального количества отрезков, которые могут быть слиты сбалансированным трехпутевым слиянием с пятью проходами по данным (используя шесть устройств).
11.52. Составьте таблицу, соответствующую рис. 11.16, для определения максимального количества отрезков, которые могут быть слиты полифазным слиянием с теми же затратами, что и пять проходов по всем данным (используя шесть устройств).
11.53. Напишите программу, вычисляющую количество проходов, выполняемых многопутевым слиянием, и эффективное количество проходов, выполняемых поли-фазным слиянием для заданного количества устройств и заданного количества начальных блоков. Используйте полученную программу для вывода таблицы этих затрат при работе каждого метода, для P = 3, 4, 5, 10 и 100 и N = 10³, 10⁴, 10⁵ и 10⁶ .
11.54. Напишите программу, последовательно назначающую начальные отрезки устройствам перед выполнением P-путевого полифазного слияния. Если количество отрезков есть обобщенное число Фибоначчи, отрезки должны быть распределены по устройствам так, как требует алгоритм; ваша задача заключается в отыскании удобного способа последовательного распределения отрезков.
11.55. Реализуйте выборку с замещением, воспользовавшись интерфейсом, определенным в упражнении 11.38.
11.56. Реализуйте сортировку-слияние, комбинируя решения упражнений 11.38 и 11.55. Используйте полученную программу для сортировки файла максимально возможного в вашей системе размера, воспользовавшись полифазным слиянием. При возможности определите, как отражается на времени выполнения программы увеличение числа устройств.
11.57. Как нужно обрабатывать небольшие файлы в реализации быстрой сортировки при упорядочении очень большого файла в среде с виртуальной памятью?
11.58. Если на вашем компьютере функционирует подходящая система виртуальной памяти, выполните эмпирическое сравнение быстрой сортировки, LSD-сортировки, MSD-сортировки и пирамидальной сортировки для очень больших файлов. Используйте размер файла, максимально возможный в вашей системе.
11.59. Разработайте реализацию рекурсивной многопутевой сортировки слиянием, основанной на k-путевом слиянии, которую можно использовать для сортировки очень больших файлов в среде с виртуальной памятью (см. упражнение 8.11).
11.60. Если на вашем компьютере функционирует подходящая система виртуальной памяти, эмпирически определите значение к, при котором достигается минимальное время выполнения реализации из упражнения 11.59. Используйте размер файла, максимально возможный в вашей системе.