Loading article…
コンピュータプログラミングにおいて、シュワルツ変換は、項目のリストのソート効率を向上させるために使用される手法です。このイディオム[ 1 ]は、要素の特定のプロパティ（キー）の順序に基づいてソートが行われる比較ベースのソートに適しています。このプロパティの計算はコストのかかる操作であり、最小限の回数で実行する必要があります。シュワルツ変換の特筆すべき点は、名前付き一時配列を使用しないことです。
シュワルツ変換は、Lispのイディオムである「decorate-sort-undecorate」の一種で、ソートキーを入力項目に一時的に関連付けることで、再計算を回避します。このアプローチは、特定の入力値に対応するキーの計算を繰り返すことを回避するメモ化に似ています。これに対し、このイディオムでは各入力項目のキーが正確に一度だけ計算されることが保証されますが、入力データに重複する項目が含まれている場合は、一部の計算が繰り返される可能性があります。
このイディオムは、1994年にPerl 5がリリースされた直後にPerlで初めて実演したRandal L. Schwartz氏にちなんで名付けられました。「Schwartzian transform」という用語は、長年Perlプログラミングにのみ適用されていましたが、後にPythonなどの他の言語のユーザーによって、それらの言語における同様のイディオムを指すために採用されました。しかし、このアルゴリズムは、Schwartz氏によってPerlコミュニティでこの特定のイディオムとして普及する以前から、他の言語で（特定の名前は付けられていませんでしたが）既に使用されていました。「Schwartzian transform」という用語は、アルゴリズム全般ではなく、特定のイディオムを示しています。
例えば、単語リスト ("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 ] or $a -> [ 0 ] cmp $b -> [ 0 ] } # 数値比較を使用し、元のマップで文字列ソートにフォールバックしますmap { [ $_ , length ( $_ )] } # 文字列の長さを計算します@unsorted ;シュワルツ変換の一般形は次のとおりです。
@sorted = map { $_ -> [ 0 ] } sort { $a -> [ 1 ] cmp $b -> [ 1 ] or $a -> [ 0 ] cmp $b -> [ 0 ] } map { [ $_ , foo ( $_ )] } @unsorted ;ここで、 は(リストの各項目を順番に) 受け取り、代わりに比較される対応する値を生成するfoo($_)式を表します。$_
右から左（または下から上）に読む場合：
@unsortedに渡されますmap。この配列は、項目自体と、そのソート順を決定する計算値で構成されます（項目のリストは[項目、値]のリストになります）。mapがに渡されsort、以前に計算された値に従ってソートされます（[アイテム、値]のリスト ⇒ [アイテム、値]のソート済みリスト）。map操作でソートに使用した値（匿名配列から）をアンラップし、元のリストの項目をソートされた順序で生成します（[項目、値] のソート済みリスト ⇒ 項目のソート済みリスト）。匿名配列を使用することで、ソート処理が完了した直後にPerlのガベージコレクタによってメモリが解放されることが保証されます。
シュワルツ変換を用いない場合、上記の例のソート処理はPerlでは次のように記述されます。
@sorted = sort { foo ( $a ) cmp foo ( $b ) } @unsorted ;コードは短くなりますが、ここでの単純なアプローチは、キー関数 (上記の例ではfooと呼ばれています) の計算コストが高い場合、効率が著しく低下する可能性があります。これは、括弧内のコードが2 つの要素を比較する必要があるたびに評価されるためです。最適な比較ソートでは、 O ( n log n ) 回の比較 ( nはリストの長さ) が実行され、比較ごとにfooが 2 回呼び出されるため、結果としてfooの呼び出しはO ( n log n ) になります。これに対し、シュワルツ変換を使用すると、マップの開始段階で要素ごとにfooを 1 回だけ呼び出し、合計でn回のfoo呼び出しになります。
しかし、関数fooが比較的単純な場合、シュワルツ変換による余分なオーバーヘッドは不必要かもしれません。
例えば、ファイルのリストを更新時刻順に並べ替える場合、単純な方法としては次のようになります。
function naiveCompare(file a, file b) { return modificationTime(a) < modificationTime(b) } // sort(list, comparisonPredicate) は、2 つの要素を比較する comparisonPredicateを使用して、指定されたリストをソートすると仮定します。 sortedArray := sort(filesArray, naiveCompare)各ファイルの更新時刻をメモ化していない限り、この方法では、ソート時にファイルを比較するたびに更新時刻を再計算する必要があります。シュワルツ変換を使用すれば、更新時刻はファイルごとに一度だけ計算されます。
シュワルツ変換は、上記で説明した関数型イディオムを用いるものであり、一時配列は使用しません。
同じアルゴリズムを手続き型で記述することで、その動作をより分かりやすく示すことができますが、そのためには一時配列を使用する必要があり、シュワルツ変換ではありません。以下の擬似コード例は、この方法でアルゴリズムを実装したものです。
filesArray内の各ファイルについて 変換された配列の末尾に配列(ファイル、変更時刻(ファイル))を挿入します。 function simpleCompare(array a, array b) { return a[2] < b[2] } transformedArray := sort(transformedArray, simpleCompare) transformedArray内の各ファイルについて ソート済み配列の末尾にファイル[1]を挿入するシュワルツ変換がオンラインで初めて登場したのは、1994年12月16日にランダル・シュワルツがcomp.unix.shell Usenetニュースグループのスレッドに投稿し、comp.lang.perlにもクロスポストした時である。（現在のPerlタイムラインは誤りであり、1995年の後の日付を参照している。）このスレッドは、行のリストを「最後の」単語でソートする方法に関する質問から始まった。
adjn:Joshua Ng adktk:KaLap Timothy Kwong admg:Mahalingam Gobieramanan 管理者:マーサ・L・ナンガラマ
シュワルツ氏は次のように答えた。
#!/usr/bin/env perl require 5 ; # 新機能、新しいバグ! print map { $_ -> [ 0 ] } sort { $a -> [ 1 ] cmp $b -> [ 1 ] } map { [ $_ , /(\S+)$/ ] } <> ;このコードを実行すると、次の結果が得られます。
admg:Mahalingam Gobieramanan adktk:KaLap Timothy Kwong 管理者:マーサ・L・ナンガラマ adjn:Joshua Ng
シュワルツ氏は投稿の中で、「PerlでLispを使って話している」と述べており、これはその表現がLispに由来することを指している。
「シュヴァルツ的変容」という用語自体は、トム・クリスチャンセンが後続の返信で造語したものです。クリスチャンセンのその後の投稿では、彼がこの概念に名前を付けるつもりはなく、単に元の投稿から参照しようとしただけだったことが明らかになっています。最終的に「ブラック・トランスフォーム」と名付けようとした試みは定着しませんでした（ここでいう「ブラック」は、ドイツ語で黒を意味する「schwar[t]z」をもじったものです）。
他の言語の中には、シュワルツ変換と同じ最適化を行うための便利なインターフェースを提供しているものもあります。
sort関数は、キーを抽出する関数を含むキーワード引数を受け取り#:key、さらに、#:cache-keys?ソート中に結果の値をキャッシュするように要求します。たとえば、リストをシャッフルする便利な方法は です。(sortl<#:key(λ(_)(random))#:cache-keys?#t)function spaceballs_sort ( array & $a ) : void { array_walk ( $a , function ( & $v , $k ) { $v = array ( $v , $k ); }); asort ( $a ); array_walk ( $a , function ( & $v , $_ ) { $v = $v [ 0 ]; }); }@a . sort ( { $^a . Str } ) # またはより短い: @a.sort(*.Str)@a . sort ( { $^a . Str cmp $^b . Str } ) sortOn基本ライブラリの関数がシュワルツ変換を実行します。