Дополнительное пространство - память
Cтраница 2
Одним из наиболее привлекательных свойств сортировки слиянием является тот факт, что она сортирует файл, состоящий из N элементов, за время, пропорциональное WlogW, независимо от характера входных данных. Основной недостаток сортировки слиянием заключается в том, что прямолинейные реализации этого алгоритма требуют дополнительного пространства памяти, пропорционального N. Это препятствие можно обойти, однако сделать это довольно сложно, причем потребуются дополнительные затраты, которые в общем случае не оправдываются на практике, особенно если учесть, что существует альтернатива в виде пирамидальной сортировки. Получить программную реализацию сортировки слиянием не труднее, чем реализацию пирамидальной сортировки, при этом длина внутреннего цикла принимает среднее значение между аналогичными показателями быстрой сортировки и пирамидальной сортировки, следовательно, сортировка методом слияния достойна того, чтобы к ней проявить внимание в случае, когда на первый план выходят такие показатели как быстродействие, необходимость избегать наихудших случаев, возможность использования дополнительного пространства памяти. [16]
Подход ( грименнтельно к поразрядной сортировке получил широкое распространение в CRT у того, что он требует исключительно простых структур управления, а его базовые операции очень удойны для реализаций а машинном яшке, который легко шдагттирустся к высокопроизводительным аппаратным средствам специального назначения, В такой среде наибольшее быстродействие, но-пилим ому достигается при ис-мо. LSD, Если мы используем указатели, то чтобы попользоваться норгирклкой сортировкой LSD нам потребуется дополнительное пространство памяти для размещения / V евшей ( и Д счетчиков), и эти затраты позволяют ревизовать метод, который может сортировать файлы с произвольной ирга ни злцие и всего лишь за три-четыре прохода. [17]
 |
Эмпирические исследования алгоритмов сортировки слиянием. [18] |
По обыкновению мы должны выразить предостережение относительно того, что погоня за усовершенствованиями подобного рода, перед которой не в состоянии устоять многие программисты, могут в некоторых случаях приносить всего лишь незначительные выгоды и должны быть реализованы только после того, как будут сняты более важные вопросы. В таких случаях сортировка слиянием будет обладать явно выраженным превосходством перед быстрой сортировкой в том, что она устойчива и обеспечивает высокую скорость сортировки, равно как и недостатками, которые проявляются прежде всего в том, что она использует дополнительное пространство памяти, пропорциональное размерам массива. Если совокупность этих факторов складывается в пользу сортировки слиянием ( при этом большое значение имеет быстродействие), то предложенные усовершенствования заслуживают внимательного рассмотрения наряду с тщательным изучением программного кода, порожденного компиляторами, специальных свойств архитектуры машины и пр. [19]
Мы достаточно подробно рассматривали эти моменты в главе 5, однако привлекательность преждевременной оптимизации настоль сильна, что каждый раз, когда изучается возможность применения того или иного метода усовершенствования реализации на таком уровне детализации, целесообразно подумать об улучшении самих методов. Что касается оптимизации сортировки слиянием, то здесь можно чувствовать себя вполне спокойно, ибо программы 8.1 - 8.4 обладают всеми наиболее важными характеристиками производительности, которые исследовались выше: время их выполнения пропорционально TVlogTV, они нечувствительны к организации входных данных ( см. рис. 8.8), они используют дополнительное пространство памяти, они могут быть реализованы с сохранением свойства устойчивости. Сохранение этих свойств в процессе снижения времени выполнения в общем случае не является особо трудной задачей. [20]
Хотя реализация слияния, по-видимому, требует дополнительного пространства, мы все еще считаем абстракцию обменного слияния полезной при реализации методов сортировки, которые здесь изучаются. Можно было бы реализовать эту программу слияния, сначала скопировав абсолютно все во вспомогательный файл с последующим применением базового метода, использованного в программе 8.1, однако пока мы не будем делать этого, а сначала внесем одно усовершенствование в данный подход. И хотя дополнительное пространство памяти для вспомогательного массива, по-видимому, на практике связано с определенной ценой, в разделе 8.4 мы рассмотрим дальнейшие улучшения, которые позволят избежать дополнительных затрат времени, требуемого на копирование массива. [21]
Подход применительно к поразрядной сортировке получил широкое распространение в силу того, что он требует исключительно простых структур управления, а его базовые операции очень удобны для реализаций в машинном языке, который легко адаптируется к высокопроизводительным аппаратным средствам специального назначения. В такой среде наибольшее быстродействие, по-видимому, достигается при использовании полной поразрядной сортировки LSD. Если мы используем указатели, то чтобы воспользоваться поразрядной сортировкой LSD нам потребуется дополнительное пространство памяти для размещения N связей ( и R счетчиков), и эти затраты позволяют реализовать метод, который может сортировать файлы с произвольной организацией всего лишь за три-четыре прохода. [22]
Сортировка слиянием - это устойчивая сортировка, и данное обстоятельство склоняет чашу весов в ее пользу в тех приложениях, в которых устойчивость имеет важное значение. Конкурирующие методы, такие как быстрая сортировка или пирамидальная сортировка, не относятся к числу устойчивых. Различные приемы, придающие этим методам устойчивость, имеют стойкую тенденцию к использованию дополнительного пространства памяти; следовательно, требования дополнительной памяти, предъявляемые со стороны сортировки слиянием отодвигаются на задний план в тех случаях, когда устойчивость становится доминирующим фактором. [23]
Одним из наиболее привлекательных свойств сортировки слиянием является тот факт, что она сортирует файл, состоящий из N элементов, за время, пропорциональное WlogW, независимо от характера входных данных. Основной недостаток сортировки слиянием заключается в том, что прямолинейные реализации этого алгоритма требуют дополнительного пространства памяти, пропорционального N. Это препятствие можно обойти, однако сделать это довольно сложно, причем потребуются дополнительные затраты, которые в общем случае не оправдываются на практике, особенно если учесть, что существует альтернатива в виде пирамидальной сортировки. Получить программную реализацию сортировки слиянием не труднее, чем реализацию пирамидальной сортировки, при этом длина внутреннего цикла принимает среднее значение между аналогичными показателями быстрой сортировки и пирамидальной сортировки, следовательно, сортировка методом слияния достойна того, чтобы к ней проявить внимание в случае, когда на первый план выходят такие показатели как быстродействие, необходимость избегать наихудших случаев, возможность использования дополнительного пространства памяти. [24]
В условиях ограниченной памяти блоки-дублеры будут, как правило, изыматься из памяти при листании, а объектом листания могут быть концы очень больших основных блоков. Механизмы листания могут не дать схеме буферизации реализовать свое назначение. Если среднее время доступа к блоку на устройстве слияния ( диске) существенно больше, чем на устройстве листания ( например, барабане), то все равно, возможно, стоит использовать удвоенную буферизацию и разрешить листание. Повторный вызов блока с устройства листания может занимать меньше времени, чем ожидание считывания этого блока с медленного устройства. По отношению к блокам память с листанием действует как некоторое устройство, сбрасывающее ненужные элементы конструкции. Когда устройство листания и устройство слияния одинаковы, то использование буферизации с дублированием становится несколько подозрительным. Такая буферизация требует дополнительного пространства памяти и не гарантирует присутствия записи в памяти, когда она нужна центральному процессору. Однако, если буферизация с дублированием становится сомнительной, вся концепция равновесия между центральным процессором и вводом-выводом должна быть подвергнута кропотливому повторному анализу. Эта проблема сохранения совмещения ввода-вывода с работой центрального процессора встает особенно остро в системах с одноуровневой памятью, где весь ввод-вывод загнан в пространство виртуальной памяти и распределение данных очевидно для сортировки. [25]
АБД может включить, кроме данных для дополнительного упорядочения, другие поля из сегмента-источника в сегмент-указатель индекса. Это оказывается полезным в том случае, когда программа обрабатывает вторичный индекс как данные. Например, допустим, что вы, зная имя пациента, хотите определить идентификатор его койки. Тогда вам будет достаточно обеспечить доступ программы только ко вторич ному индексу. Однако он требует наличия поля ИДЕНТИФИКАТОР КОЙКИ как в базе данных БОЛЬНИЦА, так и во вторичном индексе. В подобных ситуациях приходится сопоставлять выигрыш во времени обработки с проигрышем из-за использования дополнительного пространства памяти. [26]
Страницы: 1 2