ごく例外を除けば、ゲームの流行というのはスパンが短いものだから、皆さん がこれを読む時にはもう「ときメモ」も流行が終わっているのかもしれないが、 とりあえず、前回、アルバムモードの写真の枚数を「150〜180の間に限界がある のではないか」と見積もってしまったが、これが甘かったようなのでフォローさ せていただくと、本気で「やり直しプレイ」をすれば、200枚を簡単に越えること が分かった。デートに誘ってもらえる所は全部誘ってもらって、残りの休日で誘 える所は全部デートに誘えば、壁は多分230枚のあたりに来るようだ。枚数が多く て何が面白いのだとか、枚数よりも中身ではないか、という声もあり、実際その 通りなのだが、何十分の1の確率でその週の予定がうまくいって、最後に電話でデー トのOKをもらうだけ、という時には、まるでスーパーリーチがかかったようなエ キサイティングな状態になるものである。もっとも、私はパチンコから足を洗っ たので、ここ数年やっていないが。
*
以前、漢字コードの1バイト目を判断するトリッキーな判断を紹介した。
((unsigned int) (c ^ 0x20) - 0xa1 < 0x3c) …(1)
何をやっているのか、ぱっと見ただけでは分からないという点では、これは秀
逸であるが。しかし、目的としては、技巧に走るというよりは、処理速度とか効
率を考えた結果このような書き方になったのである。
最もポピュラーなのは、次のような比較であろうと想像していた。というのは、 経験として、この処理は複数のプログラムで見掛けたことがあるからだ。
/* c は unsigned char */
(c >= 0x81 && c <= 0x9f) || (c >= 0xe0 && c <= 0xfc) …(2)
この場合、&&の方が||より優先されるため、括弧()は不要だが、あえ
て付けておいた方がいい。可読性を高めるためである。a*b+c*dやa+b*c+dは、優
先順位を知っていれば計算間違いすることはないが、ぱっと見た時の明瞭さは
(a*b)+(c*d)やa+(b*c)+dに及ばないのだ。だったら、
((c >= 0x81) && (c <= 0x9f)) || ((c >= 0xe0) && (c <= 0xfc))
と書いてもよさそうなものだという人もいるだろう。過ぎたるは及ばざるが如
し、ということもある。括弧が多すぎると、逆に可読性が低くなる。美観の問題
だから、多少は個人差があるだろうが、私の感覚だとここまで付ける必要はない
と思う。
さて、確かにこれはこれで問題なさそうだが、ここで終わってしまってよいの だろうか、という疑問を感じた人はいないか。つまり、この比較方法は、本当に ポピュラーなのだろうかということである。他に書き方があるのではないか、と いう疑問だ。実際、(1)のような書き方があることが分かっているから、唯一の書 き方でないことは証明されたことになる。しかし、これはこれで単純明解ではな いか、何がダメなんだ、と思われるかもしれない。そこで、実際にどのような処 理が行われているのか、頭の中でたどってみよう。
&&と||という演算子は、左から右に評価されることになっている。C言 語では、多くの演算子の評価順序は不定だが、言うまでもなく、これらの演算子 は数少ない特例だ。そこで、(2)の式がどのような順序で評価されるか考えるとい う単純な作業を試みる。
仮に、cの値が0x45としてみよう。最初の式は、
c >= 0x81
である。これは偽になるから、&&の右側は評価されずに打ち切られる。
そして、最初の()の中全体は偽になるから、続いて||の右側の評価に移る。次に
評価される式は
c >= 0xe0
である。これも偽になるから、その後の&&の右側は評価されずに打ち切
られる。右側の()の中全体も偽になるから、最終的にこの式全体の値は偽という
ことになる。
ここで細かい話が好きな人は気になることがあると思うのだ。そう、
c >= 0x81
が偽であるならば、
c >= 0xe0
も偽に決まっているのではないか。なぜこのような無駄な比較をしなければなら
ないのだろう。即座に思い付く理由は、その無駄を取り除くのが困難な場合であ
る。無駄は承知だが、どうしようもない、ということはよくある。では、この場
合も無駄を省く方法はないのか。否、実に簡単な方法があるのだ。というのは、
この場合は
c >= 0x81
が成り立ったら、全体の式が偽になることは即座に確定するのである。だから、
ちょっと細工をして、(2)の式の括弧の位置を次のようにしてみる。
c >= 0x81 && ((c <= 0x9f) || (c >= 0xe0 && c <= 0xfc)) …(3)
まさに括弧の位置が変わっただけである。これで、
c >= 0x81
が成り立たない時にさらに
c >= 0xe0
を確かめるという無駄はなくなった。しかも、他の場合の処理は元のままである。
従って、明らかに、結果は元の式と同値である。
では、この書き換えの是非はどうか。私の感じとしては、この書き換えが、特 にコードをどうしようもないほど難解にするとは思えないのである。しかも、経 験的に、この記述はiskanji1stのような名前のマクロ定義として用いられ、プロ グラム本体では現れないようにする習慣がある。プログラム全体がこれで見にく くなることも、まずない。にもかかわらず、なぜかこのような書き方は見た覚え がない。例えば、手元にある「C言語による最新アルゴリズム事典」「C言語によ る最新プログラム事典」には、括弧が省略されているが、(2)相当の比較が行われ ている。
(3)のアルゴリズムの特徴は、0〜0x80のコードが現れた時の無駄が省かれた所
にあるから、処理する内容の殆どがこの範囲に入る場合には、効率がかなり違っ
てくる。例えばCのプログラムソースなどは、その典型的な例だろう。殆どが漢字
で書かれた文書なら、最初の
c >= 0x81
の結果が真になってしまうので、あまり差はないはずだ。
これで話が終わりではない。まだある。一つ簡単な数学のクイズを考えてみよ う。抽象的に考えてみよう。この処理は、0〜0xffの整数値が、独立した二つの区 間によって五個の範囲に分かれている。ある値が、この二区間のいずれかに含ま れるか、あるいはどちらにも含まれないかを知るためには、最低何回の比較を行 う必要があるか。ただし、最初の比較結果によって、次に比較する値を変えても よい。二つの区間が離れているから、その間の数とまず比較することにより、ど ちらの区間に含まれる可能性があるか判定できる。その後、それぞれの区間に本 当に含まれるかどうかは上限下限の2回の判定で実現できる。従って、高々三回の 比較で結論が出せるはずだ。ところが、(3)の方法だと、値が0xe0〜0xfcの範囲に ある場合は、4回の比較を行っている。ということは、まだどこかに無駄があるこ とになる。
今考えた方法をすなおにコーディングすると次のようになる。
c <= 0x9f ? c >= 0x81 : c >= 0xe0 && c <= 0xfc …(4)
このように、同じ処理に対して4通りの方法が見つかったのである。ここで、
(2)〜(4)の、cの値に対する比較の回数は表のようになる。(1)は演算を一回の比
較とみなして数えたら、cの値に関らず3回の比較で結果が出る。あまり効率がよ
くないように見えるが、最近のCPUのように内部でパイプライン処理を行っていた
りすると、一般に比較で分岐する命令より単純な演算の方が処理速度が期待でき
そうなので、何ともいえない。
00〜80 81〜9f a0〜df e0〜fc fd〜ff
(2) 2 2 3 4 4
(3) 1 2 3 4 4
(4) 2 2 2 3 3
比較回数だけに注目すると、表を見る限りでは、(2)よりは(3)が明らかに優れ
ている。(3)と(4)を比べると、00〜80の文字コードが多いテキスト(例えばプログ
ラムなど)では(3)が、0xe0〜0xffのコードが多いテキストでは(4)が有利に見える。
ところで、もう一つ見逃しがちなことがある。これらの文字の出現頻度だ。実際
にNIFTY-Serveのログの文字数を数えてみたら、00〜80が3割、81〜9fが7割である
ことがわかった。つまり、a0〜ffに相当する文字は、殆ど現れないのである。言
いかえると、文章中に現れる漢字コードの殆どは1バイト目が0x81〜0x9fの範囲に
入っているのである。この場合の比較の期待値は、(2)(4)の方法だと2回、(3)だ
と1.7回ということになり、NIFTY-Serveのログを処理する場合には(3)が最も効率
よいという結論が出る。
*
実は、これについてNIFTY-Serveのプログラマーズフォーラムの電子会議「ソフ
トウェア無作法」で、先行して議論を試みたのである。中には、やはり(3)の書き
方をしている人もいたのだが、議論全体の結果としては、あくまで私の主観的な
判定だが、効率を考慮してなお、(2)の書き方の方が(3)よりも好まれるというも
のだった。すなわち、確かに(3)の方が効率は良いかもしれないが、(2)の明快さ
はそれに勝るというのである。これに関してはどちらの主張も一理あるので結論
は難しいと思うのだが、一つの要因としては、「今までそう書いてきたから」と
か「他の人がそう書いているから」という伝統的なものがあるような気がする。
しかも、(2)の書き方は二つの範囲を押さえるという、直感的に極めて理解しやす
いロジックで成立している。同様に考えると、(3)は下から順に押さえてゆくとい
う考え方ができて、仮にC言語ではなくアセンブラで漢字1バイト目の判定コード
を書くということになったら、(3)の考え方の方がむしろポピュラーではないかと
も思えるのだが。
といいつつも、実はBPLの最新版の中の処理はこっそり(2)から(3)に書き直して あったりするのである。もっとも、最近はハードウェアが高速になりすぎたので、 この程度の頑張りはどこか別のボトルネックに隠れてしまって、何の効率向上に も結び付かないかもしれない。そうなると、この手の工夫をするという姿勢を忘 れないプログラマーは、今後はどんどん減ってしまうのかもしれないが、それは それで何か変な気分である。
※参考文献
奥村晴彦 著、「C言語による最新アルゴリズム事典」、技術評論社 平林雅英 著、「C言語による最新プログラム事典」、技術評論社