Преобразование Шварца
Идиома программирования для эффективной сортировки списка по вычисляемому ключу

В программировании преобразование Шварца — это метод, используемый для повышения эффективности сортировки списка элементов. Эта идиома [1] подходит для сортировки на основе сравнения , когда упорядочение фактически основано на упорядочении определенного свойства ( ключа ) элементов, где вычисление этого свойства — интенсивная операция, которая должна выполняться минимальное количество раз. Преобразование Шварца примечательно тем, что оно не использует именованные временные массивы.

Преобразование Шварца — это версия идиомы Lisp, известной как decorate-sort-undecorate , которая избегает повторного вычисления ключей сортировки, временно связывая их с входными элементами. Этот подход похож на memoization , который избегает повторного вычисления ключа, соответствующего определенному входному значению. Для сравнения, эта идиома гарантирует, что ключ каждого входного элемента вычисляется ровно один раз, что все равно может привести к повторению некоторых вычислений, если входные данные содержат повторяющиеся элементы.

Идиома названа в честь Рэндала Л. Шварца , который впервые продемонстрировал ее в 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"). Это был алгоритм в целом, поэтому он не считается преобразованием. Чтобы сделать это настоящим преобразованием Шварца, это будет сделано в Perl следующим образом:

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

Идиома Perl

Общая форма преобразования Шварца имеет вид:

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

Здесь foo($_)представлено выражение, которое берет $_(каждый элемент списка по очереди) и выдает соответствующее значение, которое должно сравниваться вместо него.

Читаем справа налево (или снизу вверх):

  • исходный список @unsortedпередается в mapоперацию, которая оборачивает каждый элемент в массив (ссылку на анонимный 2-элементный), состоящий из него самого и вычисленного значения, которое будет определять его порядок сортировки (список элементов становится списком [элемент, значение]);
  • затем список списков, созданный функцией, mapподается в sort, которая сортирует его в соответствии с ранее вычисленными значениями (список [элемент, значение] ⇒ отсортированный список [элемент, значение]);
  • наконец, другая mapоперация извлекает значения (из анонимного массива), используемые для сортировки, создавая элементы исходного списка в отсортированном порядке (отсортированный список [элемент, значение] ⇒ отсортированный список элементов).

Использование анонимных массивов гарантирует, что память будет освобождена сборщиком мусора Perl сразу после завершения сортировки.

Анализ эффективности

Без преобразования Шварца сортировка в приведенном выше примере была бы записана на Perl следующим образом:

@sorted = sort { foo ( $a ) cmp foo ( $b ) } @unsorted ;

Хотя код короче, наивный подход здесь может быть гораздо менее эффективным, если функция ключа (называемая foo в примере выше) требует больших вычислительных затрат. Это связано с тем, что код внутри скобок оценивается каждый раз, когда необходимо сравнить два элемента. Оптимальная сортировка сравнением выполняет O ( n log n ) сравнений (где n — длина списка) с 2 вызовами foo на каждое сравнение, что приводит к O ( n log n ) вызовам foo . Для сравнения, используя преобразование Шварца, мы делаем только 1 вызов foo на элемент на начальном этапе отображения , что в общей сложности дает n вызовов foo .

Однако если функция foo относительно проста, то дополнительные накладные расходы на преобразование Шварца могут оказаться неоправданными.

Пример

Например, чтобы отсортировать список файлов по времени их изменения , наивный подход может быть следующим:

 функция naiveCompare(файл a, файл b) { return modificationTime(a) < modificationTime(b) }  // Предположим, что sort(list, comparisonPredicate) сортирует заданный список, используя  // comparisonPredicate для сравнения двух элементов. sortedArray := sort(filesArray, naiveCompare)

Если время модификации не запоминается для каждого файла, этот метод требует повторного вычисления его каждый раз, когда файл сравнивается в сортировке. Используя преобразование Шварца, время модификации вычисляется только один раз для каждого файла.

Преобразование Шварца включает в себя функциональную идиому, описанную выше, которая не использует временные массивы.

Тот же алгоритм можно записать процедурно, чтобы лучше проиллюстрировать, как он работает, но это требует использования временных массивов и не является преобразованием Шварца. Следующий пример псевдокода реализует алгоритм таким образом:

 для каждого файла в filesArray вставить массив (файл, время модификации (файл)) в конец преобразованного массива  функция simpleCompare(массив a, массив b) { return a[2] < b[2] }  преобразованныйМассив := сортировка(преобразованныйМассив, простоеСравнение)  для каждого файла в transformedArray вставить файл[1] в конец sortedArray

История

Первое известное появление преобразования Шварца в сети — это сообщение Рэндала Шварца от 16 декабря 1994 года в теме в группе новостей Usenet comp.unix.shell , перенесенное в comp.lang.perl. (Текущая версия Perl Timeline неверна и относится к более поздней дате в 1995 году.) Тема началась с вопроса о том, как отсортировать список строк по их «последнему» слову:

прим.:Джошуа Нгadktk:KaLap Тимоти Квонгadmg:Mahalingam Gobieramananadmln:Марта Л. Нангалама

Шварц ответил:

