Выпуск 4. Июнь 2013

← От редактора | Содержание | Создание RSS из списка файлов →

Сортировка в Perl

Если для сравнения элементов массива используется нетривиальная функция, сортировку массива можно ускорить, кэшируя ключи сортировки или подобрав функцию попроще.

Основы

Каждый программист сталкивается с задачей упорядочения массивов данных. Иногда по пять раз еще до завтрака. Хорошо, если данные сразу приходят упорядоченными из внешнего источника (базы данных, файловой системы и т.п.), если нет — тоже не страшно, можно в самой программе отсортировать.

Существует несколько десятков алгоритмов сортировки. Почтенный дедушка Дональд Кнут написал о них эпохальный труд сорок лет назад. Самые удачные алгоритмы всем известны и «прошиты» в языки программирования и стандартные библиотеки.

В Perl тоже есть встроенная функция сортировки. Называется sort. Работает в списковом контексте, принимает неупорядоченный список, возвращает упорядоченный.

my @sorted = sort @unsorted;

На этом, кажется, можно было закончить. Но рассмотрим случаи посложнее.

Программисту не обязательно знать, какой именно алгоритм сортировки у Perl под капотом (хотя способ узнать и даже изменить есть).

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

Функция сравнения

Если для sort не указана функция сравнения, будет использована операция cmp — лексикографическое сравнение строк. Четыре наиболее популярных функции:

{ $a <=> $b }
{ $b <=> $a }
{ $a cmp $b }
{ $b cmp $a }

заменяются на встроенный код, выполняющийся очень быстро.

Иногда можно встретить замечание, что
reverse sort { $a <=> $b } @list
выполняется быстрее, чем
sort { $b <=> $a } @list
В современных версиях Perl это не так. Не используйте reverse для изменения порядка сортировки.

Функция сравнения должна возвращать число, меньшее, большее или равное нулю, в зависимости от того, как переменные $a и $b связаны отношением порядка. Но даже встроенные функции не всегда соблюдают это требование: операция численного сравнения <=> возвращает undef, если в операндах есть NaN, «не-число». Поэтому избегайте списков, содержащих NaN, результат их сортировки будет неопределенным. Очистить список можно так:

@clean = grep { $_ == $_ } @nans;

Сортировка по нескольким полям

Одной операцией сравнения не обойтись если нужна комбинированная сортировка. Очень удобно объединять несколько сравнений с помощью || — логического «или».

Упорядочим строки сначала по длине, затем (строки одной длины) лексикографически:

my @sorted = sort {
    length $a <=> length $b
    ||
    $a cmp $b
} @strings;

Для первой операции ключом сортировки является длина строки, для второй — сама строка.

Теперь упорядочим список сотрудников по фамилии, имени и размеру тапочек (тапочки сортируем от больших к меньшим):

my @sorted = sort {
    $a->{LastName}  cmp $b->{LastName}  ||
    $a->{FirstName} cmp $b->{FirstName} ||
    $b->{ShoeSize}  <=> $a->{ShoeSize}
} @employees;

Такая функция сравнения уже достаточно сложна, чтобы занимать заметное процессорное время, учитывая, что для списка из тысячи элементов она будет вызвана десяток тысяч раз. Запомните: всё, что происходит в функции сравнения, происходит O(n log n) раз.

Маневр орков (Orcish Maneuver, OM)

Во многих задачах ключ сортировки вычисляется сложной или недетерминированной функцией, или даже внешней функцией (XSUB). Популярный пример — сортировка списка файлов по времени модификации. Очевидная реализация:

sort { -m $a <=> -m $b } @files;

имеет два недостатка: во-первых, функция stat будет вызвана столько раз, сколько потребуется сравнений, то есть O(n log n). Во-вторых, между вызовами функции файл может быть изменен, получив новое значение в качестве ключа.

Закэшируем вычисленное значение времени модификации. Тогда для каждого файла функция stat будет вызвана единожды:

