Perl Language
Сортировка

Вступление

Синтаксис

• сортировать SUBNAME LIST
• сортировать БЛОК-СПИСОК
• сортировать СПИСОК

Базовая лексическая сортировка

@sorted = sort @list;

@sorted = sort { $a cmp $b } @list;

sub compare { $a cmp $b }
@sorted = sort compare @list;

Три приведенных выше примера делают то же самое. Если вы не предоставляете какую-либо функцию или блок-компаратор, sort предполагает, что вы хотите, чтобы список был правильно отсортирован лексически. Обычно это форма, которую вы хотите, если вам просто нужны ваши данные в определенном предсказуемом порядке и не заботятся о лингвистической правильности.

sort проходит пар элементов в @list к функции компаратора, который говорит sort , какой элемент больше. Оператор cmp делает это для строк, а <=> делает то же самое для чисел. Сравнитель вызывается довольно часто, в среднем n * log ( n ) раз, когда n - это количество элементов для сортировки, поэтому важно быстро. В этом случае sort использует предопределенные глобальные переменные пакета ( $a и $b ) для передачи элементов, которые будут сравниваться с блоком или функцией, вместо правильных параметров функции.

Если вы use locale , cmp учитывает специфический порядок сортировки по языку, например, он будет сортировать Å подобно A в датском языке, но после Z под английским или немецким. Однако он не учитывает более сложные правила сортировки Юникода и не обеспечивает какого-либо контроля над заказом - например, телефонные книги часто сортируются иначе, чем словари. В этих случаях рекомендуется использовать Unicode::Collate и особенно Unicode::Collate::Locale .

Числовая сортировка

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

Сравнение $a и $b с оператором <=> гарантирует, что они сравниваются численно, а не текстовыми по умолчанию.

Обратная сортировка

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

Сортировка элементов в порядке убывания может быть просто достигнута путем замены $a и $b в блоке компаратора. Тем не менее, некоторые люди предпочитают четкость отдельного reverse даже если он немного медленнее.

Трансформация Шварца

Это, пожалуй, самый известный пример оптимизации сортировки с использованием возможностей программирования Perl, которые будут использоваться там, где порядок сортировки элементов зависит от дорогостоящей функции.

# What you would usually do
@sorted = sort { slow($a) <=> slow($b) } @list;

# What you do to make it faster
@sorted =
map { $_->[0] }
sort { $a->[1] <=> $b->[1] }
map { [ $_, slow($_) ] }
@list;

Проблема с первым примером заключается в том, что компаратор вызывается очень часто и продолжает пересчитывать значения, используя медленную функцию снова и снова. Типичным примером будет сортировка имен файлов по их размеру файла:

use File::stat;
@sorted = sort { stat($a)->size <=> stat($b)->size } glob "*";

Это работает, но в лучшем случае это наносит накладные расходы на два системных вызова за сравнение, а в худшем случае приходится дважды переходить на диск для каждого отдельного сравнения, и этот диск может находиться в перегруженном файловом сервере с другой стороны планета.

Введите трюк Рэндалла Шварца.

@list преобразование в основном @list через три функции, снизу вверх. Первая map превращает каждую запись в двухэлементный список исходного элемента, а результат медленной функции - в качестве ключа сортировки, поэтому в конце этого мы называем slow() ровно один раз для каждого элемента. Следующий sort может затем просто открыть ключ сортировки, просмотрев список. Поскольку нам не нужны ключи сортировки, но нужны только исходные элементы в отсортированном порядке, окончательная map выбрасывает списки из двух элементов из уже отсортированного списка, который он получает от @sort и возвращает список только своих первых членов ,

Нечувствительный к регистру сортировка

Традиционная техника для выполнения sort игнорирует регистр строк lc или uc для сравнения:

@sorted = sort { lc($a) cmp lc($b) } @list;

Это работает во всех версиях Perl 5 и вполне достаточно для английского языка; неважно, используете ли вы uc или lc . Тем не менее, это представляет проблему для таких языков, как греческий или турецкий, где нет соответствия 1: 1 между буквами верхнего и нижнего регистра, чтобы вы получали разные результаты в зависимости от того, используете ли вы uc или lc . Поэтому Perl 5.16 и выше имеют функцию фальцовки fc , называемую fc которая позволяет избежать этой проблемы, поэтому современная многоязычная сортировка должна использовать это:

@sorted = sort { fc($a) cmp fc($b) } @list;