Алгоритм сортировки строк

Привет, хабровчане!

Я здесь совсем новенький, только вчера зарегистрировался (хотя в Инете я уже 27 лет), и планировал потусоваться тут с месячишко, осмотреться… но тут, оказывается, очень жёсткие правила, в частности: для того, чтобы комментировать старые статьи нужно расширить полномочия аккаунта до полноправного участника, т.е. написать интересную статью в Песочницу.

Ну, что же: думаю, эта тема ДОЛЖНА БЫ вызвать интерес (на эту тему и здесь написано немало статей), хотя она касается именно МОЕГО недавнего алгоритма (этого года выпуска), а это у вас, кажется, называется «я пиарюсь». Ну да, я пиарюсь — в частности, для того, чтобы получить здесь полноценный аккаунт.


Итак, тема этой заметки — сортировка. Не теоретические изыскания, а именно практическая реализация. Сортировка строк, чисел, структур, «а также всего, что понадобится впредь».

Сортировка внутренняя и внешняя, «в одном флаконе», автоматически переходящая одна в другую в зависимости от наличия доступного ОЗУ. Предлагаемый алгоритм (он называется «сортировка воронкой») получился невероятно удачным (я не хотел, так получилось, я нечаянно), а область применения настолько высока, что у меня лично не хватает фантазии придумать что-либо более востребованное: везде, где вообще есть данные, нужна сортировка. По слухам, самая первая программа, написанная для ЭВМ, была именно программой сортировки.

Сортировка воронкой является существенно улучшенным вариантом алгоритма сортировки слиянием. Принципиальное отличие состоит в том, что отсортированные массивы данных для слияния формируются динамически, а их размер определяется самой последовательностью входных данных. В частности, если массив уже отсортирован (в прямом или обратном порядке — это почти безразлично), сразу после окончания загрузки данных в ОЗУ они уже будут организованы в виде полностью отсортированного единого списка, который остаётся лишь отправить в выходной поток.

Алгоритм можно условно разделить на несколько шагов:

Шаг 1. Чтение исходных данных.

Воронка представляет собой набор из k упорядоченных списков (первоначально пустых). Чтобы минимизировать количество сравнений, текущий входной элемент, вне зависимости от числа элементов в списке, сравнивается лишь с головой и хвостом соответствующего списка: если он меньше или равен первому элементу — становится его головой, если больше или равен последнему — дописывается в хвост. Если ни то, ни другое — переходит к сравнению с головой и хвостом следующего списка (если такой имеется) либо сам образует очередной список, являясь в нём одновременно головой и хвостом. Таким образом, элементы этих списков образуют «воронку»: голова каждого следующего списка гарантированно больше головы предыдущего, а его хвост, соответственно, меньше. А потому при движении по «воронке» вероятность того, что очередной элемент будет куда-нибудь пристроен без увеличения размера воронки, довольно высока.

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

Шаг 2. Слияние списков.

Необходимость слияния списков возникает, если:

  • элемент не удаётся пристроить в воронку (все k списков воронки заполнены);
  • входной поток исчерпан (все данные загружены в ОЗУ);
  • исчерпано доступное ОЗУ (некуда размещать очередной элемент).

Алгоритм слияния упорядоченных массивов хорошо известен: на каждом шаге берётся меньший из текущих элементов подмассивов и отправляется в результирующий массив. Счётчики номеров элементов результирующего массива и подмассива, из которого был взят элемент, увеличиваются на единицу. Когда один из подмассивов закончился, оставшиеся элементы второго подмассива добавляются в результирующий массив. Поскольку массивы в ОЗУ представлены в виде списков, слияние двух подмассивов происходит без перемещения самих элементов данных, что гораздо быстрее.

Механизм слияния списков при переполнении воронки может быть реализован, например, так: два наименьших (по объёму или по числу элементов) списка сливаются в один — в тот, который занимает место старшего по воронке объединяемого списка (в этом случае воронка остаётся воронкой, то есть голова и хвост любого списка гарантированно лежат внутри диапазона любого из старших списков и вне диапазона любого из младших), все списки меньше младшего из сливаемых сдвигаются на единицу, а последний список воронки обнуляется.