#!/usr/bin/perl require 5 ; # Новые возможности, новые ошибки! print map { $_ -> [ 0 ] } sort { $a -> [ 1 ] cmp $b -> [ 1 ] } map { [ $_ , /(\S+)$/ ] } <> ;

Этот код выдает результат:

admg:Mahalingam Gobieramananadktk:KaLap Тимоти Квонгadmln:Марта Л. Нангаламаприм.:Джошуа Нг

Шварц отметил в посте, что он «разговаривал на языке lisp в Perl», имея в виду происхождение идиомы из языка lisp .

Сам термин «преобразование Шварца» был придуман Томом Кристиансеном в последующем ответе. Более поздние посты Кристиансена ясно дали понять, что он не намеревался давать название конструкции, а просто ссылаться на нее из исходного поста: его попытка наконец назвать ее «Черное преобразование» не прижилась («Черное» здесь — каламбур от «schwar[t]z», что в переводе с немецкого означает черный).

Сравнение с другими языками

Некоторые другие языки предоставляют удобный интерфейс для той же оптимизации, что и преобразование Шварца:

  • В Python 2.4 и выше как функция sorted() , так и метод list.sort() принимают параметр key= , который позволяет пользователю указать «функцию ключа» (например, foo в примерах выше). В Python 3 и выше использование функции ключа является единственным способом указать пользовательский порядок сортировки (ранее поддерживаемый параметр cmp= , который позволял пользователю указать «функцию сравнения», был удален). До Python 2.4 разработчики использовали идиому decorate–sort–undecorate (DSU), происходящую из lisp [2], обычно путем оборачивания объектов в кортеж (sortkey, object).
  • В Ruby 1.8.6 и выше абстрактный класс Enumerable (который включает Array s) содержит метод sort_by [3] , который позволяет указать «ключевую функцию» (например, foo в примерах выше) как блок кода.
  • В D 2 и выше доступна функция сортировки Шварца . Она может потребовать меньше временных данных и быть быстрее, чем идиома Perl или идиома decorate–sort–undecorate, представленная в Python и Lisp. Это связано с тем, что сортировка выполняется на месте, и создается только минимальное количество дополнительных данных (один массив преобразованных элементов).
  • Основная функция Racketsort принимает #:keyаргумент ключевого слова с функцией, которая извлекает ключ, и дополнительный #:cache-keys?запрос на кэширование полученных значений во время сортировки. Например, удобный способ перетасовать список — .(sort l < #:key (λ (_) (random)) #:cache-keys? #t)
  • В PHP 5.3 и выше преобразование можно реализовать с помощью array_walk , например, чтобы обойти ограничения нестабильных алгоритмов сортировки в PHP.
    функция  сортировки_массивов_пространства ( массив &  $a ) :  void {  array_walk ( $a ,  функция ( & $v ,  $k )  {  $v  =  массив ( $v ,  $k );  });  сортировка ( $a );  array_walk ( $a ,  функция ( & $v ,  $_ )  {  $v  =  $v [ 0 ];  }); }
  • В Elixir методы Enum.sort_by /2 и Enum.sort_by/3 позволяют пользователям выполнять преобразование Шварца для любого модуля, реализующего протокол Enumerable .
  • В Raku необходимо предоставить лямбда-компаратор, который принимает только один аргумент для выполнения преобразования Шварца под капотом:
    @a . sort ( { $^a . Str } ) # или короче: @a.sort(*.Str)
    отсортировал бы по строковому представлению, используя преобразование Шварца,
    @a . sort ( { $^a . Str  cmp  $^b . Str } )
    будет делать то же самое, преобразуя сравниваемые элементы непосредственно перед каждым сравнением.
  • В Rust , что несколько сбивает с толку, метод slice::sort_by_key не выполняет преобразование Шварца, поскольку он не выделяет дополнительное хранилище для ключа, а вызывает функцию ключа для каждого значения для каждого сравнения. Метод slice::sort_by_cached_key вычисляет ключи один раз для каждого элемента.
  • В Haskell функция sortOnиз базовой библиотеки выполняет преобразование Шварца.

Ссылки

  1. ^ Мартелли, Алекс; Эшер, Дэвид, ред. (2002). "2.3 Сортировка с гарантией стабильности сортировки" . Python Cookbook . O'Reilly & Associates. стр. 43. ISBN 0-596-00167-3. Эта идиома также известна как «преобразование Шварца» по аналогии с родственной идиомой Perl.
  2. ^ «Как/Сортировать/Украсить Сортировать Неукрасить».
  3. ^ "Ruby-doc Core-API Classes" . Получено 14 сентября 2011 г. .
В Wikibook Algorithm Implementation/Sorting есть страница по теме: Преобразование Шварца
  • Сортировка с помощью преобразования Шварца Рэндала Л. Шварца
  • Марк-Джейсон Доминус объясняет преобразование Шварца
  • http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52234
  • Python Software Foundation (2005). 1.5.2 Я хочу выполнить сложную сортировку: можно ли выполнить преобразование Шварца в Python?. Получено 22 июня 2005 г.
  • Модуль Memoize Perl — ускорение ресурсоемких функций за счет кэширования их результатов.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Schwartzian_transform&oldid=1234679303"