Оптимизация сортировки в Perl

АЛЕКСЕЙ МИЧУРИН

Оптимизация сортировки в Perl

В пилотном номере журнала «Системный администратор» была опубликована статья Даниила Алиевского – «Эффективное использование памяти в Perl при работе с большими строками». Тогда-то у меня и возникла мысль написать статью об эффективном использовании времени в Perl, то есть об оптимизации, направленной на увеличение быстродействия.

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

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

Давайте сперва изучим особенности алгоритма сортировки, вернее особенности её реализации в Perl 5.6. Я не буду здесь рассматривать саму реализацию. Она достаточно сложна и вместе с тем отлично прокомментирована в исходных кодах Perl. Если вас интересует этот вопрос, просто почитайте исходные коды. Итак, приступим.

Оценка производительности сортировки в Perl

В качестве критерия производительности я выбрал величину, равную отношению: в числителе – количество сравнений, необходимое для выполнения сортировки, в знаменателе – количество элементов в сортируемом списке. То есть величину, показывающую, сколько сравнений приходится в среднем на один элемент списка. Естественно, эта величина зависит и от размера массива, и от меры его начальной упорядоченности.

Рисунок 1. Результаты тестов производительности встроенной процедуры сортировки языка Perl для изначально упорядоченных массивов (упор.),

обратноупорядоченных массивов (обр.) и не упорядоченных массивов (случ.) различной длины[2].

На приведённой диаграмме показаны результаты тестов, проведённых на разных массивах. Тестировались три рода массивов: упорядоченный (в результате сортировки массив не менялся), обратноупорядоченный (в результате сортировки массив перестраивался в обратном порядке) и массив случайных величин (для этого случая на диаграмме показаны средние значения).

Как видите, наименее ресурсоёмкой оказалась сортировка уже отсортированного массива, чего, наверное, и следовало ожидать. Менее тривиальный результат состоит в том, что для сортировки обратноупорядоченного массива требуется не намного больше актов сравнения, чем для упорядоченного. И самой ресурсоёмкой оказывается сортировка «случайного» (неупорядоченного) списка.

Такие результаты тестов не случайны, но мы договорились, что не будем затрагивать тонкости реализации, оставив их для разработчиков языков. Просто сортировка такова и результаты тестов таковы.

Самым важным и интересным для нас в этих тестах является то, что количество необходимых для сортировки актов сравнения возрастает непропорционально количеству элементов в списке. То есть для сортировки случайной последовательности из 10 элементов необходимо (в среднем) 23 сравнения, а для сортировки подобного списка из 10 000 элементов необходимо не 23 000 сравнений, а в шесть(!) раз больше – 136 000. Обратите внимание, эта закономерность выполняется для любых списков, независимо от их начальной упорядоченности.

Здесь-то перед программистом и открывается кажущийся бескрайним простор для оптимизации кода. Давайте перейдём от сухой теории к практическим рецептам (пока тоже достаточно сухим).

Сортировка в Perl и её оптимизация

Для сортировки массивов и списков в Perl предусмотрена встроенная функция sort, которая в самой простой своей форме может использоваться так:

Листинг 1

# Элементарное применение функции sort

@sorted = sort @unsorted;

В результате выполнения этой команды элементы массива @unsorted сортируются по алфавиту и новый, сортированный, список помещается в массив @sorted[4].

Ценность функции sort для программиста была бы не велика, если бы это была единственная её форма, но, к счастью, функция sort допускает формулирование любого критерия сортировки. Вторая форма такова:

Листинг 2

# Функция sort с заданным критерием сортировки

@sorted = sort {...} @unsorted;

При каждом сравнении в блоке операторов {...} автоматически создаются две локальные переменные $a и $b, которые являются синонимами сравниваемых элементов исходного списка @unsorted. Из-за этой синонимичности менять значение этих переменных весьма нежелательно, это приведёт к изменения соответствующих элементов списка @unsorted и может сбить sort с толку. Результат выполнения блока интерпретируется так же, как результат выполнения операторов <=> и cmp. То есть блок сообщает, какой из двух элементов следует считать меньшим.

Пример:

Листинг 3

# Сортировка чисел по убыванию

@sorted = sort {$b <=> $a} @unsorted;

В этом примере элементы списка сравниваются уже как числа. При каждом сравнении, для пары сравниваемых элементов создаются синонимы – локальные переменные $a и $b; выполняется блок {$b <=> $a}; по его результатам sort делает вывод – надо ли переставить элементы или следует сохранить прежний порядок. Как видите, в нашем случае сортировка выстроит числа, составляющие массив @unsorted по убыванию.

Для иллюстрации подхода, который я собираюсь описать, более подходит следующий пример, реализующий сортировку строк по алфавиту без учёта регистра:

Листинг 4

# Сортировка строк по алфавиту без учёта регистра (оптимизации нет)

@sorted = sort {uc($a) cmp uc($b)} @unsorted;

Здесь, выполняя каждое сравнение, мы преобразуем операнды cmp к верхнему регистру; uc – встроенная функция Perl[6]. Обратите внимание, мы не сохраняем результат работы uc. Вот тут-то и кроется возможность оптимизировать нашу работу.

Итак, блок {uc($a) cmp uc($b)} выполняется столько раз, сколько сравнений необходимо для сортировки. Функция uc вызывается дважды при каждом выполнении блока. Давайте оценим, сколько раз она выполнится.

Цифры оказываются весьма красноречивы. Для сортировки «случайного» (неупорядоченного) списка из 1000 строк понадобится в среднем 19 460 вызовов uc. То есть каждый элемент списка будет преобразован в верхний регистр почти двадцать раз! Для аналогичного списка из 1 000 000 строк Perl придётся вызывать uc 4 3180 000 раз, и каждый элемент будет преобразован более 43 раз. Конечно, такая трата вычислительных ресурсов совершенно не оправданна.

Для оптимизации быстродействия нам придётся пожертвовать памятью, но, к счастью, память сейчас не дорога, а вот время всегда – деньги.

Путь оптимизации очень прост, суть его такова:

Листинг 5

# Оптимизированная сортировка строк по алфавиту без учёта регистра; длинная форма с временными массивами

@temp_unsorted =

    map {[uc, $_]} @unsorted;

@temp_sorted =

    sort {$a->[0] cmp $b->[0]} @temp_unsorted;

@sorted =

    map {$_->[1]} @temp_sorted;

Здесь нам встречается оператор map, позвольте сказать два слова о нём для тех, кто не знаком с Perl. Оператор map получает в качестве аргументов блок операторов и массив; блок операторов применяется последовательно к каждому элементу массива, в каждой итерации переменная $_[7] становится синонимом очередного элемента; все результаты итераций возвращаются оператором в виде массива результатов.

Давайте теперь посмотрим, как работает последний листинг.

Сперва (первый вызов map), мы создаём временный несортированный массив @temp_unsorted, состоящий из указателей на двухэлементные массивы. Нулевой элемент каждого из них содержит критерий сортировки. В нашем случае это строка в верхнем регистре. Первый элемент содержит оригинальную (исходную) строку. Созданная нами конструкция напоминает двумерный массив. В Perl не предусмотрено многомерных массивов, их роль выполняют массивы указателей на массивы. В данном случае нам нужно именно это, и при реализации подобного подхода на других языках понадобится скорее всего нечто подобное. Работа с настоящим двумерным массивом в этой ситуации может оказаться менее эффективной (в зависимости от конкретной реализации двумерных массивов в языке).

Затем (вызов sort) мы сортируем временный массив @temp_unsorted, используя в качестве критерия сортировки нулевые элементы анонимных двухэлементных массивов. В переменной @temp_sorted получаем уже отсортированный массив указателей на наши двухэлементные массивы.

Наконец (второй вызов map), восстанавливаем отсортированный массив @sorted, извлекая оригинальные строки из первых элементов анонимных массивов, указатели на которые составляют @temp_sorted.

Вы уже заметили, что теперь мы вычисляем uc ровно столько раз, сколько у нас сортируемых элементов. Это прогресс! Но теперь кроме sort мы дважды вызываем map. Это лишняя трата времени. Тем не менее, затраты времени на выполнение map растут пропорционально количеству элементов в массиве @unsorted, а экономия времени на выполнение процедуры sort растёт пропорционально количеству сравнений, то есть гораздо быстрее, чем прямая пропорциональность количеству элементов.

Одним словом, при достаточном количестве элементов мы обязательно снизим суммарный расход времени на сортировку. Какое количество элементов следует считать «достаточным»? Это зависит от сложности критерия сортировки. Часто (но не всегда), чем сложнее критерий (тот критерий, который сформулирован в блоке оператора sort), тем меньше надо элементов, чтобы почувствовать выигрыш; но, чем сложнее процедура вычисления критерия (та процедура, которая находится в map), тем больше надо элементов, чтобы выигрыш стал ощутимым. Подробнее это обсудим совсем скоро, а пока рассмотрим детальнее наш последний код.

