Глава 15: Другие операции преобразования данных.
15.4 Сортировка по заданным критериям

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

Чтобы задать порядок сортировки, следует определить программу сравнения, которая задает способ сравнения двух элементов. Для чего она нужна? Нетрудно понять, что сортировка — это размещение множества элементов в определенном порядке путем их сравнения между собой. Поскольку сравнить сразу все элементы нельзя, нужно сравнивать их по два й, используя результаты этих попарных сравнений, расставить все их по местам.

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

Чтобы повысить скорость выполнения, эти два значения передаются в подпрограмму не в массиве, а как значения глобальных переменных $а и $b. (Не волнуйтесь: исходные значения $ а и $b надежно защищены.) эта подпрограмма должна возвратить любое отрицательное число, если $а меньше $b, нуль, если $а равно $b, и любое положительное число, если $а больше $b. Теперь учтите, что "меньше чем" соответствует вашему пониманию этого результата в данном конкретном случае; это может быть сравнение чисел, сравнение по третьому символу строки, наконец, сравнение по значениям какого-то хеша с использованием передаваемых значений как ключей — в общем, это очень гибкий механизм.

Вот пример подпрограммы сортировки в числовом порядке:

sub by_number {
  if ($a < $b) {
    return -1;

  } elsif ($a == $b) {
    return 0;

  } elsif ($a > $b) {
    return 1;
  }
}

Обратите внимание на имя by_number. На первый взгляд, в имени этой подпрограммы нет ничего особенного, но скоро вы поймете, почему нам нравятся имена, которые начинаются с префикса bу_.

Давайте разберем эту подпрограмму. Если значение $а меньше (в данном случае в числовом смысле), чем значение $b, мы возвращаем значение -1.

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

Как использовать данную программу? Давайте попробуем рассортировать такой список:

@somelist = (1,2,4,8,16,32,64,128,256);

Если использовать с этим списком обычную функцию sort без всяких "украшений", числа будут рассортированы так, как будто это строки, причем сортировка будет выполнена с учетом кодов ASCII, т.е.:

$wronglist = sort @somelist; 

# @wronglist теперь содержит (1,128,16,2,256,32,4,64,8)

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

@rightlist = sort by_number $wronglist;

# @rightlist теперь содержит (1,2,4,8,16,32,64,128,256)

Задача решена. Обратите внимание: функцию sort можно прочитать вместе с ее спутницей, программой сортировки, на человеческом языке, т.е. "рассортировать по числовым значениям". Бот почому мы использовали в имени подпрограммы префикс bу_ ("по").

Такое тройное значение (-1, 0, +1), отражающее результаты сравнения числовьк значений, встречается в программах сортировки достаточно часто, поэтому в Perl есть специальная операция, которая позволяет сделать все это за один раз. Эту операцию часто называют "челноком" (или "космическим кораблем", как следует из дословного перевода английского spaceship), потому что ее знак — <=>.

Используя "космический корабль", можно заменить предыдущую под-программу сортировки следующим кодом:

sub by_number {
  $а <=> $b;
}

Обратите внимание на знак операции между двумя переменными. Да, он действительно состоит из трех символов. эта операция возвращает те же значения, что и цепочка if/elsif из предыдущего определения этой программы. Теперь все записано очень кратко, но этот вызов можно сокра-тить и дальше, заменив имя подпрограммы сортировки самой подпрограммой, записанной в той же строке:

@rightlist = sort ($а <=> $b) @wronglist;

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

Для операции сравнения числових значений "челнок" есть соответствующая строковая операция — cmp*. Эта операция возвращает одно из трех значений в зависимости от результата сравнения двух аргументов по строковым значениям. Вот как можно по-другому записать порядок сортировки, который установлен по умолчанию:

@result = sort ( $а cmp $b ) @somelist;

Вам, вероятно, никогда не придется писать именно такую подпрограмму (имитирующую встроенную функцию стандартной сортировки) — если только вы не пишете книгу о Perl. Тем не менее, операция cmp все же находит применение в каскадних схемах упорядочивания. Например, вам необходимо расставить элементы по численним значениям, если они численно не равны; при равенстве они должны идти быть упорядочены по строковым значениям. (По умолчанию приведенная выше подпрограмма by_number просто ставит нечисловые строки в случайном порядке, потому что при сравнении двух нулевих значений числовое упорядочение провести нельзя.) Вот как можно сказать "числовые, если они численно не равны, иначе строковие":

sub by_mostly_numeric {
  ($a <=> $b) || ($a cmp $b);
}

Этот код работает следующим образом. Если результат работы "челнока" равен -1 или 1, то остальная часть выражения пропускается и возвращается -1 или 1. Если "челнок" дает нуль, то выполняется операция cmp, которая возвращает соответствующее значение, сравнивая сортируемие значения как строки.

Сравниваются не обязательно те значения, которне передаются в программу. Пусть, например, у вас есть хеш, ключи которого — регистрационные имена, а значения — реальные имена пользователей. Предположим, вы хотите напечатать таблицу, в которой регистрационные и реальные имена будут рассортированы по порядку реальних имен.

Сделать это довольно легко. Давайте Предположим, что значения находятся в массиве % names. Регистрационные имена, таким образом, представляют собой список keys (%names). Нам нужно получить список регистрационных имен, рассортированных по соответствующим значениям, поэтому для любого конкретного ключа $а мы должны проверить значение $names ($а) и провести сортировку относительно данного значения. Если следовать этой логике, то программа практически напишется сама:

@sortedkeys = sort_by_name keys (%names);

sub by_names {
  return $names{$a} cmp $names($b};
}

foreach (@sortedkeys) {
  print "$_ has a real name of $names($_)\n";
}

K этому нужно еще добавить "аварийное" сравнение. Предположим, что реальные имена двух пользователей совпадают. Из-за капризной натуры программы sort мы в первый раз можем получить эти значения в одном порядке, а во второй раз — в другом. Это плохо, если данный результат придется, например, вводить в программу сравнения для формирования отчета, поэтому следует избегать таких вещей. Задача легко решается с помощью операции cmp:

sub by_names {
  ($names($a} cmp $names($b}) || ($a cmp $b);

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