Cтраница 2
Сравнивая трехпутевую поразрядную быструю сортировку со стандартной поразрядной сортировкой MSD мы можем отметить, что она разбивает файл всего лишь на три части, так что она не использует всех преимуществ быстрого многопутевого разбиения, особенно на ранних стадиях сортировки. С другой стороны, на поздних стадиях поразрядной сортировки MSD появляется множество пустых корзин, но в то же время поразрядная быстрая сортировка хорошо приспособлена для случаев дублированных ключей, ключей, принимающих значения в узких диапазонах, файлов небольших размеров и многих других случаев, в условиях которых поразрядная сортировка MSD выполняется медленно. Особо важное значение приобретает то обстоятельство, что подобного рода разбиение хорошо подходит для случаев проявления различного рода закономерностей в разных частях ключа. Более того, для нее не нужны никакие вспомогательные файлы. В противовес всем этим достоинствам можно поставить тот факт, что требуются дополнительные операции обмена, чтобы реализовать многопутевое разбиение с помощью трехпутевого разбиения, когда число подфайлов велико. [16]
Быструю сортировку более корректно было бы назвать алгоритмом типа разделяй и властвуй: в рекурсивных реализациях после активизации программы большая часть работы выполняется перед рекурсивными вызовами. С другой стороны, рекурсивная сортировка слиянием еще больше выдержана в духе принципа разделяй и властвуй: прежде всего, файл делится на две части, затем обработке ( воздействию власти) по отдельности подвергаются обе части. Сначала сортировке слиянием подвергаются файлы небольших размеров, в заключение обработке подвергается самый большой подфайл. Быстрая сортировка начинается с обработки наибольшего подфайла и завершается обработкой подфайлов небольших размеров. Интересна провести сравнение этих алгоритмов в контексте аналогии с управлением коллективом сотрудников, приводимой в начале настоящей главы: быстрая сортировка соответствует тому, что каждый руководящий работник затрачивает свои усилия на то, чтобы правильно разбить задачу на подзадачи, так что работа будет успешно выполнена, если успешно выполнены все подзадачи, в то время как сортировка слиянием соответствует тому, что каждый руководящий работник выполняет быструю произвольную разбивку задачу напополам, а затем затрачивает все свои усилия на то, чтобы преодолеть последствия подобных действий после того, как соответствующие подзадачи будут решены. [17]
Доказательство наличия этого свойства практически тривиально, в то же время оно играет весьма важную роль в нашем понимании поразрядной сортировки MSD. В частности, оно говорит нам, что мы не можем утверждать, что время выполнения сортировки будет меньше в силу того, что N мало, поскольку R может быть намного больше, чем N. Короче говоря, для сортировки файлов небольших размеров следует использовать другие методы. Этот вывод может служить решением проблемы пустых корзин, которую мы обсуждали в конце раздела 10.3. Например, если R равно 256, а N равно 2, то поразрядная сортировка MSD будет в 128 раз медленнее, чем более простой метод, предусматривающий только сравнение элементов. Рекурсивная структура поразрядной сортировки MSD приводит к тому, что соответствующая рекурсивная программа будет многократно вызывать себя для большого числа файлов небольших размеров. Поэтому в условиях рассматриваемого примера игнорирование проблемы пустых корзин может привести к тому, что вся поразрядная сортировка замедлится в 128 раз по сравнению с тем, какой она может быть. Что касается промежуточных ситуаций ( например, предположим, что R равно 256, а N равно 64), то стоимость не будет настолько катастрофичной, тем не менее весьма существенной. Использование сортировки вставками - не слишком удачный выбор, ибо стоимость N2 / 4 сравнений все еще недопустимо высока; не следует игнорировать проблему пустых корзин в силу того факта, что их очень много. Простейший путь решения этой проблемы состоит в использовании основания системы счисления, которая меньше размера сортируемого файла. [18]
Когда используется явно заданный стек, что, собственно говоря, и делалось в программе 7.3, удается избегать некоторых непроизводительных затрат, характерных для рекурсивных реализаций, хотя современные системы программирования не привносят больших непроизводительных затрат в столь простые программы. Далее рассматривается важное усовершенствование быстрой сортировки, которое обеспечивает повышение ее эффективности за счет распространения этой идеи на все файлы небольших размеров. [19]
Доказательство наличия этого свойства практически тривиально, в то же время оно играет весьма важную роль в нашем понимании поразрядной сортировки MSD. В частности, оно говорит нам, что мы не можем утверждать, что время выполнения сортировки будет меньше в силу того, что N мало, поскольку R может быть намного больше, чем N. Короче говоря, для сортировки файлов небольших размеров следует использовать другие методы. Этот вывод может служить решением проблемы пустых корзин, которую мы обсуждали в конце раздела 10.3. Например, если R равно 256, а N равно 2, то поразрядная сортировка MSD будет в 128 раз медленнее, чем более простой метод, предусматривающий только сравнение элементов. Рекурсивная структура поразрядной сортировки MSD приводит к тому, что соответствующая рекурсивная программа будет многократно вызывать себя для большого числа файлов небольших размеров. Поэтому в условиях рассматриваемого примера игнорирование проблемы пустых корзин может привести к тому, что вся поразрядная сортировка замедлится в 128 раз по сравнению с тем, какой она может быть. Что касается промежуточных ситуаций ( например, предположим, что R равно 256, а N равно 64), то стоимость не будет настолько катастрофичной, тем не менее весьма существенной. Использование сортировки вставками - не слишком удачный выбор, ибо стоимость N2 / 4 сравнений все еще недопустимо высока; не следует игнорировать проблему пустых корзин в силу того факта, что их очень много. Простейший путь решения этой проблемы состоит в использовании основания системы счисления, которая меньше размера сортируемого файла. [20]
Многие из возможных приложений сортировки часто отдают предпочтение простейшим алгоритмам. Во-первых, очень часто программа сортировки используется всего лишь один или небольшое число раз. После того как удалось решить проблему сортировки для некоторого набора данных, в дальнейшем потребность в программе сортировки в приложениях, которые манипулируют этими данными, отпадает. Если элементарная сортировка работает не медленней других частей приложения, осуществляющего обработку данных - например, считывание данных или их вывод на печать - то отпадает необходимость в поиске более быстрых методов сортировки. Если число сортируемых элементов не очень большое ( скажем, не превышает нескольких сотен элементов), можно просто воспользоваться простым методом и не ломать голову над тем, как работает интерфейс для системной сортировки, или как написать и отладить программу, реализующую какой-нибудь сложный метод сортировки. Во-вторых, элементарные методы всегда годятся для файлов небольших размеров ( состоящих из нескольких десятков элементов) - сложные алгоритмы в общем случае обусловливают непроизводительные затраты ресурсов, а это приводит к тому, что на файлах небольших размеров они работают медленнее элементарных методов сортировки. Эта проблема не попадет в фокус нашего внимания до тех пор, пока не возникнет необходимость сортировки большого числа файлов небольших размеров, однако следует иметь в виду, что приложения с подобного рода требованиями встречаются достаточно часто. Другими типами файлов, сортировка которых существенно упрощена, являются файлы, с почти ( или уже) завершенной сортировкой или файлы, которые содержат большое число дублированных ключей. Далее можно будет убедиться в том, что некоторые методы из числа простейших особенно эффективны при сортировке хорошо структурированных файлов. [21]
Многие из возможных приложений сортировки часто отдают предпочтение простейшим алгоритмам. Во-первых, очень часто программа сортировки используется всего лишь один или небольшое число раз. После того как удалось решить проблему сортировки для некоторого набора данных, в дальнейшем потребность в программе сортировки в приложениях, которые манипулируют этими данными, отпадает. Если элементарная сортировка работает не медленней других частей приложения, осуществляющего обработку данных - например, считывание данных или их вывод на печать - то отпадает необходимость в поиске более быстрых методов сортировки. Если число сортируемых элементов не очень большое ( скажем, не превышает нескольких сотен элементов), можно просто воспользоваться простым методом и не ломать голову над тем, как работает интерфейс для системной сортировки, или как написать и отладить программу, реализующую какой-нибудь сложный метод сортировки. Во-вторых, элементарные методы всегда годятся для файлов небольших размеров ( состоящих из нескольких десятков элементов) - сложные алгоритмы в общем случае обусловливают непроизводительные затраты ресурсов, а это приводит к тому, что на файлах небольших размеров они работают медленнее элементарных методов сортировки. Эта проблема не попадет в фокус нашего внимания до тех пор, пока не возникнет необходимость сортировки большого числа файлов небольших размеров, однако следует иметь в виду, что приложения с подобного рода требованиями встречаются достаточно часто. Другими типами файлов, сортировка которых существенно упрощена, являются файлы, с почти ( или уже) завершенной сортировкой или файлы, которые содержат большое число дублированных ключей. Далее можно будет убедиться в том, что некоторые методы из числа простейших особенно эффективны при сортировке хорошо структурированных файлов. [22]
Многие из возможных приложений сортировки часто отдают предпочтение простейшим алгоритмам. Во-первых, очень часто программа сортировки используется всего лишь один или небольшое число раз. После того как удалось решить проблему сортировки для некоторого набора данных, в дальнейшем потребность в программе сортировки в приложениях, которые манипулируют этими данными, отпадает. Если элементарная сортировка работает не медленней других частей приложения, осуществляющего обработку данных - например, считывание данных или их вывод на печать - то отпадает необходимость в поиске более быстрых методов сортировки. Если число сортируемых элементов не очень большое ( скажем, не превышает нескольких сотен элементов), можно просто воспользоваться простым методом и не ломать голову над тем, как работает интерфейс для системной сортировки, или как написать и отладить программу, реализующую какой-нибудь сложный метод сортировки. Во-вторых, элементарные методы всегда годятся для файлов небольших размеров ( состоящих из нескольких десятков элементов) - сложные алгоритмы в общем случае обусловливают непроизводительные затраты ресурсов, а это приводит к тому, что на файлах небольших размеров они работают медленнее элементарных методов сортировки. Эта проблема не попадет в фокус нашего внимания до тех пор, пока не возникнет необходимость сортировки большого числа файлов небольших размеров, однако следует иметь в виду, что приложения с подобного рода требованиями встречаются достаточно часто. Другими типами файлов, сортировка которых существенно упрощена, являются файлы, с почти ( или уже) завершенной сортировкой или файлы, которые содержат большое число дублированных ключей. Далее можно будет убедиться в том, что некоторые методы из числа простейших особенно эффективны при сортировке хорошо структурированных файлов. [23]