WikiSort.ru - Программирование

ПОИСК ПО САЙТУ | о проекте

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

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии