2005年05月12日(Thursday)
_ 科学大好き
＞日本の正答率は５４％で１３位
２択で正解率５４％って・・・。
「５年の科学」を愛読したオレならばこんなの当然満点ですよ！
英語力常識チェックとかやられたら散々な結果になりそうですけど。
_ 値の入れ替え
たまにはプログラミングの話題でも。
プログラムを書いていると、しばしば二つの変数の中身を入れ替えるという処理が必要なときがあります。
例えばa=13;b=8;という状態をa=8;b=13という状態にしたい場合。
素直に考えれば、いったんaかbの値を一時変数に保存しておき、順番にコピーをして値を入れ替えます。
Ｃ言語で書けば以下のような感じです。
有名な手法なので知ってる人も多いと思いますが、排他的論理和を使うと一時変数なしで値を入れ替えることができます。
同じくＣ言語で書くと以下のような感じ。
わかりますでしょうか？
排他的論理和を２回とると元に戻るので上記のような方法でも値が失われないわけです。
Ｃ言語を使い始めた何もわかってなかった学生の頃、素直なボクはswap1のようなコードを書いていました。
そこへとある知らない人（大学院生だったか？）がやってきて言いました。
「Hey! 値を入れ替えるときは排他的論理和を使うと一時変数がいらねえんだぜ。
おまえのような素人は知らなかっただろうヘヘン。
プロはこうやるんだぜ。
つまりプロとアマの違いって訳だウハハハハ」
突然やってきてこの台詞は腹立たしいですが、本当に知らなかったのでどうしようも無い。
謙虚に勉強になったからヨシとしときましょう。
しかし当時彼の言った事は本当に正しいのでしょうか？
調べてみましたがあまり情報がみつからなかったのでちょっと検証してみます。
■効率
上の二つの関数をVisualC++.NET 2003でコンパイルしたら以下のようなコードが出力されました。
一応、動作内容をコメントでＣ言語風に併記しましたが、別にちゃんと読んでいただく必要はありません。
（esiをpush,popしているのは関数を抜けるときに変化させてはいけないレジスタだからです）
上のアセンブラコードはおそらく最短コードだと思います。
そして意外にも（？）swap2でも使用レジスタの数は一緒です。
メモリアクセスをできるだけ減らすためにa,bポインタをレジスタにコピーしているからですね。
上の例のように関数になっていたらダメですが、もし処理の途中で計算したい値がレジスタに格納されているならばレジスタが一つ節約できるかもしれません。
結果、レジスタがちょうど足りないという場面があればスタックを使わなくて良い分実行効率が上がる可能性もあります。
ま、そんな都合の良い条件ははごくごく希です。
こうして考えてみると排他的論理和を使うのは速度的に特に有利というわけでもなさそうです。
上の例で実際測定してみても排他的論理和を使った方が速いという事はありません。
というかむしろ遅い。
＃もちろんコンピュータのアーキテクチャにもよりますが。
■そもそも正しいの？
ほとんどの場合、関数swap1を実行しても関数swap2を実行しても全く同じ結果が得られます。
「ほとんどの場合」といったのは例外があるからです。
それは二つの引数が示すアドレスが同一だった場合です。
例えば以下のような呼び出し。
int a=13;
swap2(&a,&a);
printf("a=%d b=%d\n",a,b);
実行結果は以下のようになってしまいます。
a=0 b=13
上の例では明らかに無意味な呼び出しなので同じポインタを
渡すことは無いよと思われるかもしれませんが、混み入った計算をしていたら条件によっては同じポインタが渡されることもあるかもしれません。
このような関数の存在は潜在的なバグの原因になり得ます。
もちろん一時変数を使ったやり方ならば全く問題ありません。
■まとめ
上記のような理由により排他的論理和を利用する値入れ替えは安全であるとは言えません。
パフォーマンス的にも特殊な場合を除いて有利ではありません。
ソースを見たときの理解しやすさも悪そうです。
なんとなくビット演算をすると難しそうに見えてすごそうに見えます。
初心者を騙すにはぴったりな題材という訳です。
しかし実際にはそれほど良いコードではありません。
役に立つのはアセンブラでプログラミングをしていてレジスタが足りないときくらいです。
喜んで覚え立ての排他的論理和で値を入れ替える関数を作る、しかもそれを自慢して回るのはやめたほうがよさそうです。
というわけで結論。
二つの値を入れ替えるときは一時変数を利用せよ。
マクロを作るときは良いかもしれませんが。
#define SWAP(a,b) (a=a^b,b=a^b,a=a^b)
一応、これ以外にも足し算引き算で入れ替える手段もある事を付け加えておきます。
#define SWAP(a,b) (a=a+b,b=a-b,a=a-b)
この場合もaとbが同じアドレスにあるものだと無惨な事になります。
＃なにぶん素人なんで、おかしなところあればご指摘ください。
2006年05月12日(Friday)
_ 写真ダイジェスト（その２）
続きです。
山陰～東北への鉄道の旅を写真でさらっと紹介。
■山陰本線
山陰線の醍醐味は美しい日本海。
暖流が流れるこの地方だからこその景観です。
■舞鶴線～小浜線～北陸本線へ
ここからはややごちゃごちゃした景色が広がります。
日常に近い風景。
ある意味旅行者にはつらい区間。
新幹線はほんの数分間だけ２階建ての２階席を体験。
新幹線を降りれば新潟駅に到着。いよいよ北国に近づきます。
次は東北～北海道で終了です。
364,000 at 2008.06.14
Copyright (c) Suika KNOnline.NET
§ みかん [レジスタ節約云々よりもペアリング失敗（並列処理不可能）の方が痛いですね。 ＞排他的論理和 もっといえばレジスタに割り..]
§ みかん [追加。VCのコードだと並列化がどこにあるか分かりませんね……。 (A) mov ecx, [eax] mov esi..]
§ みかん [(A)訂正。連続書き込みごめんなさい。 mov ecx, [eax] mov esi, [edx] mov [edx..]
§ Suika [なるほどー。 といって使用するレジスタの数増やすと関数呼び出しでスタックに退避する分余計に損しそうだ。]
§ ぉゅぅ [コンパイラや最適化によって変わるとは思いますけど，関数にした次点でオーバヘッドがでかい希ガス. auto変数, 引数..]
§ Suika [効率考えるなら、変数型も含めてマクロにするのが一番かな。 ちなみにテーマはＸＯＲを使うことが意味あるのかどうか。結論..]
§ ひかりん [科学について知らないなと思う人に対してはあさりよしとお氏の「まんがサイエンス」を勧めています。って「５年の科学」じゃ..]
§ Suika [めっちゃおもしろいです！]
§ spoopsbek [シャネル ポー|..]
§ にら [このアルゴリズムを前風呂で思いついた。]