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

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

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

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

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