my %mod_times;  # cache
my @sorted = sort {
    ( $mod_times{$a} //= -M $a )
    <=>
    ( $mod_times{$b} //= -M $b )
} @files;

Оба недостатка ликвидированы.

Название идиомы происходит от созвучия слов «Or» и «Cache» со словом «Orcish»; пока в Perl не появился оператор defined-or, приходилось использовать обычное or, с тем неудобством, что если значение ключа интерпретировалось как false, оно вычислялось повторно.

Преобразование Шварца (Schwartzian transform, ST)

Добиться вычисления ключа только один раз для каждого элемента можно иным способом:

Дополним элементы исходного списка вычисленным ключом: построим новый список с элементами-кортежами вида [item, sortkey], которые содержат собственно элемент и ключ сортировки.
Упорядочим новый список «по второй колонке».
Извлечем из упорядоченного списка исходные элементы.

Perl позволяет лаконично записать такое преобразование с использованием анонимных списков:

my @sorted = map  { $_->[0] }
             sort { $a->[1] <=> $b->[1] }
             map  { [$_, -M] }
                  @files;

Эта идиома программирования названа в честь Рэндала Л. Шварца, соавтора многих книг о Perl (в частности, легендарной «Llama book»). Рэндал Шварц продемонстрировал её в 1994 году, вскоре после выхода Perl 5.

Справедливости ради заметим, что метод был известен и ранее, в других языках, как идиома «decorate-sort-undecorate», а название «Schwartzian transform» применяется в основном в Perl-практике.

Ключ будет вычислен ровно N раз для списка из N элементов. Поскольку нет расходов на поиск в хеш-таблице, ST, как правило, выполняется быстрее, чем OM. Но если сортируемый список содержит значительное число одинаковых элементов, то метод OM может оказаться эффективнее: попадание в кэш будет происходить чаще (на всякий случай напомню, что если множество значений элементов мало, то можно упорядочить список вообще за линейное время — смотрите сортировку подсчетом).

Преобразование Гаттмана-Рослера (Guttman-Rosler Transform, GRT)

Вызов пользовательской функции сравнения достаточно дорог, а обычное численное или лексикографическое сравнение выполняется быстро. Метод оптимизации, предложенный Perl-хакерами Uri Guttman и Larry Rosler, заключается в преобразовании элементов сортируемого списка таким образом, чтобы их сравнение выполнялось встроенными функциями.

Допустим, исходный список представляет собой набор кортежей-троек целых чисел в диапазоне от 0 до 99 включительно, и упорядочить его нужно сначала по первым числам, затем по вторым и т.д. Сортировка с пользовательской функцией сравнения:

my @sorted = sort {
    $a->[0] <=> $b->[0] ||
    $a->[1] <=> $b->[1] ||
    $a->[2] <=> $b->[2]
} @triplets;

Воспользуемся тем фактом, что числа укладываются в два десятичных разряда и составим из троек целые числа в диапазоне [ 0, 999999 ] (они даже помещаются в машинное целое). Затем отсортируем полученные элементы обычным численным сравнением $a <=> $b (несмотря на то, что код тоже выглядит как пользовательская функция, Perl будет использовать встроенный метод). Наконец, разобьем числа на тройки по двум цифрам, вернув исходное представление:

my @sorted = map  {
                      $x = int($_ / 100**2);
                      $y = int($_ / 100) - $x * 100;
                      $z = $_ % 100;
                      [ $x, $y, $z ];
                  }
             sort { $a <=> $b }
             map  { $_->[0] * 100**2 + $_->[1] * 100 + $_->[2] }
                  @triplets;

На массивах из ста тысяч элементов можно получить выигрыш в скорости выполнения более чем в два раза.

Второй вариант — преобразовать тройки чисел в строки длиной три байта и упорядочить их лексикографически:

my @sorted = map  { [ unpack "C3", $_ ] }
             sort
             map  { pack "C3", @$_ }
                  @triplets;

Для упаковки сортируемых объектов в числа или строки есть множество способов:

запись в битовые поля;
арифметическое кодирование;
формирование строк фиксированной длины (padding);
формирование строк с разделителями, например, нулевыми байтами.

Здесь будут полезны функции sprintf, pack, join, регулярные выражения. При сериализации чисел в строку не забывайте выравнивать их по правому краю, дополняя нулями или пробелами, и использовать фиксированное число знаков после точки. Побитовое отрицание над строками удобно, чтобы изменить порядок сортировки строк на обратный. Не забудьте, что на лексикографическое сравнение действует включенная локаль (locale collation).

Сериализация и десериализация данных — также довольно дорогие действия. Насколько эффективным будет GRT, зависит от способа сериализации, от сложности функции сравнения и от отношения количества сравнений к количеству преобразований данных. Можно ускорить сортировку на порядок, можно и наоборот, потерять в скорости. Обязательно протестируйте несколько вариантов упаковки объектов на данных, максимально приближенных к реальным.

Выбор алгоритма сортировки

Начиная с версии 5.8, Perl использует два алгоритма сортировки: mergesort — сортировку слиянием, и quicksort — быструю сортировку.

В большинстве случаев выгоднее алгоритм mergesort: он имеет гарантированную сложность O(n log n), в то время как quicksort деградирует до квадратичной сложности в худших случаях, и он устойчив, то есть сохраняет исходный порядок элементов, равных по ключу.

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

Вы можете указать предпочитаемый алгоритм директивой (прагмой) sort, например, потребовать, чтобы обязательно использовался устойчивый алгоритм:

use sort qw(stable);

Директива действует в лексической области видимости.

Модули CPAN

Sort::Maker

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

Sort::MultipleFields

Не содержит никаких оптимизаций, зато позволяет записать сортировку по нескольким полям компактнее и понятнее.

Sort::Key

Самая лучшая оптимизация — написать функцию сравнения на C. Модуль предоставляет целую пачку XSUB для сравнения ключей и ссылается на не меньшую пачку модулей Sort::Key::*.

Sort::Fields

Весьма старый, но вполне работающий модуль для сортировки текстовых таблиц (наподобие CSV).

Sort::XS

Еще один XS-модуль, предоставляющий уже не функции сравнения, а собственно алгоритмы сортировки.

Sort::External

Реализация внешней сортировки, то есть сортировки списков, не помещающихся в память. Подмодуль Sort::External::Cookbook содержит прекрасное описание метода GRT.

Заключение

Функция сравнения вызывается O(n log n) раз.
Кэшируйте ключи сортировки.
Упакуйте элементы списка в числа или строки и сравнивайте их одной операцией.
Как водится, на CPAN есть много вкусного.

Исходные тексты с тестами производительности

1-basic.pl

Тестирование тривиальных операций сравнения. Для сортировки в обратном порядке функция reverse не дает преимуществ. Если же в результате операции изменить знак, функция будет воспринята уже как пользовательская, а не встроенная — с соответствующим падением производительности.

2-om-st.pl

Упорядочим набор точек на плоскости по расстоянию до центра (или, если угодно, упорядочим векторы по длине). Расчет длины вектора даже в 2-мерном пространстве достаточно трудоемок, чтобы кэширование принесло значительную пользу. ST справляется быстрее, чем OM.

3-om-st-cardinality.pl

Изменим предыдущую задачу так, чтобы набор содержал большое число одинаковых точек (в примере генерируются точки с целыми координатами в диапазоне [0, 10], то есть всего сто уникальных значений). На этот раз OM быстрее, чем ST.

4-grt.pl

Сортировка троек целых чисел методом GRT. Три различных способа сериализации; упаковка в битовые поля наиболее эффективна.

■ Олег Алистратов