Perl. Библиотека программиста

Сортировка списка по вычисляемому полю

Проблема

Требуется отсортировать список, руководствуясь более сложным критерием, нежели простыми строковыми или числовыми сравнениям.

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

Решение

Воспользуйтесь нестандартной функцией сравнения в sort:

@ordered = sort { compare() } @unordered;

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

@precomputed = map { [compute (), $_] } @unordered;
@ordered_precomputed = sort { $a->[0] <=> $b->[0] } @precomputed;
@ordered = map { $_->[1] } @ordered_precomputed;

Наконец, эти три шага можно объединить:

@ordered = map { $_->[1] }
sort { $a->[0] <=> $b->[0] }
map { [compute(), $_] }
@unordered;

Комментарий

Помимо использования встроенных операторов вроде <=>, можно конструировать более сложные условия:

@ordered = sort { $a->name cmp $b->name } @employees;

Функция sort часто используется подобным образом в циклах fоreach:

foreach $employee (sort ($а->name cmp $b->name } @employees) {
  print $employee->name, " earns \$", $employee->salary, "\n";
}

Если вы собираетесь много работать с элементами, расположенными в определенном порядке, эффективнее будет сразу отсортировать их и работать с отсортированным списком:

@sorted_employees = sort { $a->name cmp $b->name } @employees;
foreach $employee (@sorted_employees) {
  print $employee->name, "earns \$", $employee->salary, "\n";
}
# Загрузить %bonus
foreach $employee (@sorted_employees) {
  if ($bonus{ $employee->ssn } ) {
    print $employee->name, "got a bonus! \n";
  }
}

В функцию можно включить несколько условий и разделить их операторами ||. Оператор || возвращает первое истинное (ненулевое) значение. Следовательно, сортировку можно выполнять по одному критерию, а при равенстве элементов (когда возвращаемое значение равно 0) сортировать по другому критерию. Получается «сортировка внутри сортировки»:

@sorted = sort {$a->name cmp $b->name || $b->age <=> $a->age} @employees:

Первый критерий сравнивает имена двух работников. Если они не совпадают, || прекращает вычисления и возвращает результат cmp (сортировка в порядке возрастания имен). Но если имена совпадают, || продолжает проверку и возвращает результат <=> (сортировка в порядке убывания возраста). Полученный список будет отсортирован по именам и по возрасту в группах с одинаковыми именами. Давайте рассмотрим реальный пример сортировки. Мы собираем информацию обо всех пользователям в виде объектов User::pwent, после чего сортируем их по именам; и выводим отсортированный список:

use User::pwent qw(getpwent);
@users = ();
# Выбрать всех пользователей
while (defined($user = getpwent))  {
  push(@users, $user);
}
@users = sort {$a->name cmp $,->name} @users;
foreach $user (@users) {
  print $user->name, "\n";
}

Возможности не ограничиваются простыми сравнениями пли комбинациями простых сравнений. В следующем примере список имен сортируется по второй букве имени. Вторая буква извлекается функцией substr:

@sorted = sort { substr($a,1,1) cmp substr($b,1,1) } @names;

А ниже список сортируется по длине строки:

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

Функция сравнения вызывается sort каждый раз, когда требуется сравнить два элемента. Число сравнений заметно увеличивается с количеством сортируемых элементов. Сортировка 10 элементов требует (в среднем) 46 сравнений, однако при сортировке 1000 элементов выполняется 14000 сравнении. Медленные операции (например, split или вызов подпрограммы) при каждом сравнении тормозят работу программы.

К счастью, проблема решается однократным выполнением операции для каждого элемента перед сортировкой. Воспользуйтесь map для сохранения результатов операции в массиве, элементы которого являются анонимными массивами с исходным и вычисленным полем. Этот «массив массивов» сортируется по предварительно вычисленному полю, после чего map используется для получения отсортированных исходных данных. Концепция map/sort/map применяется часто и с пользой, поэтому ее стоит рассмотреть более подробно.

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

@temp = map { [length $_, $_] } @strings;
@temp = sort { $a-> [0] <=> $b->[0] } @temp;
@sorted = map { $_->[1] } @temp;

В первой строке map создает временный массив строк с их длинами. Вторая строка сортирует временный массив, сравнивая их предварительно вычисленные длины. Третья строка превращает временный массив строк/длин в отсортированный массив строк. Таким образом, длина каждой строки вычисляется всего один раз.

Поскольку входные данные каждой строки представляют собой выходные данные предыдущей строки (массив @temp, созданный в строке 1, передается sort в строке 2, а результат сортировки передается map в строке 3), их можно объединить в одну команду и отказаться от временного массива:

@sorted = map { $_->[1] }
sort {$а->[0] <=> $b->[0] }
map { [ length $_, $_] }
@strings;

Теперь операции перечисляются в обратном порядке. Встречая конструкцию /sort/map, читайте ее снизу вверх:

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

map: нижний вызов map строит временный список анонимных массивов. Список содержит пары из предварительно вычисленного поля (length $_) и исходного элемента ($_). В этой строке показано, как происходит вычисление поля.

sort: список анонимных массивов сортируется посредством сравнения предварительно вычисленных полей. По этой строке трудно о чем-то судить – разве что о том, будет ли список отсортирован в порядке возрастания или убывания.

mар: вызов map в начале команды превращает отсортированный список анонимных массивов в список исходных отсортированных элементов. Как правило, во всех конструкциях map/sort/map он выглядит одинаково.

Ниже показан более сложный пример, в котором сортировка выполняется по первому числу, найденному в каждой строке @fields:

@temp = map { [ /(\d+)/, $_ ] } @fields;
@sorted_temp = sort {$a->[0] <=> $b->[0] > @>temp;
@sorted_fields = map { $_->[1] } @sorted_temp;

Регулярное выражение в первой строке извлекает из строки, обрабатываемой map, первое число. Мы используем регулярное выражение /(\d+)/ в списковом контексте.

Из этого фрагмента можно убрать временный массив. Код принимает следующий вид:

@sorted_fields = map { $_->[1] }
sort { $а->[0] <=> $b->[0] }
map { [ /(\d+)/, $_ ] }
@fields;

В последнем примере выполняется компактная сортировка данных, разделенных запятыми (они взяты из файла UNIX passwd). Сначала выполняется числовая сортировка файла по четвертому полю (идентификатору группы), затем — числовая сортировка по третьему полю (идентификатору пользователя) и алфавитная сортировка по первому полю (имени пользователя).

print map { $_->[0] }      # Целая строка
sort { 
  $а->[1] <=> $b->[1]      # Идентификатор группы 
        ||
  $а->[2] <=> $b->[2]      # Идентификатор пользователя
        ||
  $а->[3] <=> $b->[3]      # Имя пользователя
}
mар { [ $_, (split /:/)[3,2,0] ] }
'cat /etc/passwd';

См. также

Описание функции sort