シュワルツ変換

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

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

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

例として、リスト  を各語の長さに基づいて並び替えることを考える。 まず文字列と長さの配列からリスト  を生成し、次にタプルの数値に基づいてこのリストをソートし  を得て、最後にソート済みリスト要素から数値を取り除き、目的のリスト  を得る。このアルゴリズムの Perl での実装を以下に示す： @sorted = map { $_->[0] } sort { $a->[1] <=> $b->[1] or $a->[0] cmp $b->[0] } # 先に長さを比較し、長さの等しい場合のみ文字列の比較を行う map { [$_, length] } # 文字列の長さを計算する @unsorted;

1. 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 においてこれらの無名配列は、ソート処理が完了した直後にガベージコレクタが呼び出されることが保証されている。

2. 効率
-----

シュワルツ変換を用いずソートする場合、例えば Perl では以下のように書ける： @sorted = sort { foo cmp foo } @unsorted;

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

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

3. 利用例
------

4. 歴史
-----

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

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

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

!/usr/bin/perlrequire 5; # New features, new bugs! print map { $_->[0] } sort { $a->[1] cmp $b->[1] } map { [$_, /$/] } <>;<WtXmlEndTag />

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

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

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

5. 他言語との比較
----------

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

5.1. Python
-----------

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

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

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

5.2. Ruby
---------

Ruby 1.8.6 以降、抽象クラス Enumerable}}は sort_by}} メソッドを持つ。sort_by}} は「キー関数」をコードブロックとして指定できる。

5.3. D言語
--------

5.4. Racket
-----------

5.5. PHP
--------

5.6. Elixir
-----------

5.7. Raku
---------

6. 出典
-----

7. 外部リンク
--------

[1]
[2]
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52234
Python Software Foundation . [3]. Retrieved June 22, 2005.
[4]