コンテンツにスキップ

シュワルツ変換

出典: フリー百科事典『ウィキペディア（Wikipedia）』

シュワルツ変換（シュワルツへんかん、英: schwartzian transform）は、リストの要素のソートを効率良く行うためのプログラミングの手法の一つである。 このイディオム[1] は、要素の順序が実際には要素のあるプロパティ（キー）の順序に基づいていて、キーの計算に多くの計算資源を要するため計算回数を最小限にしたい状況で行う比較ソートに適している。シュワルツ変換の特徴として、名前付きの一時配列を使わないことが挙げられる。

シュワルツ変換は LISP において decorate-sort-undecorate（DSU）として知られるイディオムの一種であり、一時的に入力要素とキーを関連付けることでキーの再計算を避けるイディオムである。このアプローチはメモ化に似ていて、メモ化では特定の入力値に関連しているキーの再計算を避けている。比較すると、シュワルツ変換は各入力要素のキーを計算回数が厳密に一度であることを保証する。ただし、入力要素に重複がある場合、同値な要素に対して複数回キーの計算を行う。

シュワルツ変換の名はランダル・L・シュワルツ（Randal L. Schwartz）に因む。シュワルツは Perl 5 リリース直後の1994年にこのイディオムを Perl で初めて実装した。「シュワルツ変換」の語は専ら Perl の文脈でのみ用いられてきたが、後に Python など他のプログラミング言語のユーザの間でも、類似のイディオムに言及する際に用いられるようになった。しかしこのアルゴリズムは、シュワルツによる特定のイディオムとして Perl コミュニティの間で普及するより以前に、既に他の言語で（特定の名前を与えられずに）用いられている。「シュワルツ変換」の語は特定のイディオムを示すのであって、一般のアルゴリズムを示すのではない。

例として、リスト ("aaaa","a","aa") を各語の長さに基づいて並び替えることを考える。 まず文字列と長さの配列からリスト (["aaaa",4],["a",1],["aa",2]) を生成し（decorate）、次にタプルの数値に基づいてこのリストをソートし (["a",1],["aa",2],["aaaa",4]) を得て（sort）、最後にソート済みリスト要素から数値を取り除き（undecorate）、目的のリスト ("a","aa","aaaa") を得る。このアルゴリズムの Perl での実装を以下に示す： 

@sorted = map  { $_->[0] }
          sort { $a->[1] <=> $b->[1] or $a->[0] cmp $b->[0] } # 先に長さを比較し、長さの等しい場合のみ文字列の比較を行う
          map  { [$_, length($_)] }    # 文字列の長さを計算する
               @unsorted;

Perl

[編集]

一般のシュワルツ変換は以下である: 

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

ここで foo($_) は $_（リスト要素）を順番に受け取り、リスト要素の代わりに比較に使う値を与える式を表す。

上記コードは右から左へ（あるいは下から上へ）順に:

  • ソート元のリスト @unsorted は map 操作へ渡され、各要素は自分自身とソート順を決定する値（キー）からなる配列にラップされる（結果は [元要素, キー] の未ソートのリスト）
  • map されたリストを sort に渡し、直前に計算したキー基づいてソートする（結果は [元要素, キー] のソート済みリスト）
  • 最後に map でリスト内の配列から目的の要素を取り出し、元リストのソート結果を得る（結果は元要素のソート済みリスト）

最初の map 操作でリスト要素と対応するキーを無名配列に持たせているが、Perl においてこれらの無名配列は、ソート処理が完了した直後にガベージコレクタが呼び出されることが保証されている。

効率

[編集]

シュワルツ変換を用いずソートする場合、例えば Perl では以下のように書ける： 

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

コードは単純になるが、この素朴な方法は、キー関数 foo の計算が高価になる場合、シュワルツ変換の方法より非効率となる。それは素朴な実装では2要素の比較が必要となるたびに、括弧内のコードが評価されるためである。最適比較ソートの比較の計算量は O(n log n)（ここで n はリストの長さ）であり、素朴な実装では一度の比較のたび foo が 2 回呼び出されるため、O(n log n) 回だけ foo が呼ばれる。対照的に、シュワルツ変換の方法では、最初の map 操作の段階でソート対象のリストの各要素に対し 1 回だけ foo が呼び出されるため、合計の呼び出し回数は n 回となる。

