シュワルツ変換
シュワルツ変換を用いずソートする場合、例えば Perl では以下のように書ける:
コードは単純になるが、この素朴な方法は、キー関数 foo の計算が高価になる場合、シュワルツ変換の方法より非効率となる。それは素朴な実装では2要素の比較が必要となるたびに、括弧内のコードが評価されるためである。最適比較ソートの比較の計算量は O(n log n)(ここで n はリストの長さ)であり、素朴な実装では一度の比較のたび foo が 2 回呼び出されるため、O(n log n) 回だけ foo が呼ばれる。対照的に、シュワルツ変換の方法では、最初の map 操作の段階でソート対象のリストの各要素に対し 1 回だけ foo が呼び出されるため、合計の呼び出し回数は n 回となる。
しかし、関数 foo が比較的安価である場合、シュワルツ変換は必ずしも素朴な実装より効率的ではなく、(decorate-undecorate による)追加のオーバーヘッドのために素朴な実装より計算量を要することがある。
シュワルツ変換(シュワルツへんかん、英: schwartzian transform)は、リストの要素のソートを効率良く行うためのプログラミングの手法の一つである。 このイディオム は、要素の順序が実際には要素のあるプロパティ(キー)の順序に基づいていて、キーの計算に多くの計算資源を要するため計算回数を最小限にしたい状況で行う比較ソートに適している。シュワルツ変換の特徴として、名前付きの一時配列を使わないことが挙げられる。
シュワルツ変換は LISP において decorate-sort-undecorate(DSU)として知られるイディオムの一種であり、一時的に入力要素とキーを関連付けることでキーの再計算を避けるイディオムである。このアプローチはメモ化に似ていて、メモ化では特定の入力値に関連しているキーの再計算を避けている。比較すると、シュワルツ変換は各入力要素のキーを計算回数が厳密に一度であることを保証する。ただし、入力要素に重複がある場合、同値な要素に対して複数回キーの計算を行う。
シュワルツ変換の名はランダル・L・シュワルツ(Randal L. Schwartz)に因む。