В случае исчерпания входного потока данных или доступного ОЗУ все списки вначале попарно сливаются в один, начиная с самых мелких, а затем этот список отправляется в выходной поток. Процесс сортировки завершён.

Шаг 3. Слияние файлов.

Этот шаг выполняется лишь при нехватке ОЗУ для размещения всего сортируемого массива данных. Слияние временных файлов производится в новый файл с последующим удалением двух сливаемых, до полного исчерпания временных файлов. Алгоритм слияния тот же, как и при слиянии списков.

Оценка сложности алгоритма

Алгоритм сортировки воронкой относится к классу алгоритмов, основанных на сравнении элементов. Они отличаются гибкостью применения, но имеют фундаментальное ограничение производительности для худшего случая: она не может быть лучше, чем O(n*log2n). Худший случай для данного алгоритма прекрасно известен: если входной поток также отсортирован «воронкой» и не имеет одинаковых элементов, т.е. а) минимальный элемент б) максимальный в) минимальный из оставшихся г) максимальный из оставшихся (например при сортировке чисел: 1, 99, 2, 98, 3, 97, ...) и т.д. В этом случае в массив воронки поместится только два элемента, и алгоритм фактически сводится к классическому алгоритму сортировки слиянием, у которого первый шаг совмещён с процессом чтения элементов в ОЗУ. Как известно, этот алгоритм имеет именно такую сложность O(n*log2n) — как для худшего случая, так и для лучшего. Практика, однако, показывает, что в реальном мире сортируемые массивы данных часто содержат в себе упорядоченные подмассивы, а любая восходящая или нисходящая подпоследовательность будет гарантированно «поймана» воронкой размером даже в один список! А потому сортировка воронкой для лучшего случая (когда входные данные уже отсортированы) будет выполнена за линейное время O(n).

Среднюю сложность при случайном распределении входных данных можно оценить лишь вероятностно. Очевидно, что чем больше в исходных данных монотонно возрастающих или убывающих подпоследовательностей, чем больше там повторяющихся элементов, тем «линейнее» будет время сортировки — особенно, если учитывать время загрузки исходных данных и записи результатов. Тем более, что при чтении и записи данных доступ к ним последовательный, то есть максимально быстрый. Эксперименты показали, что время сортировки соизмеримо со временем копирования файлов или любой другой линейной обработки данных. Тестирование на специально подготовленных массивах для лучшего и худшего случая объёмом от миллиона до ста миллионов строк показало: несмотря на то, что количество сравнений элементов отличается на порядки, общее время сортировки замедляется лишь на десятки процентов (во всех экспериментах менее, чем в два раза). Для сравнения: нехватка ОЗУ из-за резкого увеличения числа файловых операций замедляет время сортировки в десятки раз. Таким образом, если теоретическая сложность для худшего случая всё-таки логарифм, реальная сложность работы программы — линейная: время работы худшего случая лишь вдвое превышает время для лучшего, заведомо линейное.

Достоинства и недостатки

Достоинства:

  • один из самых быстродействующих (на практике) из алгоритмов внутренней и внешней сортировки общего назначения;
  • универсален. Сортирует практически любые типы данных — в частности, массивы с элементами постоянной или переменной длины;
  • поточная обработка входных данных: если для других алгоритмов требуется предварительно закачать весь массив данных в ОЗУ, после чего начинается собственно сортировка, то у «воронки» она к этому времени практически закончена;
  • естественность поведения: при обработке уже упорядоченных или частично упорядоченных данных время сортировки заметно уменьшается;
  • работает в условиях ограниченных ресурсов (нехватка ОЗУ);
  • работает на структурах данных последовательного доступа;
  • не имеет «трудных» входных данных;
  • прост в реализации;
  • требует лишь O(n) дополнительной памяти для своей работы.

