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

Преобразова́ние Шва́рца — идиома, появившаяся в языке программирования Perl, которая решает задачу эффективной сортировки списков элементов по сложным (вычисляемым) атрибутам.

Идея состоит в том, чтобы сравниваемые вычисляемые атрибуты элементов (например, длина строки, часть строки, квадрат числа, прочие формулы и внешние запросы) вычислить один раз для всех элементов и занести во временный массив, который затем сортируется стандартной функцией сортировки по этим результатам, после чего временные данные отбрасываются. По сути, это кэширование (временное запоминание) вычисляемых атрибутов, поскольку в процессе сортировки они используются многократно (при сравнениях элементов). В языке Perl, благодаря использованию «переменной по умолчанию», этот алгоритм умещается в одно выражение из трёх функций, то есть очень кратко и наглядно.

Идиома получила своё название в честь Рэндела Шварца, который продемонстрировал её спустя некоторое время после выхода Perl 5 в 1994 году. Термин «преобразование Шварца» долгие годы использовался исключительно для языка программирования Perl, но позже это преобразование было адаптировано другими программистами и для других языков (например, Python). Алгоритм, используемый в преобразовании Шварца, существовал в некоторых языках программирования (не имея специального названия) ещё до того, как он был популяризирован в сообществе Perl-программистов в качестве идиомы.

Пример

Предположим, что необходимо отсортировать список слов («aaaa», «a», «aa») по длине слов. Сначала необходимо создать список ([«aaaa»,4], [«a»,1], [«aa»,2]), затем отсортировать его по числовому значению, а потом из полученного списка ([«a»,1], [«aa»,2], [«aaaa»,4]) удалить числа. В результате будет получен список («a», «aa», «aaaa»). Описанный алгоритм записывается в виде преобразования Шварца следующим образом:

@sorted = map  { $_->[0] }
          sort { $a->[1] <=> $b->[1] } # численное сравнение
          map  { [$_, length($_)] }    # подсчёт длины строк
               @unsorted;