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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Преобразование Шварца — идиома, появившаяся в языке программирования 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;