2014-03-09-01-minmax_element - project-enigma

2014-03-09-01-minmax_element

>> Site top >> weblog >> 月別アーカイブ >> 2014年03月のlog >> 2014-03-09-01-minmax_element

最終更新日付:2014/03/09 13:29:32


minmax_element

2014 年 03 月 09 日

ファンクタの件も一応カタがついたので、新しいアルゴリズムを少しずつ実装している。今日は、minmax_element について。

‥‥‥というか、今回のエントリは一度書き上げたものを操作ミスで完全に削除してしまい、全部書き直しをするハメに陥った。使い慣れたつもりの Emacs だが、dired で削除するとゴミ箱にはいかないから二度と戻ってこない。気をつけないと。

さて、minmax_element。これは、まぁ要するに min_element と max_element をいっぺんにやるようなものなわけだが、単純に考えると対象シーケンスの要素を順番に反復し、都度最小値と最大値(の位置)と比較して更新していき、最後に結果の pair を返す、ということになる。しかし、今回参考にした実装はそうなってはいなかった。どうなっていたかというと、先頭から2値ずつ反復し、最初にその2値を比較、小さい方を(それまでに見つかった)最小値と比較し、大きい方を(それまでに見つかった)最大値と比較する、ということをやっていた。最初はなんでそんなことをやっているのか分からなかったが、理由がわかった瞬間に目から鱗が落ちたような気がした。このやり方だと、全体として比較回数はおおむね 1.5 n 回になるが、まさにそれが狙いだったのだ。

どういうことかというと、最初に書いた「単純な実装」だと、比較回数は最良の場合で n 回だが、最悪の場合には 2n 回になるのだ。最小値との比較を先にやる場合、毎回最小値が更新されるならば最大値との比較はしないで済むから最良の場合になるが、それ以外の場合は最大値との比較もしなければならない。だから、9 - 0 の順番で並んでいるような場合には最良だが、0 - 9 で並んでいるような場合は最悪だ。ランダムな並び順であれば、最良と最悪の間のどこかになる。

2値ずつ比較していく方法であれば、これが 1.5 n 回の固定になる。愚直な実装の最良には敵わないが、最悪よりは効率が良いし、なにより安定している。実際問題として、2回に1回以上の割合で最小値が更新されるのでなければ愚直な実装で 1.5 n 回を下回ることはないのだから、これは割に合う取引と言えるだろう。アルゴリズムの設計というのはこういうことを考え抜く必要があるのだな‥‥‥と痛感した次第。

 

コメント

このページにコメントする

 

このページのタグ

Page tag : STLとその移植

 

 


Copyright(C) 2005-2017 project-enigma.
Generated by CL-PREFAB.