Cтраница 1
Внешняя сортировка составляет часть таких приложений, в которых в работу вовлекается гораздо больше элементов, чем можно сразу запомнить в оперативной памяти. [1]
Внешняя сортировка выполняется в несколько этапов, и внешняя память при этом неоднократно используется для размещения данных. [2]
Внешняя сортировка составляет часть таких приложений, как обработка расчетов, при которой в работу вовлекается гораздо больше элементов, чем можно сразу запомнить в оперативной памяти. Поэтому методы внешней сортировки, применимые к данным, находящимся на внешних устройствах памяти ( таких, как диски или магнитные ленты), имеют огромное коммерческое значение. [3]
Внешняя сортировка, при которой на первом этапе группы записей сортируются в оперативной памяти и записываются па несколько лент, а на втором этапе упорядоченные группы сливаются с нескольких лент на одну. [4]
Внешняя сортировка с помощью многофазного слияния осуществляется следующим образом. [5]
Внешняя сортировка, при которой на первом этапе группы записей сортируются в оперативной памяти и записываются на несколько лент; на втором этапе упорядоченные группы сливаются с нескольких лент на одну. [6]
Вид внешней сортировки, при которой производится группировка сортируемых записей, причем каждая группа хранится в виде отдельного блока ( В. Различные блоки будут, вероятно, находиться при этом в разных запоминающих устройствах. Тогда все записи, которые могут содержать требуемый ключ, будут извлекаться из внешней памяти за одно обращение. [7]
Метод внешней сортировки, позволяющий выполнить слияние п последовательных файлов, если имеется п 1 рабочий файл. Является разновидностью метода слияния. [8]
Разделение методов внешней сортировки отражает основные различия в построении и оценках методов. В основе классификационного деления методов ( см. рис. 4.2, 2 - й уровень) лежит способ разделения сортируемого массива на группы при обмене с внешней памятью. [9]
В процессе внешней сортировки часть файла считывается в основную память, там упорядочивается, а затем переписывается на внешние устройства. Этот процесс повторяется несколько раз. Внутренние методы используются для перестановки данных, обрабатываемых между их пересылками. Поэтому, когда говорят о сортировке на лентах, то подразумевают не только процесс считывания и записи на эти ленты, но также и внутреннюю сортировку, которая упорядочивает и комбинирует элементы с этих лент по мере их считывания. [10]
Большая часть методов внешней сортировки соблюдает следующие принципы общего характера. Выполняется первый проход по сортируемому файлу, в процессе которого производится его разбиение на блоки, размер которых примерно соответствует пространству оперативной памяти, после чего выполняется сортировка этих блоков. Затем осуществляется слияние отсортированных блоков, при необходимости с этой целью выполняются несколько проходов файла, при этом с каждым проходом степень упорядоченности возрастает, пока весь файл не окажется отсортированным. Такой подход называется сортировкой-слиянием ( sort-merge), он с успехом применяется на практике с тех пор, когда компьютеры получили широкое распространение в коммерческих приложениях в пятидесятых годах прошлого столетия. [11]
Классификационная схема методов внешней сортировки ( рис. 4.2) учитывает эту особенность. [12]
Наиболее общей формой внешней сортировки является сортировка-слияние. [13]
Раздел 7.2 посвящен внешней сортировке, представляющей собой задачу полной сортировки для случая такой большой таблицы, что доступ к ней организован по частям, расположенным на внешних запоминающих устройствах. Наконец, задачи частичной сортировки - задачи выбора j - ro наибольшего имени и слияния двух упорядоченных таблиц - обсуждаются в разд. [14]
Разработать подход к внешней сортировке, который основан на разделении, подобном используемому в быстрой сортировке или в поразрядной сортировке MSD ( сначала по старшей цифре), проанализировать его и сравнить с многопутевой сортировкой. Вы можете перейти на более высокий уровень абстракции, использованный при описании сортировки-слияния в этом разделе, однако вы должны стремиться к тому, чтобы быть способными спрогнозировать время выполнения для заданного числа устройств и заданного объема оперативной памяти. [15]