Перевод Anton Petrusevich <casus@mail.ru>, Alex Ott <ott@phtd.tpu.edu.ru>, Grigoriy Strokin >grg@isabase.philol.msu.ru<
Одна из наиболее важных задач по управлению данными --- это
приведение их в какой-нибудь осмысленный порядок. Perl предоставляет
довольно мощную операцию sort, которая обладает огромной
гибкостью. Я собираюсь поговорить о некоторых способах сортировки, и,
надеюсь, вы сможете сортировать что угодно, когда закончите чтение. (Нет,
несмотря на моё имя, я не буду говорить о ``случайной сортировке'').
Randal похоже на random -- произвольный, случайный (англ.). --- Прим. переводчика.
Давайте возьмём простой случай. Где-то в программе на Perl у меня есть список слов, и я хочу отсортировать их в алфавитном порядке (технически, в возрастающем порядке кодов ASCII
Случай не-латинского алфавита здесь не рассматривается. Он вообще редко рассматривается в англоязычной литературе. Смотрите документацию на locale. --- Прим. переводчика.). Это достаточно легко.
@somelist = ("Fred","Barney","Betty","Wilma");
@sortedlist = sort @somelist;
Здесь мы помещаем значение (``Barney'',``Betty'',``Fred'',
``Wilma'') в @sortedlist. Если бы эти имена были в файле, я
мог бы прочитать их оттуда:
#!/usr/bin/perl
@somelist = <>; # read everything
@sortedlist = sort @somelist;
print @sortedlist;
В этом случае @somelist (и @sortedlist тоже) также
будут иметь символы новой строки в конце каждого имени. Это нормально,
поскольку никак не влияет на порядок сортировки, и делает печать намного
легче.
Конечно, это можно немного сократить:
#!/usr/bin/perl
@somelist = <>;
print sort @somelist;
И даже больше:
#!/usr/bin/perl
print sort <>;
(Я полагаю, это как раз то, что придаёт Perl репутацию нечитабельного языка). Как вы видите, здесь я вообще не использую переменных. Тем не менее, это на самом деле делает сортировку того, что читается, и печатает результат.
Такие виды сортировки хороши для текстовых данных. Однако если данные
цифровые, мы получим неправильный порядок: сравнение чисел 15 и 3 как строк
поставит 3 после 15, а не наоборот. Поскольку по умолчанию sort
сравнивает строки как текстовые, нам необходимо каким-либо образом сказать
sort делать вместо текстовой сортировки числовую.
Для всех видов данных, кроме текстовых, необходимо использовать ``подпрограмму сортировки''. Это работает просто --- в момент, когда Perl смотрит на два элемента из списка, пытаясь выяснить как упорядочить элементы, ему необходимо выполнить некоторого рода сравнение. По умолчанию, это обычное сравнение строк ASCII. Однако вы можете задать свою функцию сравнения элементов, используя подпрограмму сортировки, при выполнении которой будут действовать следующие соглашения:
$a и
$b. (Нет нужды делать их локальными или смотреть на
@_).$a и $b в
подпрограмме сортировки, и решить, которое из них больше.$a ``меньше чем'', ``равно'' или ``больше чем''
$b, используя свою операцию сравнения.Те, кто знаком с функцией qsort из библиотеки языка C, должны
быть знакомы с такой подпрограммой. На самом деле, Perl использует именно
функцию qsort, так что ничего удивительного.
Таким образом, подпрограмма сортировки, которая делает числовое, а не текстовое сравнение, выглядит так:
sub numerically {
if ($a < $b) { -1; }
elsif ($a == $b) { 0; }
else { +1; }
}
Теперь всё, что мы должны сделать --- это сказать Perl использовать
как функцию сравнения эту подпрограмму сортировки, а не встроенную
сортировку в ASCII-порядке. Это делается помещением имени подпрограммы (без
стоящего впереди амперсанда) между ключевым словом ``sort'' и
сортируемым списком. Например:
@newlist = sort numerically 32,1,4,8,16,2;
Так вместо списка, отсортированного в порядке ASCII (как это было бы,
если бы я не поставил слово ``numerically'') я получаю правильную числовую
последовательность степеней двойки в @newlist.
Численное сравнение $a и $b возвращающее в результате
-1, 0, или +1, выполняется так часто, что Ларри Уол (Larry Wall) решил, что
оно заслуживает своего собственного оператора ``<=>'', который стал
известен как ``космический корабль'' по причинам, которые я не стал бы
обсуждать. Таким образом, я могу сократить ``numeracally'' следующим
образом:
sub numerically {
$a <=> $b;
}
Теперь это настолько коротко, что кажется лишним определять отдельную
процедуру, и на самом деле, Perl позволяет ещё более компактную запись:
подставить фрагмент кода, ответственный за сортировку, в вызов функции
sort, подобно такому:
@newlist = sort { $a <=> $b; } @oldlist;
Взаимодействие с этим сортирующим блоком в точности такое же, как я описал с подпрограммой раньше. Просто такая запись немного компактнее. Лично я использую этот стиль для сортировочных подпрограмм не длиннее 40 символов и создаю нормальную подпрограмму для больших.
Давайте снова посмотрим на чтение списка чисел со стандартного ввода:
#!/usr/bin/perl
print sort numerically <>;
sub numerically { $a <=> $b; }
Теперь, если я передам этой программе список чисел, то я получу отсортированный список чисел. Эта функциональность эквивалентна команде UNIX ``sort'' с ключом ``-n''.
Рассмотрим более интересный пример. Предположим, что у меня есть файл с именами в первой колонке и количеством очков, набранных при игре в боулинг, во второй:
Fred 210
Barney 195
Betty 200
Wilma 170
Dino 30
и я хочу отсортировать этот список по количеству очков. Получить данные в программе довольно просто:
#!/usr/bin/perl
@data = <>;
но каждый элемент @data выглядит как ``Fred 210\n'', и тому
подобное. Как мне отсортировать список @data, но глядя только на
число, а не на имя?
Пожалуй, я бы выделил число из строки. Как я это сделаю? Один из способов --- разбить строку с помощью ``split'':
$a = "Fred 210\n";
($name,$score) = split /\s+/, $a;
Здесь я разбиваю $a по пробелам, получая список список из двух
элементов. Первый элемент попадает в $name (который нас не
интересует, на самом деле), второй элемент попадает в $score. Вот
теперь всё, что мне надо, --- это сказать Perl смотреть только на
количество очков:
sub scores {
($name_a,$score_a) = split /\s+/, $a;
($name_b,$score_b) = split /\s+/, $b;
$score_a <=> $score_b;
}
и, на самом деле, это именно так и работает!
#!/usr/bin/perl
sub scores { ... } # as above
print sort scores <>;
Так, что неправильно в этой картине? Было бы здорово, если бы мы смотрели на каждый элемент списка только один раз. Тем более, после того, как мы сравним счёт Fred'а и счёт Barney (и решим, что Fred лучше), нам так же придётся сравнивать счёт Fred'а со счётом Betty. Это значит, что данные о Fred'e нам придётся разбивать дважды. А для огромного списка нам придётся выполнять одно и то же разбиение снова и снова.
Есть несколько способов этого избежать. Один из них, это создать отдельный массив, который содержит только количество очков, и затем сортировать этот массив. Давайте посмотрим сначала на этот способ.
Наша цель сначала прочитать данные, затем создать ассоциативный массив, чьи ключи представляют отдельный элемент массива, а значения представляют количество очков. Затем мы упростим задачу до поиска в ассоциативном массиве вместо (возможного) лишнего разбиения строки.
@data = <>; # read data
foreach (@data) {
($name,$score) = split; # get score
$score{$_} = $score; # record it
}
Теперь значением $score{``Fred 210\n''} будет 210, и так далее,
для каждого элемента массива @data.
Далее мы должны использовать эту информацию. Для этого нам нужна
подпрограмма, которой будут передаваться два элемента из @data в
переменных $a и $b. Подпрограмма находит соответствующие
значения в \%score и численно их сравнивает:
sub score {
$score{$a} <=> $score{$b};
}
и она на самом деле делает это. Давайте сложим эти кусочки вместе:
#!/usr/bin/perl
@data = <>; # read data
foreach (@data) {
($name,$score) = split; # get score
$score{$_} = $score; # record it
}
print sort {
$score{$a} <=> $score{$b};
} @data;
Заметьте, что в этой версии я вписал подпрограмму сортировки как блок в строке sort. (Я просто пытался дать вам побольше альтернативных форм записи).
Другой способ подойти к проблеме --- это сжать список в список пар. Второй элемент каждой пары (в действительности, анонимный список из двух элементов) будет ключом сортировки, а первый будет оригинальным значением (так мы всегда сможем вернуться к оригинальным данным). Это лучше всего делается с помощью оператора ``map'' (в старых версиях Perl отсутствует).
@pairs = map {
($name, $score) = split;
[ $_, $score ];
} @data;
Здесь блок программы выполняется для каждого элемента массива
@data с $_, установленным на элемент. Это приводит к
тому, что элемент разбивается на $name и $score, и затем
я строю двух-элементный анонимный список из $score и оригинального
значения $_. Эти анонимные массивы собираются в новый список. Если
@data имеет пять элементов, тогда @pairs имеет тоже пять
элементов, каждый из которых является ссылкой на двух-элементный анонимный
список. Ох!
Следующим шагом отсортируем список @pairs. Внутри подпрограммы
сортировки $a и $b будут ссылками на двух-элементные
списки. Второй элемент каждого списка --- это ключ для сортировки, и
адресуется как $a->[1]. Таким образом, мы получаем подпрограмму
сортировки:
sub mangle {
$a->[1] <=> $b->[1];
}
и сортировка выглядит так:
@sorted = sort mangle @pairs;
Теперь @sorted является таким же списком пар данных, как
@pairs, но отсортированных по количеству очков (вы ещё не забыли,
что мы работаем с очками?). Мне придётся убрать анонимный список, чтобы
получить назад оригинальные данные, но сохраняя порядок. Это легко,
map спасёт нас снова:
@finally = map {
$_->[0];
} @sorted;
Это потому, что $_ будет равен каждому элементу
@sorted --- ссылке на анонимный список, и поэтому,
$->[0] будет доставать первый элемент анонимного списка,
указанного в $_, который является оригинальными данными. Вот так
вот!
Конечно, если использовать традиционный для Perl стиль, то я могу
склеить это вместе таким образом, что все будет очень похоже
наLISP. Чтобы понять, что происходит, вам нужно будет прочитать
этот фрагмент задом наперед:
#!/usr/bin/perl
print
map { $_->[0] }
sort { $a->[1] <=> $b->[1] }
map {
($name,$score) = split;
[$_,$score];
} <>;
Ого. Однако это работает!
И последняя оптимизация: Я могу поставить разбиение строки прямо внутри создания списка:
#!/usr/bin/perl
print
map { $_->[0] }
sort { $a->[1] <=> $b->[1] }
map { [$_, (split)[1] ] }
<>;
это работает потому, что split делит строку $_ на
``текстовые части'' --- только второй элемент списка остаётся после
того, как мы его вырежем.
Perl предоставляет несколько мощных методов сортировки, которые могут быть действительно удобны после того, как вы хорошо их освоите. Я надеюсь, что я вас больше вдохновил, чем смутил. В следующий раз я расскажу про что-нибудь другое.