Пример:

Листинг 3

# Сортировка чисел по убыванию

@sorted = sort {$b <=> $a} @unsorted;

В этом примере элементы списка сравниваются уже как числа. При каждом сравнении, для пары сравниваемых элементов создаются синонимы – локальные переменные $a и $b; выполняется блок {$b <=> $a}; по его результатам sort делает вывод – надо ли переставить элементы или следует сохранить прежний порядок. Как видите, в нашем случае сортировка выстроит числа, составляющие массив @unsorted по убыванию.

Для иллюстрации подхода, который я собираюсь описать, более подходит следующий пример, реализующий сортировку строк по алфавиту без учёта регистра:

Листинг 4

# Сортировка строк по алфавиту без учёта регистра (оптимизации нет)

@sorted = sort {uc($a) cmp uc($b)} @unsorted;

Здесь, выполняя каждое сравнение, мы преобразуем операнды cmp к верхнему регистру; uc – встроенная функция Perl[6]. Обратите внимание, мы не сохраняем результат работы uc. Вот тут-то и кроется возможность оптимизировать нашу работу.

Итак, блок {uc($a) cmp uc($b)} выполняется столько раз, сколько сравнений необходимо для сортировки. Функция uc вызывается дважды при каждом выполнении блока. Давайте оценим, сколько раз она выполнится.

Цифры оказываются весьма красноречивы. Для сортировки «случайного» (неупорядоченного) списка из 1000 строк понадобится в среднем 19 460 вызовов uc. То есть каждый элемент списка будет преобразован в верхний регистр почти двадцать раз! Для аналогичного списка из 1 000 000 строк Perl придётся вызывать uc 4 3180 000 раз, и каждый элемент будет преобразован более 43 раз. Конечно, такая трата вычислительных ресурсов совершенно не оправданна.

Для оптимизации быстродействия нам придётся пожертвовать памятью, но, к счастью, память сейчас не дорога, а вот время всегда – деньги.

Путь оптимизации очень прост, суть его такова:

Листинг 5

# Оптимизированная сортировка строк по алфавиту без учёта регистра; длинная форма с временными массивами