• BPnet
  • ビジネス
  • IT
  • テクノロジー
  • 医療
  • 建設・不動産
  • TRENDY
  • WOMAN
  • ショッピング
  • 転職
  • ナショジオ
  • 日経電子版
  • PR

  • PR

  • PR

  • PR

  • PR

記者の眼

楽しい! プログラミング

山口哲弘 2003/10/30 ITpro

 プログラミング雑誌『日経ソフトウエア』に異動して,かれこれ1年近くになる。私自身のプログラミング経験は長い。1981年に初めてパソコン(当時は「マイコン」と呼んでいた)に触れて以来,かれこれ20年以上になる。当時は,「パソコンを使う」と「プログラムを作る」は同義語だったから,パソコン・ユーザーはみんなプログラマだった。そんな私だが,プロのプログラマでないので,こんなに明けても暮れてもプログラミング漬けの生活を送ったのは,今年が生涯初めてだ。

 20年以上にわたって続けているだけのことはあり,プログラミングは嫌いではない。どちらかというと好きな方だ。ただ,最近のプログラミングには,どこか飽きてきている。モデリングどのこうの,なんたらウィザード・・・。プログラミングとはそうではなくて,もっと作る喜び,考える楽しさがあったはずだ。もちろん設計は重要だし,プログラマの負担を軽減する機能は重要なのだが。

 そんな今でも,プログラミングの楽しさはいくらでも味わえる。ここではそんな例として,『日経ソフトウエア』2003年12月号特集2で扱った二つの処理を紹介しよう。

立っているビットをどう数える?

 まずは,次の処理を考えてみてほしい。
「任意の32ビットの値の立っているビット(1のビット)の数を数える」

 これは1年ほど前,知人に出されたクイズだ。このような処理を考えているときは楽しいし,解答例だと思われる処理方法が思いついたときには,やはりうれしいものだ。

 ちなみにこの問題,32ビット値の立っているビットを数えるのに,1ビットずつ32回繰り返し処理するのでは,クイズにならない。32回繰り返さずに,しかもより短い時間で処理する方法を考えなければならない。ここでは私が考えた処理方法と,そこに行き着くまでを紹介しよう(詳しくは,日経ソフトウエア2003年12月号特集2をご覧いただきたい)。たぶん読者の方々の中には,私よりもすぐにひらめいた方もいらっしゃることだろう。

 私は最初,1ビットずつ32回繰り返し調べる方法を考えた。それにはシフト命令を使えばいい。ここまでで数秒である。少しプログラミングに慣れていれば,32回繰り返す方法はすぐに思いつく。私はこの方法をより最適化しようとした。だが,この方法はすぐに行き詰まった。1ビットずつ調べる方法を採った時点で,32回繰り返さなければならない。32回繰り返さずに調べるには,1ビットずつ調べてはいけないのである。
 ここで少し頭をひねると,ひらめいた。「1ビットずつ調べてはいけない」の「調べてはいけない」方にである。調べないで数えられるうまい方法があれば,それに違いない。

 調べないということは,数値的に演算することしか思いつかない。そこで,簡単のため4ビットで考えた。任意の4ビット値の立っているビットを「計算」する方法は,と考えると,リスト1のような処理が思いついた(リスト1はC言語風に書いてあるが,C言語には符号なし4ビット整数を表す組み込みデータ型がないので,変数宣言などは省いてある)。詳しい説明は2003年12月号の特集2をご覧いただきたいが,かいつまんで説明すると次のとおりだ。

 任意の4ビットの値を「abcd」(a,b,c,dはそれぞれ0または1)とすると,この値は10進数では8a+4b+2c+dになる。また,立っているビットの数はa+b+c+dだ。元の値「8a+4b+2c+d」から立っているビットの数「a+b+c+d」を導く処理がリスト1というわけである。これを32ビットに拡張すると,リスト2のような処理になる。32ビットの値を4ビットずつ八つのブロックに分けて処理し,求まった八つの数を足し合わせるというものだ。ここまでたどり着くのに約3時間を要した。

 これが模範解答だろうと先ほどの知人に伝えると,基本方針は同じものの,違っていた。もっと速く処理できる方法があったのである。その処理方法は,2ビットずつ16個のブロックに分けて処理するというものだ。4ビットずつ処理するプログラムと2ビットずつ処理するプログラムとを比べると,確かに2ビットずつの方がステップ数が少なくて済む。

 私が4ビットずつで考えたのは,4ビットは16進数1けた分で考えやすかった,という理由だけだが,その時点で負けていたわけだ。

