Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

Например, чтобы отсортировать список слов («аааа», «а», «аа») по длине слова: сначала создайте список ([«аааа», 4], [«а», 1], [«аа ", 2]), затем отсортируйте его в соответствии с полученными числовыми значениями ([" a ", 1], [" aa ", 2], [" aaaa ", 4]), затем удалите числа, и вы получите ( «а», «аа», «аааа»). Это был алгоритм в целом, поэтому он не считается преобразованием. Чтобы сделать его истинным преобразованием Шварца, это нужно сделать в Perl следующим образом:

@sorted  =  map  {  $ _ -> [ 0 ]  }  sort  {  $ a -> [ 1 ]  <=>  $ b -> [ 1 ]  или  $ a -> [ 0 ]  cmp  $ b -> [ 0 ]  }  # Использовать числовое сравнение, вернуться к сортировке строк на исходной  карте  {  [ $ _ ,  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 . Для сравнения, используя преобразование Шварца, мы делаем только один вызов foo для каждого элемента в начале map.stage, всего n вызовов foo .

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

Пример [ править ]

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

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

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

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

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

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

История [ править ]

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

прил .: Джошуа Нгadktk: KaLap Тимоти Квонгadmg: Махалингам Гобиерамананadmln: Марта Л. Нангалама

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

#! / usr / bin / perl требуется  5 ;  # Новые функции, новые ошибки! распечатать  карту  {  $ _ -> [ 0 ]  }  sort  {  $ a -> [ 1 ]  cmp  $ b -> [ 1 ]  }  map  {  [ $ _ ,  / (\ S +) $ / ]  }  <> ;

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

admg: Махалингам Гобиерамананadktk: KaLap Тимоти Квонгadmln: Марта Л. Нангаламаприл .: Джошуа Нг

Шварц отметил в своем посте, что он «шепелявил в Perl», отсылка к истокам Lisp идиомы .

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

Сравнение с другими языками [ править ]

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

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

Ссылки [ править ]

  1. ^ Мартелли, Алекс; Ашер, Дэвид, ред. (2002). «2.3 Сортировка при обеспечении стабильности сортировки». Поваренная книга Python . O'Reilly & Associates. п. 43 . ISBN 0-596-00167-3. Эта идиома также известна как «преобразование Шварца» по аналогии с родственной идиомой Perl.
  2. ^ «Как / Сортировка / Украсить Сортировка Без Украсить» .
  3. ^ "Ruby-doc Core-API Classes" . Проверено 14 сентября 2011 года . CS1 maint: обескураженный параметр ( ссылка )

Внешние ссылки [ править ]

  • Сортировка с преобразованием Шварца, Рэндал Л. Шварц
  • Марк-Джейсон Доминус объясняет преобразование Шварца
  • http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52234
  • Фонд программного обеспечения Python (2005 г.). 1.5.2 Я хочу выполнить сложную сортировку: можете ли вы выполнить преобразование Шварца в Python? . Проверено 22 июня 2005 года.
  • Модуль Memoize Perl - ускорение дорогостоящих функций за счет кэширования их результатов.