.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
    ... и так далее

Или сортировать список файлов, или что угодно, что содержит смесь из цифр и символов.