10で割る処理はどうする?

 2003年12月号特集2では,カラー画像のモノクロ変換処理も題材に使った。モノクロ化するには,赤,緑,青の各成分を同じ値にすればよいのだが,単純に3成分の平均を取ってしまうと,人間の目には不自然に見えてしまう。人間の目には,緑色に感じやすく青色に感じにくいという特性があるからだ。その特性に合わせて加重平均を取った方が,自然な階調になる。式で表すと次のとおりだ。

BW = 0.299R + 0.587G + 0.114B

 浮動小数点演算は一般に時間がかかるので,通常はこれを整数で近似して,次のような処理をすることが多い。

(3R + 6G + B)/10

 画像の各画素について,このようにして求めた値を3成分に代入すると,モノクロになる(リスト3)。

 この処理をアセンブリ言語で記述するとリスト4のようになる。大きな連続したメモリー領域に対して同じ処理を繰り返すときは,プリフェッチ命令を使うとメモリー・アクセスに要する時間を隠すことができ,高速化を図れる。リスト4では,通常,コンパイラは使わないプリフェッチ命令を使った。

 C++言語のソースコード(リスト3)からC++コンパイラ(Visual C++ .NET 2003)が生成したコードの実行時間と,自分でアセンブリ言語で記述したコード(リスト4)の実行時間を比べると,1.1GHz動作のCeleron(P6アーキテクチャ)では,アセンブリ言語のコードのほうが速かった。最近のコンパイラの最適化は優秀で,ヘタなプログラマが書いたアセンブリ言語のコードよりも,コンパイラが生成したコードの方が速いことを知っていたので,内心,私のアセンブリ・プログラミングもまんざらではないな,と思った。

 が,それもつかの間。同じプログラムをAthlon XPで動かすと,コンパイラが生成したコードの方が速いではないか。いったいVCはどんなコードを生成したのかと,アセンブリ・コードを見てみた。それがリスト5である。

 10行目のMOV命令から15行目のADD命令までが10で割る処理である。これは符号付き整数の除算処理である。符号処理の分,分かりにくくなっているので,符号なしにするとリスト6のようになる。私はこれがなぜ10で割る処理になるのか,最初は理解できなかった。乗算命令が使われているので,10で割る代わりに0.1を掛けているのだろうということは想像できたが,分からない。

 そこで,先ほどの知人にこの処理を解説してもらった。実はその知人は,私のプログラミングに関する10年来の師匠なのである。その知人には,0.1で掛けているということまで分かるのになぜ分からないのか,わからない,と笑われたが,説明してもらうとなるほどである。

 リスト6の2行目でEAXレジスタに代入している0CCCCCCCDHを掛け,4行目でEDXレジスタの値を3ビット右シフトしている(8で割っている)。この処理が,0.1を掛ける処理そのものなのだった。

 MUL命令は,64ビットの乗算結果のうち上位32ビットをEDXレジスタに格納する。つまり,0CCCCCCCDHを掛け,その上位32ビットを取ってくるということは,次のような処理に当たる。

<値> × 0CCCCCCCDH ÷100000000H

 そして,その値を8で割るということは,すなわち次のような処理になる。

<値> × 1999999AH ÷100000000H

 ここで,0CCCCCCCDH÷8=1999999AHである。通常,固定小数点の小数値を小数点を使って16進数では表現しないが,便宜的に強引な書き方をすると,次のように表せる。

<値> × 0.1999999AH

 ここで,0.1999999AHは10進数の0.1である。10進数の0.1を16進数で表すと循環小数になってしまい,有限のけた数に丸めると誤差が出てしまうが,所詮,整数演算なので,問題ないのである。

 ここでは二つの処理を例に挙げたが,このような処理方法を考えること,ソースコードからその処理内容を考えることはじつに楽しい。やっぱりプログラミングは,楽しいものなのである。今後もこのようなプログラミングをしたいものだ。こんなプログラミング,楽しくないですか?

(山口 哲弘=日経ソフトウエア編集委員)

あなたにお薦め

連載新着

連載目次を見る

今のおすすめ記事

  • 【ニュース解説】

    インドIT大手が米クラウド専業を買収した理由

     米アピリオが、事業戦略の転換を図っている。米セールスフォース・ドットコムなどのクラウドサービスを活用したシステム開発で実績を積んできたが、インドのIT大手ウィプロが買収。今後は、ウィプログループのクラウド事業の牽引役としての役割を果たす。

  • 【ニュース解説】

    AWSとAzure、戦いの舞台はNoSQLへ

     パブリッククラウドサービス2強である、米アマゾン・ドット・コムのAmazon Web Services(AWS)と米マイクロソフトのMicrosoft AzureがNoSQLデータベースの分野で激しいサービス競争を繰り広げている。

ITpro SPECIALPR

What’s New!

経営

アプリケーション/DB/ミドルウエア

運用管理

設計/開発

サーバー/ストレージ

ネットワーク/通信サービス

セキュリティ

もっと見る