Недостатки:

  • неустойчив.

Вообще говоря, устойчивость алгоритма не является проблемой, если все ключи разные (это зависит от входных данных) или когда одинаковые элементы неразличимы — например, когда весь элемент является ключом (именно так и устроен алгоритм сравнения элементов в данной реализации). В крайнем случае, алгоритм может быть легко доработан для обеспечения устойчивой сортировки путём расширения ключа исходным индексом элемента в массиве. В случае равенства основных ключей сравнение производится по индексу, исключая, таким образом, возможность изменения взаимного положения равных элементов. Эта модификация требует дополнительной памяти в размер индекса на каждый элемент, который инициализируется значением в момент чтения массива в ОЗУ.

Реализация

Самое очевидное улучшение алгоритма — разделить процессы заполнения списков воронки и их слияния, а также определиться с оптимальным размером самой воронки: при увеличении максимального количества списков в ней растёт (хотя и незначительно) время на поиск места для размещения очередного элемента, а при его уменьшении начинает тормозить процесс слияния списков — ведь в них может находиться от двух элементов до многих тысяч и даже миллионов! Эксперименты показали, что размер воронки почти никак не влияет на эффективность (тестировались воронки в 1, 2, 4, 8,… 64 списка): увеличение времени на пристройку элемента почти компенсируется уменьшением числа слияний более крупных списков. Поэтому был реализован самый простой вариант с размером воронки в один список, требующий не более двух сравнений для пристройки элемента. А вот размер буфера отсортированных списков до слияния, напротив, был выбран достаточно большим (1024 списка), при переполнении которого сливаются сразу три четверти самых маленьких списков этого буфера (до 256). Такая технология позволяет эффективно сортировать неудачные (близкие к худшему случаю) наборы исходных данных, объединяя крупные массивы лишь перед записью результатов в файл.

Оптимизация процесса слияния временных файлов мало актуальна и заметна лишь при серьёзной нехватке ОЗУ, когда количество нарезок на файлы и последующих слияний достигает сотен и даже тысяч — например, при сортировке гигабайтных файлов утилитой, скомпилированной для MS-DOS с объёмом доступного ОЗУ в 300-400 килобайт. Но даже в этом случае сортировка происходит достаточно уверенно и не очень долго. Максимальное количество файлов определено в 36 (цифры и буквы латинского алфавита) со схлопыванием при переполнении сразу до 16.

Развитие

Алгоритм сортировки воронкой (как, впрочем, и другие алгоритмы, основанные на сравнениях) обладает неплохим потенциалом для повышения функциональности. В текущей реализации сортировка проводится по возрастанию значения байта данных в строке — наиболее универсальный механизм сравнения, позволяющий сортировать тексты на разных языках и структуры данных, содержащие нетекстовые символы. Но, в идеале, метод сравнения элементов должен быть настраиваемым пользователем (или вообще пользовательским). В частности, можно обеспечить возможность сортировки по возрастанию или убыванию, по алфавиту русского (в кодировках WIN-DOS-KOI-UTF et cetera), арабского, китайского и других языков, с игнорированием регистра символов или без него, сортировки данных разных типов (целочисленных, вещественных, даты, время), сортировки по полям таблиц и других структур, возможность переопределения значения терминатора (по умолчанию — символ перевода строки 0x0A) или длины массива (при сортировке структур данных постоянной длины) и т.д. В любом случае, настраивается лишь процедура сравнения элементов — весь остальной алгоритм сортировки «воронкой» остаётся неизменным.

Всё, я закончил — можете пинать ногами. Но предупреждаю заранее: я кусаюсь. И вообще собака по гороскопу.
Теги:
программирование, сортировка

Данная статья не подлежит комментированию, поскольку её автор ещё не является полноправным участником сообщества. Вы сможете связаться с автором только после того, как он получит приглашение от кого-либо из участников сообщества. До этого момента его username будет скрыт псевдонимом.