[Перевод] .sort'ировка в Perl 6
Сортировка списков – очень распространённая задача в программировании, и в Perl 6 есть несколько улучшений функции sort, помогающих вам решить такую задачу.
В языке есть обыкновенный типичный sort:
# сортировка по умолчанию с учётом типа
my @sorted = @unsorted.sort; # или sort @unsorted;
Как и в Perl 5, можно настраивать функцию для сравнения:
# численное сравнение
my @sorted = @unsorted.sort: { $^a <=> $^b };
# то же, с использованием функциональной семантики
my @sorted = sort { $^a <=> $^b }, @unsorted;
# строковое сравнение ( как cmp в Perl 5 )
my @sorted = @unsorted.sort: { $^a leg $^b };
# сравнение с учётом типа
my @sorted = @unsorted.sort: { $^a cmp $^b };
Если записать условие сравнения в скобках, тогда вам не понадобится двоеточие. Это удобно, когда вы хотите выстроить цепочку из других методов, тянущуюся за sort:
my @topten = @scores.sort( { $^b <=> $^a } ).list.munch(10);
Уточнение: в Perl 6 у переменных $a и $b нет особого назначения, как в Perl 5. В блоке сравнения сортировки, как и в любом другом блоке, можно использовать обычные переменные ($var), позиционные ($^var) или «whatever» (*).
Во время сортировки можно сразу применять преобразующую функцию:
my @sorted = @unsorted.sort: { foo($^a) cmp foo($^b) };
но для каждой итерации foo() подсчитывается заново. Для мелких списков это не страшно, но для крупных это становится проблемой, особенно, если эта функция тяжёлая по вычислениям.
В Perl 5 типичным является использование преобразования Шварца, когда вам необходимо упорядочить список не по элементам, а по некоторым производным от них.
При использовании преобразования Шварца, каждое преобразование подсчитывается один раз, затем элементы сортируются по результатам преобразования, а затем из этого списка берутся изначальные элементы.
Предположим, что необходимо отсортировать список слов («aaaa», «a», «aa») по длине слов. Сначала необходимо создать список ([«aaaa»,4], [«a»,1], [«aa»,2]), затем отсортировать его по числовому значению, а потом из полученного списка ([«a»,1], [«aa»,2], [«aaaa»,4]) удалить числа. В результате будет получен список («a», «aa», «aaaa»).
# Код для Perl 5
@sorted =
map { $_->[0] }
sort { $a->[1] cmp $b->[1] }
map { [$_, foo($_)] }
@unsorted;
В Perl 6 его тоже можно делать, но кроме того, в sort встроены некоторые интеллектуальные алгоритмы. Если у вашей функции число операндов 0 или 1, Perl 6 примечает это и автоматически добавляет преобразование Шварца.
Взглянем на примеры.
Сортировка без учёта регистра
Привести каждый элемент к нижнему регистру, отсортировать, и вернуть оригинальные элементы.
my @sorted = @unsorted.sort: { .lc };
Простота.
Сортировка по длине слова
Упорядочить список строк по количеству символов, от коротких к длинным.
my @sorted = @unsorted.sort: { .chars };
Or longest to shortest:
my @sorted = @unsorted.sort: { -.chars };
Множественные компараторы в сортировке
В блок sort можно передать несколько функций для сравнения и он выполнит столько преобразований, сколько нужно для достижения первого результата неравенства.
Сортировка по длине слов, при этом есть вторичная сортировка, которая сортирует слова с одинаковой длиной по порядку символов ASCII.
.say for @a.sort: { $^a.chars, $^a } ;
Сортировка в Perl 6 стабильна, поэтому можно отсортировать список по порядку ASCII, а затем – по длине слов.
.say for @a.sort.sort: { $^a.chars };
Работает – но так оно сортируется дважды. Можно переписать это следующим образом:
.say for @a.sort: { $^a.chars <=> $^b.chars || $^a leg $^b };
Тоже работает, но теперь потеряна автоматическое преобразование Шварца.
Или можно применить естественное сортирующее преобразование:
.say for @a.sort: { $^a.&naturally, $^a };
«Что-то? Естественная сортировка? Это ещё откуда взялось?». Рад, что вы спросили.
Естественная сортировка
Стандартная сортировка по строка выдает результат в «ASCIIвитном» прядке. Цифры перед прописными буквами, а затем строчные. Люди часто удивляются, получив в результате сортировки следующее:
0
1
100
11
144th
2
21
210
3rd
33rd
AND
ARE
An
Bit
Can
and
by
car
d1
d10
d2
И это, конечно, корректно, но не совсем интуитивно, особенно для не-программистов. Естественная сортировка упорядочила бы список по возрастанию чисел, а затем по алфавиту.
Вот те же строки, отсортированные естественно:
0
1
2
3rd
11
21
33rd
100
144th
210
An
AND
and
ARE
Bit
by
Can
car
d1
d2
d10
Для этого нужно выполнить простое преобразование. Я буду использовать метод subst. Это аналог оператора s/// в виде метода.
.subst(/(\d+)/, -> $/ { 0 ~ $0.chars.chr ~ $0 }, :g)
Сначала мы «ловим» группу из одного или нескольких последовательных цифр. Конструкция ‘ -> $/ { … } ‘ – это «блок с остриями». Она означает «выдать содержимое массива найденных совпадений ($/) в область видимости следующего блока кода ( {…} )». Блок строит строку замены: «0», к которому присоединяется количество цифр в числе, выраженное как символ ASCII, после которого уже присоединяется сама строка из цифр. Приставка :g означает «глобально».
И ещё нам нужно сортировать нечувствительно к регистру, поэтому мы пристегнём ещё метод .lc, и получим в результате:
.lc.subst(/(\d+)/, -> $/ { 0 ~ $0.chars.chr ~ $0 }, :g)
Превращаем это в функцию:
sub naturally ($a) {
$a.lc.subst(/(\d+)/, -> $/ { 0 ~ $0.chars.chr ~ $0 }, :g)
}
Работает почти правильно, но не совсем. Величины, замэпленные в одно преобразование, вернутся в том порядке, в котором поступали. Например, слова ‘THE’, ‘The’ и ‘the’ вернутся в порядке поступления, а не в порядке сортировки. Проще всего будет добавить оригинальную величину в хвост преображённой.
Итого, финальная функция естественной сортировки будет такой:
sub naturally ($a) {
$a.lc.subst(/(\d+)/, -> $/ { 0 ~ $0.chars.chr ~ $0 }, :g) ~ "\x0" ~ $a
}
Поскольку она работает с величинами по очереди, мы ещё получаем бесплатно преобразование Шварца. Теперь его можно использовать в качестве модификатора сортировки.
.say for <0 1 100 11 144th 2 21 210 3rd 33rd AND ARE An Bit Can and by car d1 d10 d2>.sort: { .&naturally };
Или отсортировать ip адреса:
# сортируем список ip
my @ips = ((0..255).roll(4).join('.')for 0..99);
.say for @ips.sort: { .&naturally };
4.108.172.65
5.149.121.70
10.24.201.53
11.10.90.219
12.83.84.206
12.124.106.41
12.162.149.98
14.203.88.93
16.18.0.178
17.68.226.104
21.201.181.225
23.61.166.202
23.205.73.104
24.250.90.75
35.56.124.120
36.158.70.141
40.149.118.209
40.238.169.146
52.107.62.129
55.119.95.120
56.39.105.245
... и так далее
Или сортировать список файлов, или что угодно, что содержит смесь из цифр и символов.
