CGI & Perl - PERL - Полезные советы: Сортировка

PERL - Полезные советы

Сортировка

Попробуем отсортировать по возрастанию числа от 1 до 10. sort 1..10 дает нам результ ('1', '10', '2', '3', '4', '5', '6', '7', '8', '9'). Немного не то... Сортировка сработала как расстановка по алфавиту. Проблему можно решить с помощью оператора <=>.


        @sorted_num = sort { $a <=> $b } 1..10;  # То, что мы ожидали

        # другой вариант этого же кода
        sub numerically { $a <=> $b }
        @sorted_num = sort numerically 1..10;

По умолчанию функция сортировки sort выполняет расстановку по алфавиту (сортировка в контексте символьных строк). Таким образом '10' и '100' появятся перед '2' и '3'. Чтобы изменить способ сортировки в данном случае мы применили собственный оператор сравнения двух переменных (блок сортировки).

Автор: Joseph N. Hall

Сортировка одного массива в соответсвии с содержимым другого массива.
Нам надо отсортировать два "параллельных" массива (списка). Например массив @page состоит из номеров страниц, а @note состоит из примечаний к этим страницам, т.е. $note[$i] - это примечание к странице $page[$i]. Нам хочется напечатать оба массива, отсортировав их по номерам страниц.


        @page = qw(24 75 41 9);
        @note = qw(p.24-text p.75-text p.41-text p.9-text);
        for (sort { $note[$a] <=> $note[$b] } 0..$#note) {
                print "$page[$_]: $note[$_]\n";
        }

        # другой вариант
        @note_sorted = @note[sort { $page[$a] <=> $page[$b] } 0..$#page];

Автор: Joseph N. Hall

Сортировка по убыванию.
Надо просто поменять местами переменные $a и $b в блоке сравнения.


        print "descending: ",
                join(" ", sort { $b <=> $a } 3,4,1,5,9,7),
                "\n";

Автор: Joseph N. Hall

Сортировка ключей хэш-массива в порядке возрастаний их значений.
Имеем хэш-массив, состоящий из слов книги и количеством повторений этих слов. Нам надо напечатать этот массив в порядке убывания частоты слова.


        # Считываем слова
        while (<>) {
                for (split) {
                        $count{$_}++;
                }
        }

        # Теперь выводим список слов и количество повторений
        for (sort { $count{$b} <=> $count{$a} } keys %count) {
                print "$_: $count{$_}\n";
        }

Автор: Joseph N. Hall

Сортировка имен файлов по дате/времени изменения.


        @newest_first = sort { -M $a <=> -M $b } <*>;

Оператор -М возвращает дату/время изменения файла в виде числа с плавающей точкой. Проблема состоит в том, что оператор -М выполняется очень медленно и на больших списках файлов операция сортировки может занять очень много времени. Для сортировки n файлов блок сравнения будет вызван примерно n log n раз. Для решения этой проблемы смотрите пример сортировки Шварца.

Автор: Joseph N. Hall

Сортировка величин, время сравнения которых сравнительно велико.
Например, нам надо отсортировать файлы по времени последнего изменения, но оператор -М (время последнего изменения файла) работает очень медленно.

Решить проблему можно с помощью сортировка Шварца (по имени Рандала Шварца Randal Schwartz).


        # Сортировка имен файлов по времени их последнего изменения
        @newest_first =
          map { $_->[0] }
          sort { $a->[1] <=> $b->[1] }
          map { [ $_, -M ] }
          <*>;

        # Общая форма. Сортировка по одному ключу
        @sorted =
          map { $_ ->[0] }
          sort { $a->[1] %%compare-op%% $b->[1] }
          map { [ $_, %%transform-func%% ] }
          @input;

        # Общая форма. Сортировка по двум ключам
        @sorted =
          map { $_ ->[0] }
          sort { $a->[1] %%compare-op1%% $b->[1] or
                 $a->[2] %%compare-op2%% $b->[2] }
          map { [ $_, %%transform-func1%%, %%transform-func2%% ] }
          @input;

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

Автор: Joseph N. Hall

Сортировка строк по полям, разделенным символом.
Например, хочу отсортировать строки, разделенные на поля запятой, сначала по второму полю по числам, затем по первому полю по алфавиту в порядке убывания.


        sub fieldsort {
            my ($sep, $cols);
            if (ref $_[0]) {
                $sep = '\\s+'
            } else {
                $sep = shift;
            }
            unless (ref($cols = shift) eq 'ARRAY') {
                die "fieldsort columns must be in anon array";
            }
            my (@sortcode, @col);
            my $col = 1;
            for (@$cols) {
                my ($a, $b) = /^-/ ? qw(b a) : qw(a b);
                my $op = /n$/ ? '<=>' : 'cmp';
                push @col, (/(\d+)/)[0] - 1;
                push @sortcode, "\$${a}->[$col] $op \$${b}->[$col]";
                $col++;
            }
            my $sortfunc = eval "sub { " . join (" or ", @sortcode) . " } ";
            my $splitfunc = eval 'sub { (split /$sep/o, $_)[@col] } ';
            return
                map $_->[0],
                sort { $sortfunc->() }
                map [$_, $splitfunc->($_)],
                @_;
        }

        #Примеры:

        # Как сказано выше
        @sorted = fieldsort ':', ['2n', -1], @data;

        # по 2-му затем по 1-му полю, по алфавиту, разделены пробелами
        @sorted = fieldsort [2, 1], @data;

        # по 1-му полю по числам в порядке убывания, затем по 3-му полю
        # по алфавиту и по 2-му по числам, поля разделены '+'
        @sorted = fieldsort '+', ['-1n', 3, 2], @data;

На самом деле большая часть приведенного выше кода - это препроцессор, который готовит данные для дальнейшей сортировки Шварца.

Автор: Joseph N. Hall