Perl Language
Сортировка
Поиск…
Вступление
Для сортировки списков вещей Perl имеет только одну функцию, неудивительно называемую sort
. Он достаточно гибкий, чтобы сортировать все виды элементов: числа, строки в любом количестве кодировок, вложенных структур данных или объектов. Однако из-за его гибкости существует множество трюков и идиом, которые нужно изучить для его использования.
Синтаксис
- сортировать 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;