Преобразование Шварца

Преобразование Шварца (Schwartzian transform) — перловая идиома для ускорения сортировки массива при условии, что условие сортировки требует выполнение достаточно дорогого кода. По сути идея в том, чтобы заранее вычислить «ключ» сортировки для каждого элемента массива и потом отсортировать по этому ключу. Представляет собой разновидность кеширования или мемоизации.

Пишу здесь потому, что по-русски в вики про него страницы нет.

Сама идеома:

@sorted = map  { $_->[0] }
          sort { $a->[1] cmp $b->[1] }
          map  { [$_, foo($_)] }
               @unsorted;

Смысл: сперва каждый элемент неотсортированного массива с помощью map дополняется вычисленным значением ключа сортировки (функцией foo()), при этом используются анонимные двухэлементные массивы для сохранения и исходного значения элементов массива, и вычисленного ключа. Затем происходит собственно сортировка по вычисленным ключам, а в конце идёт «развёртка» анонимных массивов. Т.к. после последней операции ссылок на временные анонимные массивы не остаётся, то они сразу (ну или почти сразу) попадают в руки сборщика мусора, так что памяти используется не так много, как если бы мы использовали дополнительный временный массив для хранения вычисленных значений ключей сортировки. То есть использоваться-то памяти будет примерно столько же, но освобождаться она будет очень быстро.

Пример: сортировка списка файлов по их времени модификации. Если сортировать сразу, без этой идиомы, то будет сделана куча вызовов stat для каждого элемента массива, т.к. число сравнений изначально неизвестно. С использованием идиомы дорогая операция stat будет гарантированно вызвана единственный раз для каждого имени файла из массива, а сортировка будет проводиться с простым и быстрым сравнением целых чисел (unix timestamp'ов в данном случае).