Многоканальное слияние

Если "узким местом" является обмен данными между основной и вторичной па­мятью, возможно, удалось бы сэкономить время за счет увеличения числа каналов обмена данными. Допустим, что в нашей системе имеется 2т дисководов, каждый из которых имеет собственный канал доступа к основной памяти. Мы могли бы размес­тить на т дисководах т файлов (f₁, f₂, … f_m), организованных в виде серий длины k. Тогда можно прочитать т серий, по одной из каждого файла, и объединить их в одну серию длиной mk. Эта серия помещается в один из т выходных файлов (g_1t g₂,..., g_m), каждый из которых получает по очереди ту или иную серию.

Процесс слияния в основной памяти можно выполнить за O(log т) шагов на одну запись, если мы организуем т записей-кандидатов, т.е. наименьших на данный мо­мент невыбранных записей из каждого файла, в виде частично упорядоченного дере­ва или другой структуры данных, которая поддерживает операторы INSERT и DELETEMIN, выполняемые над очередями с приоритетами за время порядка O(logn). Чтобы выбрать из очереди с приоритетами запись с наименьшим ключом, надо выполнить оператор DELETEMIN, а затем вставить (оператор INSERT) в очередь с приоритетами следующую запись из файла-победителя в качестве замены вы­бранной записи.

Если у нас имеется п записей, а длина серий после каждого прохода умно­жается на т, тогда после i проходов серии будут иметь длину тⁱ. Если тⁱ > п, т.е. после t = log_m nпроходов, весь список будет отсортирован. Так как log_m n = log₂ n / log₂m, то "коэффициент экономии" (по количеству считываний каж­дой записи) составляет log₂m. Более того, если т — количество дисководов, исполь­зуемых для входных файлов, и т дисководов используются для вывода, мы можем обрабатывать данные в т раз быстрее, чем при наличии лишь одного дисковода для ввода и одного дисковода для вывода, и в 2т раз быстрее, чем при наличии лишь одного дисковода для ввода и вывода (входные и выходные файлы хранятся на од­ном диске). К сожалению, бесконечное увеличение т не приводит к ускорению обра­ботки по “ закону коэффициента log m “. Причина заключается в том, что при доста­точно больших значениях m время, необходимое для слияния в основной памяти (которое растет фактически пропорционально log m), превосходит время, требующееся для считывания или записи данных. Начиная с этого момента дальнейшее увели­чение т ведет, по сути, к увеличению полного времени обработки данных, поскольку "узким местом" системы становятся вычисления в основной памяти.