Всю описанную здесь процедуру можно записать короче и без использования временных массивов:

Листинг 6

# Оптимизированная сортировка строк по алфавиту без учёта регистра; короткая форма без временных массивов

@sorted =

    map {$_->[1]}

    sort {$a->[0] cmp $b->[0]}

    map {[uc, $_]} @unsorted;

Эта конструкция известна как преобразование Рэндала Шварца

Последний код выглядит гораздо более изящно, но иногда уместнее использовать первый вариант (листинг 5) или некий гибридный подход. Например, это полезно, когда критерий сортировки используется многократно, или в тех случаях, когда целесообразно рассчитывать сразу несколько критериев.

В следующем примере мы создаём два сортированных без учёта регистра списка: по алфавиту и в обратном алфавитном порядке. При этом uc вызывается только один раз для каждого элемента.

Листинг 7

# Создание двух сортированных без учёта регистра списков; вдвойне оптимизированная реализация

@temp_unsorted = map {[uc, $_]} @unsorted;

@sorted_a2z = map {$_->[1]}

    sort {$a->[0] cmp $b->[0]} @temp_unsorted;

@sorted_z2a = map {$_->[1]}

    sort {$b->[0] cmp $a->[0]} @temp_unsorted;

Помимо выигрыша, который дала бы оптимизация каждой отдельной сортировки, здесь мы получили дополнительный выигрыш. Если просто дважды применить классическое преобразование Рэндала Шварца, то на одну сортировку потребовалось бы два вызова map. Здесь же на каждую сортировку приходится полтора вызова map (три map на два sort). Причём реальный выигрыш ещё больше, так как дважды выполняется процедура map, восстанавливающая данные, а процедура расчёта критерия сортировки (более ресурсоёмкая, чем восстановление данных) выполняется всего один раз на две сортировки. То есть для каждой из двух сортировок на один элемент понадобилась половина, если можно так сказать, вызова uc. Впечатляющий результат?! Особенно, если вспомнить, что если бы мы просто дважды использовали неоптимизированный код, аналогичный приведённому в листинге 4, применительно к массиву из миллиона строк, то каждая строка была бы преобразована к верхнему регистру без малого сто раз (более 86 раз).

Вернёмся теперь к вопросу о том, какой же список следует считать «достаточно» длинным, и какой критерий сортировки – «достаточно» сложным.

Тестируйте, тестируйте и ещё раз тестируйте

Переходим от теории к практике: к тестам на реальных задачах.

Я производил свои тесты на Perl версии 5.6.1 (revision 5.0 version 6 subversion 1) я оценки производительности кода использовался метод timethese стандартного пакета Benchmark. Все тесты производились на изначально несортированных, «случайных», массивах. Тесты производились многократно, результаты усреднялись.

Давайте для начала сравним производительность кода листинга 4 (без оптимизации) и листинга 6 (с оптимизацией).

При сортировке списка из 1000 однокилобайтных строк оптимизированный код показывает производительность, в пять раз превосходящую производительность неоптимизированного кода. При сортировке аналогичного списка из 100 элементов выигрыш от оптимизации снижается, становясь четырёхкратным. При работе со списком из 10 элементов выигрыш становится меньше трёхкратного. Для пяти элементов – менее двукратного. Наконец, с двухэлементным списком оптимизированная сортировка работает примерно вдвое медленнее, чем неоптимизированная

Для иллюстрации ещё одного приёма оптимизации и тестов предлагаю средней сложности сортировку.

Пусть у нас имеется некий список версий вида:

Листинг 8 

# Список версий

@unsorted=("Ver 1.0",

           "version 1.1",

           "v. 1.10",

           "ver 2.20",

           "Ver 2.0",

           "Version 2.3",

           "V 2.12");

Нам необходимо отсортировать его по возрастанию номера версии. Сортировка по алфавиту (как в листинге 1) не даст ничего удовлетворительного. Сортировка версий, как десятичных дробей тоже потерпит крах, так как в этом случае окажется, что 1.1 равно 1.10, а 2.3 больше, чем 2.12. Здесь нужен более деликатный подход[11].

Простой вариант без оптимизации может выглядеть так:

Листинг 9

# Сортировка списка версий без оптимизации

@sorted=sort {

    my ($ap, $as)=($a=~m/(d+).(d+)/);

    my ($bp, $bs)=($b=~m/(d+).(d+)/);

    $ap <=> $bp || $as <=> $bs; } @unsorted;

