Изучаем Perl


Сортировка по заданным критериям


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

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

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

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

sub by_number (

if ($a < $b) ( return -1;

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

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

) >

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

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

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

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

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

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

Swronglist = sort Osomelist; # Owronglist теперь содержит (1,128,16,2,256,32,4,64,8)

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

@rightlist = sort by_number Swronglist;

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

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

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

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

sub by_number ( $а <=> $b;

}

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

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

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

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

@result = sort ( $а cmp $b } Osomelist;

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

sub by mostly_numeric (

($a <=> $b) I I ($a cmp $b) ;

)

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

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

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

* Не вполне соответствующая. Встроенная функция sort отбрасывает злементы undef, а зта функция — нет.

сортировку относительно данного значення. Если следовать зтой логике, то программа практически напишется сама:

@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);

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









Начало  Назад  Вперед


Книжный магазин