Расширенная сортировка

А если вам нужна числовая сортировка? Или сортировка без учета регистра символов? А может, вы хотите отсортировать данные на основании информации, хранящейся в хеше? Perl предоставляет возможность отсортировать список в любом желательном порядке; до конца главы вы увидите немало примеров. Информация о порядке сортировки передается Perl в виде функции сортировки. Возможно, после начального курса информатики слова «функция сортировки» вызывают у вас кошмарные видения пузырьковой сортировки, сортировки по Шеллу и быстрой сортировки; вы качаете головой и говорите: «Нет, ни за что!» Не беспокойтесь, все не так страшно. Perl уже умеет сортировать списки; он просто не знает, какой порядок вам нужен. Функция сортировки всего лишь укажет ему, как это делать.

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


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

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

sub any_sort_sub { # На самом деле этого не происходит
my($a, $b) = @_; # Получить параметры и присвоить их переменным
# Начинаем сравнивать $a и $b
...
}

Но функция сортировки будет вызываться снова и снова, нередко по несколько тысяч раз. Объявление переменных $a и $b занимает немного времени, как и присваивание им значений в начале функции, но умножьте на тысячи вызовов функции, и они окажут заметное влияние на общую скорость выполнения. Конечно, нам бы этого не хотелось. (Но даже если вы поступите подобным образом, такое решение работать не будет.) Все выглядит так, словно Perl уже выполнил присваивание за вас еще до начала выполнения кода функции.


Вы пишете функцию сортировки без первой строки; переменные $a и $b уже содержат нужные значения. В начале функции сортировки в них хранятся два элемента исходного списка. Функция возвращает код, определяющий результат сравнения элементов (по аналогии с функцией C qsort(3), но здесь используется собственная внутренняя реализация сортировки Perl). Если значение $a должно предшествовать $b в итоговом списке, функция сортировки сообщает об этом, возвращая значение –1. Если значение $b должно предшествовать $a, функция возвращает 1.

Если порядок $a и $b неважен, функция возвращает 0. Как такое может быть? Допустим, сортировка выполняется без учета регистра символов и сравниваются две строки fred и Fred… Или при выполнении числовой сортировки сравниваются два одинаковых числа. Простейшая функция числовой сортировки выглядит так:

sub by_number {
# Функция сортировки, переменные $a и $b уже подготовлены
if ($a < $b) { -1 } elsif ($a > $b) { 1 } else { 0 }
}

Чтобы использовать эту функцию при сортировке, укажите ее имя (без префикса &) между ключевым словом sort и сортируемым списком. В следующем примере отсортированный список чисел помещается в @result:

my @result = sort by_number @some_numbers;

Обратите внимание: в функции сортировки мы не пытаемся объявлять переменные $a and $b или задавать их значения – если это сделать, функция будет работать неправильно.


Мы просто поручаем Perl задать $a и $b, а нам остается лишь написать функцию сравнения. В действительности функцию можно сделать еще проще (и еще эффективнее). Поскольку такие трехсторонние сравнения встречаются достаточно часто, в Perl предусмотрена удобная сокращенная форма для их записи: оператор <=>. Этот оператор сравнивает два числа и возвращает –1, 0 или 1, необходимые для их числовой сортировки. Таким образом, ту же функцию сортировки можно записать в упрощенном виде:

sub by_number { $a <=> $b }

Если оператор <=> сравнивает числа, нетрудно предположить, что и для строк существует свой оператор трехстороннего сравнения: cmp. Эти два оператора легко запоминаются и просты в использовании. Оператор <=> напоминает числовые операторы вида >=, но состоит из трех символов вместо двух, потому что может возвращать три возможных значения вместо двух. А оператор cmp похож на операторы сравнения строк вроде ge, но состоит из трех символов вместо двух по тем же причинам. Конечно, cmp сам по себе обеспечивает тот же порядок, что и сортировка по умолчанию. Функцию, которая всего лишь обеспечивает стандартный порядок сортировки, даже не нужно писать:

sub ASCIIbetically { $a cmp $b }
my @strings = sort ASCIIbetically @any_strings;

Однако cmp может использоваться для определения более сложного порядка сортировки – скажем, сортировки без учета регистра символов:

sub case_insensitive { "\L$a" cmp "\L$b" }

В этом случае строка из $a (приведенная к нижнему регистру) сравнивается со строкой из $b (приведенной к нижнему регистру); в результате мы получаем сортировку без учета регистра.


Обратите внимание: сами элементы при этом не изменяются, мы всего лишь используем их значения. Это очень важно: по соображениям эффективности $a и $b не являются копиями элементов данных. Они представляют собой временные псевдонимы для элементов исходного списка, а их изменение приведет к повреждению исходных данных. Никогда так не делайте. Если ваша функция сортировки не сложнее, чем функции из наших примеров (а обычно так оно и есть), программу можно дополнительно упростить: замените имя функции сортировки «встроенным» фрагментом кода:

my @numbers = sort { $a <=> $b } @some_numbers;

В современных Perl-программах отдельные функции сортировки почти не встречаются. Обычно они записываются во встроенном виде, как в нашем примере. Допустим, список необходимо отсортировать в числовом порядке по убыванию. Задача легко решается при помощи функции reverse:

my @descending = reverse sort { $a <=> $b } @some_numbers;

Но мы покажем еще один красивый трюк. Операторы сравнения (<=> и cmp) «близоруки»; они смотрят не на то, какой операнд хранится в $a или в $b, а на то, где он стоит – слева или справа. Таким образом, если переставить $a и $b местами, оператор сравнения будет каждый раз получать обратный результат.


Следовательно, числовую сортировку по убыванию можно выполнить и таким способом:

my @descending = sort { $b <=> $a } @some_numbers;

После небольшой тренировки такие конструкции легко читаются «с листа». Элементы упорядочиваются по убыванию (потому что $b предшествует $a), при этом используется числовое сравнение (оператор <=> вместо cmp). Получается, что встроенная функция сортирует числа в обратном порядке. (В современных версиях Perl выбор варианта не влияет на эффективность; reverse распознается как модификатор sort. Компилятор выбирает «короткий путь», чтобы список не пришлось сортировать в одну сторону только для того, чтобы немедленно развернуть его в обратном направлении.)

Оцените статью: (0 голосов)
0 5 0

Статьи из раздела Perl на эту тему:
Использование функции sprintf для вывода денежных сумм
Операции с подстроками и функция substr
Поиск подстроки по индексу
Сортировка по нескольким ключам
Сортировка хеша по значениям

Вернуться в раздел: Perl / 13. Строки и сортировка