Для сравнения двух строк мы выделяем по два числа из каждого сравниваемого элемента сортируемого списка и производим сравнение этих чисел. Версия и подверсия, выделенные из элемента $a, помещаются в переменные $ap и $as соответственно; элемент $b обрабатывается аналогично. Если номера версий равны, то сравниваются подверсии

Вариант с нашей оптимизацией будет выглядеть так:

Листинг 10 

# Сортировка списка версий с оптимизацией

@sorted=map  { $_->[0] }

           sort { $a->[1] <=> $b->[1] ||

                 $a->[2] <=> $b->[2]; }

           map  { m/(d+).(d+)/;

                 [$_, $1, $2]; } @unsorted;

Этим примером я хотел продемонстрировать, что вспомогательный массив (создаваемый вторым по тексту оператором map) может содержать указатели не только на двухэлементные анонимные массивы. В нашем случае критерий сортировки достаточно сложен и мы создаём трёхэлементные анонимные массивы: нулевой элемент – оригинальная строка, первый – номер версии, второй – номер подверсии.

С точки зрения расхода памяти такой подход достаточно расточителен, тем не менее он часто бывает оправдан, когда критерий сравнения достаточно сложен.

Однако наш пример не настолько сложен, в чём мы сейчас и убедимся, не только усовершенствовав оптимизацию и ускорив процедуру сортировки, но и сэкономив память.

Воспользуемся соображением, что номер версии и подверсии не может быть больше 999. Тогда мы можем преобразовать версию и подверсию в одно число по формуле:

[версия]*1000+[подверсия]

То есть 1.1 превратится в 1001, а 1.10 – в 1010. Сортировка таких чисел, очевидно, аналогична правильной сортировке версий.

Новый код будет выглядеть так:

Листинг 11

# Сортировка списка версий с дополнительной оптимизацией

@sorted=map  { $_->[0] }

sort { $a->[1] <=> $b->[1] }

map  { m/(d+).(d+)/;

               [$_, $1*1000+$2]; } @unsorted;

Обратите внимание, как упростилась процедура сравнения. Это стоило нам небольшого усложнения (и замедления выполнения) кодирующего (второго по тексту) map. Но зато теперь память используется более экономно и, что самое главное, сравнение двух элементов в блоке оператора sort происходит гораздо быстрее.

Какова же производительность этих кодов? Как показывают тесты, наш успех не всегда можно назвать головокружительным[13].

При сортировке списка из 1000 элементов: первая оптимизация (листинг 10) даёт выигрыш в 4 раза (здесь и далее будем сравнивать с неоптимизированным кодом из листинга 9); дополнительная оптимизация (листинг 11) даёт ещё больший выигрыш – в 4.7 раза.

При сортировке списка из 100 элементов: первая оптимизация даёт выигрыш в 3.8 раза, вторая оптимизация уже не способна дать дополнительный выигрыш, она работает чуть медленнее первой и даёт выигрыш в 3.7 раза.

Такая же ситуация, только более ярко выраженная, наблюдается при сортировке списка из десяти элементов: первая оптимизация – выигрыш в два раза, вторая оптимизация – выигрыш только в 1.7 раза.

Для списка из пяти элементов тестирование даёт следующие результаты: первая оптимизация по-прежнему даёт заметный выигрыш в 1.34 раза, вторая оптимизация продолжает себя дискредитировать, давая выигрыш всего в 1.19 раза.

Мораль, я думаю, уже понятна: чем продуманнее оптимизация, тем она, без сомнения, эффективнее; но её эффективность начинает проявляться только при сортировке достаточно длинных списков. Причём эта критическая длина возрастает с ростом продуманности оптимизации.

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

Есть ещё одно существенное соображение. Вы видели, что при работе с большими списками код из листинга 11 более производителен, чем код из листинга 10. Однако промежуточный массив, возникающий при работе листинга 10, позволил бы весьма гибко выполнять самые разные сортировки (конечно, если бы мы его сохранили подобно тому, как мы это сделали в листинге 7 при создании двух сортированных массивов). Например, мы могли бы сортировать список версий по возрастанию версии, но убыванию подверсии. То есть, совершенствуя наше решение, мы снизили его универсальность, которая могла бы оказаться полезной в каких-то ситуациях.

Одним словом, абсолютно универсального решения не существует. Каждый подход хорош только в определённых условиях. Если вы намерены всерьёз позаботиться о производительности своего кода, то я посоветовал бы ознакомиться со страницами руководства perldoc Benchmark и всегда тестировать свой код. Причём тестирование, как вы уже убедились, следует проводить в условиях максимально «приближенных к боевым».