Сортировка списка файлов по именам, записанным в ASCII, работает очень быстро, даже для длинных списков.
Но если вам нужно отсортировать файлы по размеру, то эта операция может выполняться гораздо медленнее.
Сортировка файлов по именам
В этом примере создаётся список файлов в формате XML, а затем выполняется их сортировка по их именам. В этом случае сортировка работает быстро.
#!/usr/bin/perl
use strict;
use warnings;
my @files = glob "*.xml";
my @sorted_files = sort @files;
Сортировка файлов по длине имён
my @sorted_length = sort { length($a) <=> length($b) } @files;
Для списка из 3000 файлов данная операция выполнится примерно в три раза медленнее, чем сортировка по именам файлов (по ASCII), но всё ещё достаточно быстро.
Сортировка файлов по размеру
Если попытаться отсортировать тот же список из 3000 файлов по их размеру, то такая операция будет в 80 (!) раз медленнее сортировки по ASCII-именам.
my @sort_size = sort { -s $a <=> -s $b } @files;
Это, конечно, неудивительно. В первом примере Perl сравнивает значения. Во втором примере перед сравнением строк Perl вычисляет их длину. В третьем примере для каждого сравнения необходимо обратиться к жёсткому диску, чтобы получить размер сравниваемых файлов.
Время доступа к жёсткому диску значительно превышает время доступа к оперативной памяти. Этим и объясняется столь значительное отличие во времени сортировки.
Зададимся вопросом: а можно ли улучшить это время сортировки?
Значительное время сортировки в третьем примере также является следствием того, как работает сортировка в Perl.
Есть различные алгоритмы сортировки (быстрая сортировка, сортировка пузырьком, сортировка слиянием и т. д.). Время работы того или иного алгоритма зависит от входных данных. Раньше в Perl использовалась быстрая сортировка (Perl 5.6 и более ранние версии), затем перешли на сортировку слиянием (Perl 5.8 и более поздние версии). В современном Perl, если вы хотите, вы можете указать метод сортировки с помощью прагмы sort.
Независимо от того, какой алгоритм вы выберете, в среднем будет использоваться не менее N*log(N) сравнений. Это означает, что для списка из 1000 файлов Perl необходимо получить доступ к диску 2 * 1000 * 3 = 6000 раз (дважды для каждого сравнения). Для каждого файла Perl будет получать его размер 6 раз! Это очень разорительно.
Мы не можем сократить количество сравнений, но можем сократить количество обращений к жёсткому диску.
Предварительное получение размера
Давайте получим размеры всех файлов и сохраним их в памяти, а затем выполним сортировку данных, которые уже находятся в памяти.
my @unsorted_pairs = map { [$_, -s $_] } @files;
my @sorted_pairs = sort { $a->[1] <=> $b->[1] } @unsorted_pairs;
my @quickly_sorted_files = map { $_->[0] } @sorted_pairs;
Когда вы будете использовать этот алгоритм, он может быть записан несколько сложнее.
Алгоритм состоит из трёх шагов. На первом шаге мы проходим по списку файлов и для каждого файла создаём ссылку на массив. В этом массиве находится два элемента. Первый - имя файла, второй - размер файла. Количество обращений к диску будет равняться количеству файлов.
На втором шаге мы сортируем массив, состоящий из двухэлементных массивов, созданных на первом шаге. При сравнении мы сравниваем вторые элементы массивов (в них хранятся размеры сравниваемых файлов). Результатом данной операции будет являться список отсортированных пар (имя файла/размер файла).
На третьем шаге мы выкидываем размеры файлов и оставляем только их имена.
Преобразование Шварца
В примере выше нам потребовались два временных массива, которые в принципе можно и не создавать. Мы можем свернуть код в одну компактную конструкцию. Для этого нужно переписать логику конструкций в обратном порядке. Чтобы улучшить читабельность, каждое утверждение запишем на отдельной строке и используем отступы для фигурных скобок.
my @quickly_sorted_files =
map { $_->[0] }
sort { $a->[1] <=> $b->[1] }
map { [$_, -s $_] }
@files;
Эта конструкция называется преобразованием Шварца, названной так в честь Рэндела Шварца.
Если вы видите в коде конструкции типа mar-sort-map, то скорее всего вы имеете дело с преобразованием Шварца.
С помощью преобразования Шварца можно сортировать что угодно, но оно особенно полезно при высоких накладных расходах при сравнении значений.
my @sorted =
map { $_->[0] }
sort { $a->[1] <=> $b->[1] }
map { [$_, f($_)] }
@unsorted;
Используя этот алгоритм, сортировка списка из 3000 XML-файлов выполняется медленнее, чем сортировка списка ASCII-имён, "только" в 10 раз, т. е. этот код работает в 8 раз быстрее, чем тот, который мы использовали в самом начале.
Выводы
За скорость приходится расплачиваться памятью и усложнением кода. Увеличение расходов памяти может проявить себя только при работе с большими массивами.
Если сортировка занимает 1 секунду от общего времени исполнения сценария, которое составляет 10 минут, то в оптимизации сортировки нет практического смысла. Но если сортировка занимает значительную часть времени, то можно воспользоваться преобразование Шварца.
Чтобы определить целесообразность преобразования Шварца, используйте профилировку кода с помощью Devel::NYTProf.
