Perl Language
Sortowanie

Wprowadzenie

Składnia

• sortuj LISTĘ SUBNAME
• sortuj LISTĘ BLOKÓW
• sortuj LISTĘ

Podstawowy sort leksykalny

@sorted = sort @list;

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

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

Trzy powyższe przykłady robią dokładnie to samo. Jeśli nie podasz żadnej funkcji lub bloku komparatora, sort zakłada, że chcesz, aby lista po prawej stronie była posortowana leksykalnie. Jest to zwykle forma, której potrzebujesz, jeśli potrzebujesz danych w przewidywalnej kolejności i nie zależy ci na poprawności językowej.

sort przechodzi pary elementów w @list do funkcji komparatora, który opowiada sort , który element jest większy. Operator cmp robi to dla łańcuchów, podczas gdy <=> robi to samo dla liczb. Komparator jest wywoływany dość często, średnio n * log ( n ) razy, gdzie n jest liczbą elementów do posortowania, dlatego ważne jest, aby był szybki. Jest to powód, dla którego sort używa predefiniowanych zmiennych globalnych pakietu ( $a i $b ) do przekazania elementów do porównania z blokiem lub funkcją, zamiast odpowiednich parametrów funkcji.

Jeśli use locale cmp , cmp bierze pod uwagę porządek sortowania specyficzny dla ustawień regionalnych, np. Sortuje Å jak A pod duńskimi ustawieniami narodowymi, ale po Z pod językiem angielskim lub niemieckim. Jednak nie bierze pod uwagę bardziej złożonych reguł sortowania Unicode ani nie zapewnia żadnej kontroli nad kolejnością - na przykład książki telefoniczne są często sortowane inaczej niż w słownikach. W takich przypadkach zalecane są moduły Unicode::Collate a zwłaszcza Unicode::Collate::Locale .

Sortowanie numeryczne

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

Porównanie $a i $b z operatorem <=> zapewnia, że są one porównywane numerycznie, a nie tekstowo, jak domyślnie.

Odwróć sortowanie

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

Sortowanie elementów w kolejności malejącej można po prostu osiągnąć poprzez zamianę $a i $b w bloku komparatora. Jednak niektórzy wolą klarowność oddzielnego reverse mimo że jest on nieco wolniejszy.

Transformacja Schwartziana

Jest to prawdopodobnie najsłynniejszy przykład optymalizacji sortowania wykorzystującej funkcjonalne funkcje programowania Perla, do zastosowania, gdy kolejność sortowania przedmiotów zależy od drogiej funkcji.

# 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;

Problem z pierwszym przykładem polega na tym, że komparator jest wywoływany bardzo często i ciągle przelicza wartości za pomocą funkcji slow. Typowym przykładem może być sortowanie nazw plików według ich rozmiaru:

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

Działa to, ale w najlepszym wypadku powoduje obciążenie dwóch wywołań systemowych na porównanie, w najgorszym przypadku musi przejść na dysk dwa razy dla każdego porównania, a dysk może znajdować się w przeciążonym serwerze plików po drugiej stronie planeta.

Wejdź w trick Randalla Schwartza.

Transformacja Schwartziana przesuwa @list przez trzy funkcje, od dołu do góry. Pierwsza map zamienia każdy wpis w dwuelementową listę oryginalnego elementu i wynik funkcji slow jako klucza sortowania, więc na końcu tego wywołaliśmy slow() dokładnie raz dla każdego elementu. Następujące sort może wtedy po prostu uzyskać dostęp do klucza sortowania, przeglądając listę. Ponieważ nie dbamy o klucze sortowania, ale potrzebujemy tylko oryginalnych elementów w posortowanej kolejności, ostateczna map odrzuca listy dwuelementowe z już posortowanej listy otrzymanej z @sort i zwraca listę tylko ich pierwszych członków .

Sortowanie bez rozróżniania wielkości liter

Tradycyjną techniką sort ignorowania wielkości liter jest przekazywanie ciągów znaków do lc lub uc celu porównania:

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

Działa to na wszystkich wersjach Perla 5 i jest całkowicie wystarczające dla języka angielskiego; nie ma znaczenia, czy używasz uc czy lc . Stanowi to jednak problem w przypadku języków takich jak grecki lub turecki, w których nie ma zgodności 1: 1 między dużymi i małymi literami, dzięki czemu uzyskuje się różne wyniki w zależności od tego, czy używasz uc czy lc . Dlatego Perl 5.16 i wyższy mają funkcję składania spraw o nazwie fc która pozwala uniknąć tego problemu, dlatego nowoczesne sortowanie wielojęzyczne powinno używać tego:

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