シュワルツ変換について

Question

ソートアルゴリズムのシュワルツ変換について質問です。

加工用の一時領域を作るためメモリが、多く必要になるのは理解しています。
しかし、計算速度が向上する理由がピンときていません。
今のところ、加工とソートを２つに分けることで命令が単純になり向上するという認識なのですが、それであっていますか？

加工とソートを２つに分けることで、計算速度が上がる物理的な理由を教えて頂けますでしょうか？

Answer 1

ソートは
・2つの要素の比較
・配列の操作
を繰り返しますが、
単純な要素でなく、要素を加工した値で比較したい場合、
・2つの要素を加工
・2つの加工した要素の比較
・配列の操作
となります。
ソート開始から終了までで、各要素はたいてい複数回参照されるので、
これだと同じ要素に対して何度も加工を行うことになります。

そこで、加工済み配列を用意し、
加工済み配列使ってソートすれば、各要素に対して一回の加工で済みます。

Comments

[退会済みユーザー]

具体的なイメージが掴めました。
ありがとうございます！

Answer 2

シュワルツ変換を使わないソートの場合は、ソートキーを参照するたびに毎回ソートキー生成を行います。
シュワルツ変換を使ったソートは、ソートキー生成の回数が１要素につき必ず１回で済むようになります。

ソートでのソートキーへのアクセスはほとんどの要素で複数回行われますので、ソートキー生成のコストが高い場合には、シュワルツ変換の方が実行効率が良くなります。

参考URL:
シュワルツ変換の実行効率 - 英語とプログラミング気まぐれ日記

Comments

[退会済みユーザー]

解説 + 参考URLをのせていただいたので、ベストアンサーにさせてもらいました。
ありがとうございました！