しかし、関数 foo が比較的安価である場合、シュワルツ変換は必ずしも素朴な実装より効率的ではなく、（decorate-undecorate による）追加のオーバーヘッドのために素朴な実装より計算量を要することがある。

利用例

[編集]

歴史

[編集]

オンライン上で確認できるシュワルツ変換の例としては、1994年12月16日にランダル・シュワルツがニュースグループ comp.unix.shell のスレッドに投稿、また comp.lang.perl へのクロスポストが最初である[2]。スレッドは、下記の形式のリストの行末の単語でソートを行うにはどうすればいいか、という質問で始められている（リストは元の投稿からの抜粋）。 

adjn:Joshua Ng
adktk:KaLap Timothy Kwong
admg:Mahalingam Gobieramanan
admln:Martha L. Nangalama

シュワルツはこの質問の回答として以下のコードを示した： 

#!/usr/bin/perl
require 5; # New features, new bugs!
print
    map { $_->[0] }
    sort { $a->[1] cmp $b->[1] }
    map { [$_, /(\S+)$/] }
    <>;

このコードは以下の結果を与える： 

admg:Mahalingam Gobieramanan
adktk:KaLap Timothy Kwong
admln:Martha L. Nangalama
adjn:Joshua Ng

"Schwartzian transform" という語そのものは、トム・クリスチャンセンの投稿に由来する。クリスチャンセンは後に、名付けをする意図はなく、単に元の投稿を示しただけであったことを明らかにしている。最終的にクリスチャンセンは "The Black Transform" という名を提案したが、普及しなかった（この命名は "schwartz" がドイツ語で英語の "black" を意味することから来る洒落である）[3]。

他言語との比較

[編集]

いくつかの Perl 以外のプログラミング言語は、シュワルツ変換（DSU）と同等の最適化のためのインタフェースを提供している。

Python

[編集]

Python 2.4 より以前は、ユーザは LISP 由来の decorate–sort–undecorate (DSU) イディオム[4] を用い、大抵はリスト要素のオブジェクトをタプル (sortkey, object) にラップしてソートしていた。

Python 2.4 以降では、 sorted() 関数と in-place な list.sort() メソッドのいずれも、引数 key= を（Perl のコード例の foo に相当する）キー関数をユーザ側で指定することができるようになった。

Python 3 から、キー関数はユーザ定義のソート順序を与える唯一の方法となり、それ以前に提供されていた比較関数の引数は廃止された。

Ruby

[編集]

Ruby 1.8.6 以降、抽象クラス Enumerable（これは Array を含む）は sort_by[5] メソッドを持つ。sort_by は（Perl の例での foo のような）「キー関数」をコードブロックとして指定できる。

D言語

[編集]

Racket

[編集]

PHP

[編集]

Elixir

[編集]

Raku

[編集]

出典

[編集]
  1. ^ Martelli, Alex; Ascher, David, eds (2002). “2.3 Sorting While Guaranteeing Sort Stability”. Python Cookbook. O'Reilly & Associates. p. 43. ISBN 0-596-00167-3. https://archive.org/details/pythoncookbook00mart/page/43. "This idiom is also known as the 'Schwartzian transform', by analogy with a related Perl idiom." 
  2. ^ Schwartz, Randal L. (16 December 1994). "Q: sort on last word in field/record". Newsgroup: comp.unix.shell. 2021年6月10日閲覧。
  3. ^ Cristiansen, Tom (7 December 1996). "Ques: Use of "[ ]" in map". Newsgroup: comp.lang.perl.misc. 2021年6月10日閲覧。
  4. ^ "The Old Way Using Decorate-Sort-Undecorate". 2021年6月14日閲覧。
  5. ^ "Module: Enumerable (Ruby 3.0.1)". 2021年6月16日閲覧。

外部リンク

[編集]
「https://ja.wikipedia.org/w/index.php?title=シュワルツ変換&oldid=85151174」から取得