Ускорение сортировки слиянием

Мы продемонстрировали пример процедуры сортировки слиянием, которая начи­нается с серий длины 1. Мы сэкономили бы немало времени, если бы начали эту процедуру с прохода, который считывает в основную память группы из k записей (при соответствующем k), сортирует их (например, с помощью процедуры быстрой сортировки) и записывает во внешнюю память в виде серии длиной k.

Если, например, у нас есть миллион записей, нам потребуется 20 проходов по этим данным, чтобы выполнить сортировку, начиная с серий длиной 1. Если, одна­ко, у нас есть возможность одновременно поместить в основную память 10 000 запи­сей, то мы сможем за один проход прочитать 100 групп из 10 000 записей, отсорти­ровать каждую группу и получить таким образом 100 серий длиной 10 000, поделен­ных поровну между двумя файлами. Таким образом, всего семь проходов и слияний потребовалось бы для сортировки файла, содержащего не более 10 000 х 2⁷ = 1 280 000 записей.

Минимизация полного времени выполнения

В современных компьютерных системах с разделением времени пользователю обычно не приходится платить за время, в течение которого его программа ожидает считывания блоков данных из файла (операция, характерная для процесса сортиров­ки слиянием). Между тем, полное время выполнения сортировки превышает (зачастую значительно) время обработки данных, находящихся в основной памяти. Если же нам приходится сортировать действительно большие файлы, время обработ­ки которых измеряется часами, полное время становится критической величиной, даже если мы не платим за него из собственного кармана, и проблема минимизации полного времени процесса сортировки слиянием выходит на первый план.

Как уже указывалось, время, необходимое для считывания данных с магнитного диска или магнитной ленты, как правило, существенно превышает время, затрачи­ваемое на выполнение простых вычислений с этими данными (например, слияния списков). Таким образом, можно предположить, что при наличии лишь одного кана­ла, по которому происходит обмен данными с основной памятью, именно этот канал и станет тем "узким местом", которое будет тормозить работу системы в целом. Этот канал обмена данными все время будет занят, и полное время работы системы будет практически равно времени, затрачиваемому на обмен данными с основной памятью, т.е. все вычисления будут выполняться практически мгновенно после того, как поя­вятся соответствующие данные, и одновременно с тем, пока будет считываться или записываться следующая порция данных.

Даже в условиях такой относительно простой вычислительной среды следует по­заботиться о минимизации затрат времени. Чтобы увидеть, что может произойти, ес­ли пренебречь этим требованием о минимизации временных затрат, допустим, что мы выполняем попеременное поблочное считывание двух входных файлов f₁ и f₂. Файлы организованы в виде серий определенной длины, намного превышающей раз­мер блока, поэтому, чтобы объединить две такие серии, нам нужно прочитать не­сколько блоков из каждого файла. Предположим, однако, что все записи в серии из файла f_l предшествуют всем записям из файла f₂. В этом случае при попеременном считывании блоков все блоки из файла f₂ должны оставаться в основной памяти. Ос­новной памяти может не хватить для всех этих блоков, но даже если и хватит, нам придется (после считывания всех блоков серии) подождать, пока не будет скопирова­на и записана вся серия из файла f₂.

Чтобы избежать подобных проблем, мы рассматриваем ключи последних записей в последних блоках, считанных из f₁ и f₂ например ключи k₁ и k₂ соответственно. Если какая-либо из серий исчерпалась, мы, естественно, считываем следующую се­рию из другого файла. Если серия не исчерпалась, мы считываем блок из файла f₁ , если, конечно, k₁ < k₂ (в противном случае считываем блок из f₂). To есть, мы опре­деляем, у какой из двух серий будут первой выбраны все ее записи, находящиеся в данный момент в основной памяти, и в первую очередь пополняем запас записей именно для этой серии. Если выбор записей происходит быстрее, чем считывание, мы знаем, что когда будет считан последний блок этих двух серий, для последующе­го слияния не может остаться больше двух полных блоков записей; возможно, эти записи будут распределены по трем (максимум!) блокам.