最近傍グラフを用いた類似文字列検索の実験に失敗した話

アルゴリズム

前々から、LSHとか最近傍探索に興味があったので、下記の論文をちょっと実装してみた。 面倒なので、ちゃんとした評価はしていない。

  1. Efficient K-Nearest Neighbor Graph Construction for Generic Similarity Measures (WWW 2011)
  2. Fast Approximate Nearest-Neighbor Search with k-Nearest Neighbor Graph (IJCAI 2011)

1の論文は、最近傍グラフを近似的に計算するもの。2の論文は、最近傍グラフを元に、クエリと一番近傍の点を近似的に探索するというもの。 1の論文については、PFI Research blogに解説があるので、詳しくはそちらを参照されたい。 2の論文については、既に構築済みの最近傍グラフから、ランダムに１点抽出し、その近傍の中で一番類似度が高いものを調べ、そのさらに近傍を調べ・・・というのを繰り返すというシンプルなもの。すごく簡単なアイディアなので、この論文がIJCAIに通ったのは、手法の理論的な分析がよくできてたからなんだろうなーと思う。

 

これらの論文の面白いところは、類似度関数に任意のものを利用できるという点。 そこで、cosine類似度や、Jaccard係数のように集合をベースとした類似度計算ではなく、編集距離を用いて計算してみた。個人的にはtree kernelの最近傍探索とかが面白いかな？とか思ってた。

実装上は、類似度関数を簡単に切り替えられるようにしてあるので、もともとは類似文字列検索ではなく適当なリコメンドエンジンにしようかと思ったんだけど、ちょっと試すのに楽なように文字列を対象にした。

 

で、結果だけど、類似文字列検索をやるのであれば、SimStringやapporoを使った方がいい。

レコメンドエンジンとしてはどうなのかなー。 たまに一番近いアイテムを取り逃すことがあるので、それはビジネス的に嬉しくなさそうだとは思った。

もちろん、素直にO(n2)使って最近傍グラフを作るよりは、ずっと高速に近傍グラフの作成及び検索が可能だけど、精度がやっぱり近似ということもあって少し残念。 (もちろん、構築&検索速度を落とせば精度は高くなるが、それだとあまり意味がない)

 

具体的にソースコードと実行結果は以下のような感じ。

ソースコード(github)

# コンパイル
$ g++ -O2 nng_builder.cc -o nng_builder
$ g++ -O2 nns.cc -o nns  

# 最近傍グラフの構築 (対象のファイル名 linux.words)
$ ./nng_builder linux.words > /dev/null

# 最近傍グラフの探索
$ ./nns linux.words "test"
test,100000 west,99999 vest,99999 text,99999 tent,99999 rest,99999 pest,99999 nest,99999 lest,99999 jest,99999 

$ ./nns linux.words "ARPA"
Anne,99997 Agee,99997 trap,99996 tool,99996 tons,99996 sulk,99996 step,99996 spot,99996 scan,99996 ring,99996

まぁ、とりとめもないエントリでしたが、成功した話でもないしただの記録ということで。

Emacsで開発環境を整える

emacs

背景と動機

Emacsはエディタではない。環境である。

最近のIDEは非常に優秀で、IDEを使うか使わないかで生産性に大きな差が出てしまう、そういう状況が整いつつあるのかなという気がしています。 それでもやはり、動作の軽さやきめ細かいカスタマイズ性にひかれて、今でもEmacsを僕は愛用しています。Emacsはエディタであるにも関わらず、非常に高機能かつ多彩なカスタマイズが可能なため、人によっては「エディタではない、環境である」と主張する人もいます。実際、各種パッケージを導入することで、WebブラウジングやIRCなど驚くほど多彩な機能が利用可能です。

そんなEmacsを使い続けて何年か経ち、設定ファイルもいろいろ貯まってきたので、今後気が向いた時に、Emacsでこんなこともできるよ!ということを紹介したいと思います。

ビルドと実行プロセスを簡略化するパッケージ

プログラミングを行う際、基本的なプロセスとして、主に「コードを書く」=>「コンパイル」=>「実行(デバッグ)」を繰り返すこととなります。今回はそのプロセスを簡略化するためのEmacsパッケージを紹介したいと思います。

yasnippet

コードを書くということを劇的に改善してくれるのがyasnippetです。 使い方を誤ると、コードクローンがそこら中に作られるよくないパッケージですが、よくあるイディオムを登録しておくと、毎度書く際の面倒臭さを軽減してくれます。

基本的なアイディアはdabbrev等と同じように略語を入力したらその略語を展開してくれるだけです。例えば、mainまで入力して「TAB」を押すと下記のようにコードが展開されます。

main[TAB]

==> 
int main(int argc, char *argv[])
{
  
  return 0;
}

僕は、下記のように設定しています。

;; yasnippet
;; http://code.google.com/p/yasnippet/
(when (locate-library "yasnippet-bundle")
  (require 'yasnippet-bundle)
  (setq yas/root-directory "~/.elisp/yasnippet/snippets")
  (setq yas/use-menu nil)
  (yas/initialize)
  (yas/load-directory yas/root-directory)
  ;;(setq yas/prompt-functions '(yas/x-prompt yas/dropdown-prompt))
  (setq yas/prompt-functions '(yas/dropdown-prompt)))

Flymake

最近のIDEは、文法間違いがあるとリアルタイムに指摘してくれます。その機能をEmacsで実現するのがFlymakeです。僕が使っている設定を下記に示します。 この設定をONにすると、C++のプログラムを書いている時にコンパイルエラー等があったらその箇所だけ赤く表示され、その箇所で「Ctrl+c d」というショートカットを使うとミニバッファにエラー内容が表示されます。 この機能を有効にしてからというもの、「プログラムを書く」=>「コンパイル」=>「コンパイルエラー」=>「プログラム修正」という繰り返しがなくなり、コーディング速度が上がったように思います。

;; flymakeパッケージを読み込み
(require 'flymake)
;; 全てのファイルでflymakeを有効化
(add-hook 'find-file-hook 'flymake-find-file-hook)

;; miniBufferにエラーを出力
(defun flymake-show-and-sit ()
  "Displays the error/warning for the current line in the minibuffer"
  (interactive)
  (progn
    (let* ((line-no (flymake-current-line-no) )
           (line-err-info-list (nth 0 (flymake-find-err-info flymake-err-info line-no)))
           (count (length line-err-info-list)))
      (while (> count 0)
        (when line-err-info-list
          (let* ((file (flymake-ler-file (nth (1- count) line-err-info-list)))
                 (full-file
                  (flymake-ler-full-file (nth (1- count) line-err-info-list)))
                 (text (flymake-ler-text (nth (1- count) line-err-info-list)))
                 (line (flymake-ler-line (nth (1- count) line-err-info-list))))
            (message "[%s] %s" line text)))
        (setq count (1- count)))))
  (sit-for 60.0))
(global-set-key "\C-cd" 'flymake-show-and-sit)

;; flymakeの色を変更
(set-face-background 'flymake-errline "red4")
(set-face-background 'flymake-warnline "dark slate blue")

;; Makefile が無くてもC/C++のチェック
(defun flymake-simple-generic-init (cmd &optional opts)
  (let* ((temp-file  (flymake-init-create-temp-buffer-copy
                      'flymake-create-temp-inplace))
         (local-file (file-relative-name
                      temp-file
                      (file-name-directory buffer-file-name))))
    (list cmd (append opts (list local-file)))))

(defun flymake-simple-make-or-generic-init (cmd &optional opts)
  (if (file-exists-p "Makefile")
      (flymake-simple-make-init)
    (flymake-simple-generic-init cmd opts)))

(defun flymake-c-init ()
  (flymake-simple-make-or-generic-init
   "gcc" '("-Wall" "-Wextra" "-pedantic" "-fsyntax-only")))

(defun flymake-cc-init ()
  (flymake-simple-make-or-generic-init
   "g++" '("-Wall" "-Wextra" "-pedantic" "-fsyntax-only")))

(push '("\\.c\\'" flymake-c-init) flymake-allowed-file-name-masks)
(push '("\\.\\(cc\\|cpp\\|C\\|CPP\\|hpp\\)\\'" flymake-cc-init)
      flymake-allowed-file-name-masks)

mode-compile

mode-compileはEmacsに元々あったコンパイル機能を改善するパッケージです。 下記の設定をすることにより、ショートカット「Ctrl-c c」を使えば適切なコマンドを自動的に選択してコンパイルを行ってくれます。 実行されるコマンドはメジャーモードを元にしており、cperl-modeであればperlを実行し、c++-modeであれば「g++」 c-modeであれば「gcc」を使ってくれます。

;;;; mode-compile
(autoload 'mode-compile "mode-compile"
  "Command to compile current buffer file based on the major mode" t)
(global-set-key "\C-cc" 'mode-compile)
(autoload 'mode-compile-kill "mode-compile"
  "Command to kill a compilation launched by `mode-compile'" t)
(global-set-key "\C-ck" 'mode-compile-kill)

;; 全てバッファを自動的にセーブする
(setq mode-compile-always-save-buffer-p t)
;; コマンドをいちいち確認しない
(setq mode-compile-never-edit-command-p t)
;; メッセージ出力を抑制
(setq mode-compile-expert-p t)
;; メッセージを読み終わるまで待つ時間
(setq mode-compile-reading-time 0)

;; コンパイルが完了したらウィンドウを閉じる
(defun compile-autoclose (buffer string)
  (cond ((string-match "finished" string)
         (message "Build maybe successful: closing window.")
         (run-with-timer 0.3 nil
                         'delete-window
                         (get-buffer-window buffer t)))
        (t (message "Compilation exited abnormally: %s" string))))
(setq compilation-finish-functions 'compile-autoclose)

carun

ふと思いたって、自分で書いてみたelispです。 名前をつけてみましたが、パッケージのインストールは必要なく、下記のelispを直接.emacsに張り付ければOKです。

本格的にデバッグを行う時にはEmacsには「gdb」フロントエンドが入っているため、「M-x gdb」とコマンドを実行するとデバッガが起動されます。

ですが、printfデバッグで十分な時もあり、そういう場合はとにかく同じコードを細かく修正し、何度も実行することがよくあります。「Ctrl-c r」のショートカットを使うと、最初はコマンドを確認しますが(ディフォルトはファイル名から拡張子をとったもの)二回目以降は前回と同じコマンドを実行し、実行結果を表示してくれます。 「Ctrl-c Ctrl-r」を実行すると再度コマンドを確認します。

(defun carun-string-matches-internal (str n)
  (if (not (match-beginning n))
      ()
    (cons (substring str (match-beginning n) (match-end n))
          (carun-string-matches-internal str (+ n 1)))))

(defun carun-string-matches (match str)
  (if (not (string-match match str))
      ()
    (cons str
          (carun-string-matches-internal str 1))))

(defvar carun-command nil)
(defun carun-shell-command ()
  (shell-command carun-command "*Shell Command Output*" nil)
  (run-with-timer 1.0 nil
                  'delete-window
                  (get-buffer-window "*Shell Command Output*" t)))

(defun carun-exec ()
  (interactive)
  (let* ((carun-names (carun-string-matches "\\([^/]+\\)\\.\\([^\\.]+\\)$"
                                (buffer-file-name)))
         (carun-file (nth 1 carun-names))
         (carun-ext (nth 2 carun-names))
         (carun-comm (if carun-file (concat "./" carun-file) ""))
         (carun-read (read-string
                      "run-command: "
                      (if (not carun-command) carun-comm carun-command))))
    (setq carun-command carun-read)
    (carun-shell-command)))

(defun carun-exec-retry ()
  (interactive)
  (if (not carun-command)
      (carun-exec)
    (carun-shell-command)))

;; ショートカット設定
(global-set-key "\C-cr" 'carun-exec-retry)
(global-set-key "\C-c\C-r" 'carun-exec)

まとめ

コードを書く際に便利なパッケージとして「yasnippet」「Flymake」、コンパイルを簡単にしてくれるパッケージとして「mode-compile」、プログラムの実行を簡単にしてくれるパッケージとして「carun」を紹介してみました。

特定の環境に強く依存してしまうと、その環境以外では実力を発揮できないことがあります。こういう状況を「特定環境への過剰適応」と呼んでみます。 こういった「特定環境への過剰適応」を嫌い、カスタマイズ等を基本的にはしないという人もいて、その気持ちもよく理解できます。

例えば僕自身、サーバ設定等の作業を行う場合には、Emacsが入っていないことも多いので、カスタマイズなしの「vim」や「vi」を使うことがあります。そういった場合に「Emacsじゃないので実力が発揮できない」、と言うのは言い訳にしかなりません。

しかし、カスタマイズをすることで、生産性を50%上げることができるのであれば、それもまた自分の実力であり、時と場合に応じて積極的に利用するべきだと僕は思います。

社会人からのTopCoder SRM参加のススメ

TopCoder

先行き不安ながらもなんとかDiv1で戦うことができるようになったのを記念して、TopCoderに参戦してからこれまでのことを、つらつらと振り返りたいと思います。まぁこれが読まれる頃には次のSRMに参加してDiv2に落ちているかもしれないのですが・・・。

最初の一歩

一番最初にTopCoderにユーザ登録したのは３年以上前の学生時代の頃でした。 その頃に一度SRM(シングルラウンドマッチ)の過去問を解いてみて、2,3問ほど解くのに１日ぐらいかかったように思います。

SRMというのは、問題が出題され、アルゴリズムを考え、コーディングして解くまでのスピードを競うゲームです。 (どういう問題が出題されるかというのは、TopCoder参戦記の方に問題の概要を張ってあるので参考にしてください。) 一回あたりEasy,Medium,Hardの三問出題され、各問題を解くごとに、解いた時間と難しさを考慮したポイントがもらえます。

その時は本番は何分かけて戦うかも理解していませんでしたが、時間がかかりすぎているということは確実でした。 とりあえず練習してからだなと思い、その時は本戦参加をあきらめてしまいました。 それからも過去問を解こうと思うことは何度かあったのですが、本格的に解いたことはしばらくなかったように思います。

動機

そもそも、僕がTopCoderを始めようと思ったのは、強い苦手意識からでした。 大学はICPCなんかの大会や情報オリンピックがあることさえ知らない非情報系だったということもあって、競技プログラミングについてコンプレックスがありました。

もちろん、TopCoderのような競技プログラミングで行うようなアルゴリズム（幅優先探索だったりDPだったり）が、すぐに業務に役立つかというとそうでもなかったりするのですが、僕の知る限り、競技プログラミングのような問題を解ける人間は技術者としてできる人であることが多く、情報系分野の進路を取った人間としては避けていてはいけないのではないか、と思うことがありました。 その気持ちは、社会人として働き始めてからも心のどこかに引っかかっていたのですが、ちゃんと勉強しなきゃと思いつつも時間がたってしまっていました。

まぁ、そんなこんなで、今でもそうなのですが、目標は日本で○○位以内とか非常に高い望みは持っていません。 そこそこアルゴリズムが解けるよというレベルになって、プログラミングが早くなればそれでいいと思ってたりします。

TopCoderリターンズ

そうやってしばらくTopCoderから離れてしまってから、再度TopCoder熱が再燃したのは、社会人になって会社の同僚とTopCoderの勉強会をしようという話をしてからでした。 時間的にSRMの本戦に参加するのは現実的ではなく、また、本戦は敷居が高く感じていたこともあり、みんなで過去問を解こうということで話はまとまりました。

それからしばらくの間、音頭をとる人間もいなくて時間がたってしまったのですが、最近会社にマイノートPCを持ち込み可能となったりと、勉強会をしやすい環境になったこともあり、「明日からやろう」と強い気持ちで再度誘ってみたのがTopCoder勉強会の始まりでした。

勉強会開始

11月ぐらいから1週間に一度ということで始めました。 上で書いたようにみんなTopCoderに不慣れでしたし、参加者の何人かはアカウントも持っていなかったので、まずはアカウントを取るところからでした。

今なら下記のリンクが参考になると思います。 TopCoderはじめました(今更 TopCoderアカウント登録、SRM(Single Round Match)解説

その後希望者はTopCoderのプラグインを設定して、過去問を解き始めました。 雑記/TopCoderでプラグインを導入してコーディング時間を短縮する

TopCoderのホームページからArenaを立ち上げてPractice Roomから、以下の計算式で解く問題を決めます。

    本日の日付(20110201)を現在のSRMの試合番号(712)で剰余を取った値
    例)  20110201 % 712 = 473 = SRM 381 Div2

みんなで解けるところまで45分から50分程で解いて、システムテストと言われる問題の出題者があらかじめ用意したテストが通るかを確認します。残りの時間で他のみんなはどう解いてるか答え合わせしたりして確認します。

SRMのルール

で、いよいよ始めようとしたのですが、勉強会を始めた当時は、Div1とかとDiv2の区別、システムテストって何？という状態でした。 幸い勉強会１回目には参戦経験豊富なTさんが顔を出してくださって、基礎的なことは把握できました。

まずSRMに参加すると、参加者はDiv1とDiv2に分かれます。 Div1が難しい問題を解く方で、Div2が少し易しめの問題を解く方です。 初心者はまずDiv2に参戦することから始まり、そこでいい成績を出せればDiv1で戦うことができるようになります。

Div2からDiv1へ移行するのはレーティングという各参加者を格付けするスコアで判断されます。 このスコアによって、いわゆるレッドコーダーなどの参加者の色も決められ（赤 => 黄 => 青 => 緑 => 灰)の順に下がっていきます。 Div1はレーティングが1200より上、ブルーコーダー以上が参加できます。

初参加者はレーティングが1200と扱われ、最初に参加する時はDiv2の問題を解かされます。 ここで上位に食い込むことができれば初参加からDiv1へ、そうでなければDiv2でしばらく戦うことになります。

TopCoderに参戦開始

もともとは、半年ぐらい？勉強会なりなんなりを続けて、自分に自信がついてからSRM本戦に参加しようと考えていました。 けれど、気が付いたら一緒に勉強会を行っていたMさんが先に本戦に参加され、しかも最初からかなりいい成績を叩き出しました。 確かにMさんならやっぱりなぁとは思うところがあったのですが、話を聞くと２問解いて3問目は解けなかったけどなんとかなったということでした。それまで３問全部解けないとダメなんだろうなーと思っていたこともあり、2問でいいんだ！ということを知って、俄然参加する意欲が湧きました。 (もちろん、自分もそこそこのところまでは行くんじゃないか？という淡い期待もありました。)

本戦のコーディング時間は1時間15分なのですが、これをEasy Mediumの２問で使うとすると、それぞれ15分、60分と十分な時間をかけることができます。 TopCoderというと、おかしなぐらい高速にコーディングする人たちがいて、とてもスピード勝負ではかなわないと思っていたのですが、1問に1時間考えていいのであればコーディングはそれほど速くなくても問題ありません。

参戦してから

最初に参加したSRMでは、250は解けたのですが、500点の問題がChallengeされあっけなく撃墜されました。 撃墜されると0点になります。部分点ぐらいくれるのかな？と甘い考えを持っていたのですが、厳しい現実を味わいました。 結果 Div2 1042人中645位で、まぁ自分の実力がよくわかりました。 そしてレーティングが初めてふられ、グリーンコーダーとなりました。

最初が1200とすると、1200 -> 988 と下がったことになります。 まぁ、ある意味自分の実力として当然ではあったのですが、悔いはいろいろ残ります。

ただ、初参戦がネガティブな気持ちばっかりで散々だったかというと、そうではありません。 凹んだ気持ち自体は次の日にはなくなり、次こそなんとかしようという前向きなモチベーションがガンガン湧いてきました。 モチベーションを維持する報酬として、レーティングは非常に効果的だと、参戦して初めて実感できました。

また、これからレーティングをあげていくために、以下のように考えました。

  1. レーティングは現在のレーティングに依存していて、Div2 の過半数より上の順位であれば少しづつでも増えていくはず。
  2. レーティングは獲得したポイントではなく、ポイントの順位だけから決まるが、時間はかかっても２問解けていれば、Div2のかなり上位に入ることができる
  3. であればコンスタントに2問解けてれば、いつかDiv1にいける

おバカな論理展開です。そもそもEasyとMediumの二問コンスタントに解くというのが難しいということはその後実感しましたが、その時はいけると根拠なく思っていました。

勉強会の効果

そろそろ勉強会初めてから２か月ちょっと経ちますが、合計20問以上は問題を解いていることになります。 勉強会を始める前に比べると確実に力はついたと思います。 具体的には、素直に書けばいいだけ、という問題については、確実に解けるんじゃないか？と慢心できる程度にはなれました。 正直、ひねりが必要だったり、ビットDPなんかの難しいアルゴリズムが使われている問題は、まだ全然解ける気がしないのですが、それはプログラミングコンテストチャレンジブックをお供に解けるようになっていきたいと思います。

また、もう一点間違いないことなのですが、一緒に勉強会をやっている仲間から強く刺激を受けています。 僕個人としては、正直かなり得られるものがありました。これは忘れず書いておきたいと思います。

つい最近、２年かけてレッドコーダーになった人のブログを読んだりしてましたが、やっぱり「継続は力」ですよね。最近は勉強会も若干だれているところがあったりしたのですが、真摯に取り組めば力はついてくるものだと思ってこれからも続けていきたいと思います。

今後の目標

とりあえずDiv1にあがれたので、今後の目標としてはやはりイエローコーダー！・・・は無理なので、そうではなく、とりあえずDiv1に定着できるようになれればなぁと思っています。 そのためにはまず、Div1 Easyの問題をちゃんと解けるようになること、ですね。 解けるように・・・なるよね？

まとめ

  • TopCoderに参加するのは敷居が高いと感じるなら、最初は勉強会などで少しづつ慣れよう
  • TopCoderのSRMに参戦して、レーティングがつけられると、モチベーションが湧く。練習するだけじゃなくて参加してみよう
  • 継続は"力"。やっぱり続けていれば力になってくる。最初は全く解けなくても少しづつでも解けるように頑張ろう

Expression Templateの蛇足的な話

C++

Preface

前にプリプロセサを駆使してシリアライザを書いたことがあったのですが、Expression Template(以下 式テンプレート)を使えば#define使わなくても近いようなことできるなーと思いついたので、実際に作ってみました。

で、そっちを説明しようと思ったんですが、やっぱり気が変わって、式テンプレート自体の自分なりの理解を簡単に説明したいと思います。 ちなみに式テンプレートのちゃんとした入門は、参考URLの方で錚々たる方々が素晴らしい記事を書いているので、そちらを参考にしてください。この記事はまぁ、蛇足的な、自己満足のためのものです。

Introduction

式テンプレートは、最初、行列やベクトルを使った科学計算の効率化のために考案されました。 例えば以下のようにVectorクラスの演算を行うとします。

Vector v_result, v1, v2, v3;
v_result = v1 + v2 - v3;

この時、式テンプレート手法を用いていないVectorクラスの場合、各「+」「-」演算子が評価される度に一時オブジェクトが生成されてしまいます。密ベクトルクラスの場合要素数がdouble型で1万次元やそれ以上が普通だったりするので一度生成される度に8 * 10000 = 約79KBのコピーが発生してしまい、使い物にならないプログラムができあがります。

そこで、一時オブジェクトを生成せずに「v_result = v1 + v2 - v3;」という記述を可能とするのが式テンプレートです。

ただこういう説明から入ると誤解してしまうのですが、式テンプレートは科学計算だけに利用されるものではありません。 (僕も科学計算をするのであればublasなどの既に実装されているライブラリを使えばいいと思って、本の説明も飛ばしてしまうことが多かったです。)

それでは式テンプレートとは何なのか、ということをオレオレ解釈で述べてみると、

C++で制限つきの遅延評価を実現する仕組み

だと思っています。

Imprementation

式テンプレートは2段階の処理に分かれます。 「構築フェーズ」と「評価フェーズ」です。下の図は件の式をフェーズごとに分解した図です。

演算子の優先順位から、まず右辺の構築フェーズが実行され、その後評価フェーズが実行されます。計算を必要な時(評価フェーズ)まで遅延させるのが式テンプレートの目的です。

Construction Phase

構築フェーズは以下のような構文木を作成するフェーズです。

Expというのは一時的に引数と計算方法を保持するプロキシオブジェクトです。 保持といっても参照を保持するだけですので、コピーは行われません。 (また、コンパイラの最適化によって最終的にこのプロキシオブジェクトは削除されますのでオーバーヘッドもありません。)

実際にコードを書くと以下のようになります。 (Vector型は簡単のため、配列ではなくint型を一つだけ保持するようにしています。 またこれ以外のメソッドも本来必要ですが、着目して欲しい箇所だけ抜きだしています。 全体のコードを確認しながら先に進みたい方はこちらを参照)

class Vector {
  int i_;
public:
  Vector(int i) : i_(i) {}

  template 
  Exp operator+(const R &r){
    return Exp(*this, r);
  }
};

template 
class Exp {
  const L &lhs_;
  const R &rhs_;
public:
  Exp(const L& l, const R& r) : lhs_(l), rhs_(r) {}

  template
  Exp, OpMinus, R2> operator-(const R2 &r){
    return Exp, OpMinus, R2>(*this, r);
  }
};

まず右辺の式「v1 + v2 - v3」は+,-演算子が左結合ですので「v1 + v2」が評価され、Vectorクラスのoperator+メソッドが呼ばれます。ここでは、以下のようにExpの一時オブジェクト(以下 Exp<v1, +, v2>のように表記)を返しています。

  template 
  Exp operator+(const R &r){
    return Exp(*this, r);
  }

次に「Exp<v1, +, v2> - v3」が評価されここではExp::operator-が呼ばれます。

  template
  Exp, OpPlus, R2> operator-(const R2&r){
    return Exp, OpMinus, R2>(*this, r);
  }

これで上記のようなExpオブジェクトの入れ子になった構文木オブジェクトをoperator=に渡して評価フェーズが始まります。

Evaluation Phase

次に評価フェーズでは、上記の構築フェーズで作成した構文木を自由に渡り歩くことにより実行されます。 ここで重要なのは評価フェーズでは上記で構築された構文木の、オブジェクト(v1, v2, v3)、それぞれの計算方法(OpMinus, OpPlus)全てにアクセスできるという点にあります。

実際に構文木を渡り歩く処理を書いてみます。 (今回も着目して欲しい箇所だけ抜き出しています)

struct OpPlus {
  static int apply(int i, int j){
    return i + j;
  }
};

struct OpMinus {
  static int apply(int i, int j){
    return i - j;
  }
};

template 
class Exp {
  const L &lhs_;
  const R &rhs_;
public:
  int eval() const {
    return Op::apply(lhs_.eval(), rhs_.eval());
  }
};

class Vector {
  int i_;
public:
  template 
  Vector& operator=(const E& exp){
    i_ = exp.eval();
    return *this;
  }
  int eval() const{
    return i_;
  }
};

まず、「Vector::operator=」から「Exp::eval()」が呼び出され、次に「lhs.eval()」つまりExp<v1, +, v2>を評価します。 Exp<v1, +, v2>::eval()は「OpPlus::apply(v1.eval(), v2.eval())」を評価して返します。 v1.eval(), v2.eval()はそれぞれ自分の持っているデータを返しているだけですので「v1.i + v2.i_」という二つのint型の和を返すことになります。以下同様です。

Application

例えば、式テンプレートを使ったロガーの実装を考えてみるとします。 tkngさんの日記で、google-glogはデストラクタを使うことで、書き出す文字列が確定してから一度に出力するという操作を実現しているという話がありました。

式テンプレートを使えば、

#definee LOG(x)  LogMessage(x).stream() = LogMesage(x).dummy()

int main(void){
  int x = 0;
  size_t z = 3;
  LOG(INFO) << x << "y" << z;
}

のようなコードを書いた場合、LogMessage(x).stream()が返す一時オブジェクトのoperator=が呼ばれる時には、x, "y", zといった書き出すべき文字列が確定しているので、デストラクタを使った場合と同様に一度に書き出すことが可能となります。

デストラクタを使うのではなく、こういった実現方法もあるのではないか、と思った次第でした。 本当にできるかどうかは試していないのでわからないですが、式テンプレートのことを「一時オブジェクトを消す仕組み」と覚えるのではなく、「遅延評価を実現する仕組み」と考えることで応用範囲が広がるんじゃないかと思っています。

Postscript

今回説明に用いたコードはgithubに上げていますので、全体を見たい方はこちらをご確認ください。また最初に話したシリアライザーのコード自体はまだ未完成ですが、この辺に転がしてあります。

boost::lambdaもそうですし、boost::xpresiveなど式テンプレートの手法を利用したライブラリは今後も増えて行きそうですね。 自分で式テンプレート対応のベクトルクラスを作るときはもちろん必要ですし、ライブラリを利用する場合でも、どういう仕組みかどうかを知っておくと、効率的に使えるようになると思います。 (僕はよく知りませんが、boost::protoを使えばさらに書き易くなるようです。)

Refences

参考URL Faith and Brave - C++で遊ぼう: Expression Template 本の虫: Expression Template Cry’s Diary: 日本で一番分かりやすく書いたつもりのExpression Templateの説明 Cry’s Diary: ETの考え方とその簡単な実装 With Unz: Expresion Template

参考書籍

C++テンプレートテクニック C++ テンプレート完全ガイド (Programmer’s SELECTION) C++テンプレートメタプログラミング (Programmer’s SELECTION)

【算術演算小話 その三】 コンパイラの除算最適化

C++ 駄文

最後です。

これも@machyさんから、2の冪乗での除算の場合、intとunsigned intで発行される命令数が違うという話を聞いて、詳しく調べてみた話です。 で、実際に検証するために、以下のコードをコンパイルしてみました。

int main(int argc, char *argv[])
{
  int x = -5;
  return x / 4;
}

xをそれぞれint,unsigned intと変えてコンパイルし、作成されたアセンブリコードのdiffを取ります。

ちなみにコンパイラはgcc-3.4.6(Linux), コンパイルオプションは「-m32 -S」です。 (gcc4系列の場合さらに最適化されてストリング命令を利用するようになるので今回の実験結果には沿いません。)

以下がアセンブリコードのdiffです。 通常除算というとidiv命令やdiv命令が使われるのですが、2の冪乗の場合、コンパイラの最適化によって除算がシフト演算に置き換わります。

@@ -1,23 +1,29 @@
        .file   "printbit2.c"
        .text
 .globl main
        .type   main, @function
 main:
        pushl   %ebp
        movl    %esp, %ebp
        subl    $8, %esp
        andl    $-16, %esp
        movl    $0, %eax
        addl    $15, %eax
        addl    $15, %eax
        shrl    $4, %eax
        sall    $4, %eax
        subl    %eax, %esp
        movl    $-5, -4(%ebp)
        movl    -4(%ebp), %eax
-       shrl    $2, %eax
+       movl    %eax, -8(%ebp)
+       cmpl    $0, -8(%ebp)
+       jns     .L2
+       addl    $3, -8(%ebp)
+.L2:
+       movl    -8(%ebp), %eax
+       sarl    $2, %eax
        leave
        ret
        .size   main, .-main
        .section        .note.GNU-stack,"",@progbits
        .ident  "GCC: (GNU) 3.4.6 (Ubuntu 3.4.6-6ubuntu5)"

int型でコンパイルした場合、確かに条件分岐を含めた結構な命令数が増加しています。 intでコンパイルした時のアセンブリコードを、わかりやすい用にCのコードに直すと、下記のようになります。 (実際コンパイルして見るとほぼ同じアセンブリコードを吐きます。)

int main(int argc, char *argv[])
{
  int x = -5;
  if(x < 0){
    x += 3;
  }
  return x >> 2;
}

なぜか、負の数かどうかをチェックし、負の数の場合は3を足しています。 この謎を解いて行きたいと思います。

まず、3を足さない場合、結果がどうなっていたかを確認してみると、返される戻り値は「-2」になりました。 3を足す場合は「-1」です。 「算術演算小話 その二」で調査した結果、Cでの除算の結果はどちらが正しいかというと、「-5 / 4 = -1」であり、0に近い整数に丸める必要があるので、3を足さなければ仕様に合わなくなってしまうようです。

では次に、3という数字はどこから来ているかについて考えるため、除算の値をいろいろ変えてコンパイルしてみました。 その結果、「32」で割る場合は「31」を足し、「64」で割る場合は「63」を足していました。

これは、実は右シフト演算は常に切り下げ(マイナス無限大方向への丸め)を行ってしまうので、「算術演算小話 その一」で書かれた手法を使ってm-1を足すことによって、0方向への切り上げ処理を行っているようです。 （たぶん合っていると思います)

以上で一連の話は終わりです。 この３回を書くに当たって、個人的には自分の中でちゃんと把握できていない、曖昧だった部分を整理できたので、書いてよかったなーと思っています。 興味深いことをお教え頂いた@machyさん、ありがとうございました。

・【算術演算小話 その一】 倍数への切り上げ ・【算術演算小話 その二】 負の剰余について ・【算術演算小話 その三】 コンパイラの除算最適化

【算術演算小話 その二】 負の剰余について

C++

今回は負の剰余の話です。

剰余は正の数同士の場合は何も問題ないのですが、負の剰余をとってしまうとはまることがあります。 なぜなら言語処理系依存だからです。C++, pythonのそれぞれを比較すると下記のようになります。

(C)       -2 % 5 = -2
(python)  -2 % 5 = 3

計算結果は違っていますが、この二つプログラミング言語の剰余は、両者とも、以下の等式が成り立つような値と定義されています。

 x == (x / y)*y + x%y

つまり剰余の値は、

 x % y = x - (x / y)*y

という式で得られます。

剰余の計算結果が異なっている原因は負の値に対する除算の値が異なるからです。

(C)       -2 / 5 = 0
(python)  -2 / 5 = -1

下のグラフを見ていただければわかると思うのですが、pythonの場合、除算の結果は「x 以下の最も大きい整数」で返しますが、Cの場合は「絶対値で0に近い整数」となります。

  • pythonの場合の除算結果イメージ

  • Cの場合の除算結果イメージ

これは、Cの場合、負の数については切り上げを行い、正の数については切り下げを行うという処理になります。これを0の方向に丸めるといいます。 (ここでの「切り下げ」「切り上げ」の定義は、切り下げが負の無限大方向への丸め, 切り上げは正の無限大方向への丸めです。)

C++では負の除法に対する定義は処理系定義となっていますが、C99で除算した場合は0方向へ丸めると定義されているためそれに従うのが一般的のようです。

Cでpython形式の剰余を使いたいという場合は以下のように定義すれば良いのではないかと思います。

int imod(int i, int j){
  if(j < 0){
    return (i < 0) ? -(-i % -j) : (i % -j) + j;
  }else{
    return (i < 0) ? -(-i % j) + j : i % j;
  }
}

最初は条件分岐を無くそうとしたのですが、残念ながら難しいようでした。

これはj > 0かつ除算が0方向に丸められるという前提をおくと、以下のように簡単化できます。 つまり負の値の剰余に対しては、忘れずにjを足すと覚えれば大丈夫なようです。

int imod(int i, int j){
  return i % j + (i < 0 && -i != j) ? j : 0;
}

これは、例えば以下のような問題を解く時に便利かなと思いました。

問題設定: 現在時刻が与えられた時に40分前の時刻を返しなさい。

python形式の剰余を使うと、よりシンプルにかけるようになる気がします。

int hour = 2;  int min = 27;
min -= 40;
if(min < 0)
    hour = imod(hour - 1, 24);
min = imod(min, 60);
printf("%02d:%02d\n", hour, min);

参考URL

負の剰余については以下を参考にしました。 bkブログ: こんなプログラムはいやだ: 負の剰余 jikkenjo.net: マイナスの剰余計算 JPCERT コーディネーションセンター: INT10-C. % 演算子を使用する際、結果の剰余が正であると想定しない 端数処理 - Wikipedia pythonの仕様書 C++の仕様書

また作成したグラフはwikipediaの床関数のグラフの作り方を参考にさせて頂きました。

・【算術演算小話 その一】 倍数への切り上げ ・【算術演算小話 その二】 負の剰余について】 ・【算術演算小話 その三 】コンパイラの除算最適化

【算術演算小話 その一】 倍数への切り上げ

C++

パイプライン処理といった技術の発達した最近のCPUでは、条件分岐を減らすことで最適化が可能な場面があります。

こういった場合に稀に利用されるのが、算術演算を利用したテクニックです。 算術演算を上手く利用することで、場合によっては必要だった条件分岐も削減可能なことがあります。 そんな算術演算の重要性の高まりを受け、今日から3回に分けて算術演算に関する話をしたいと思います。

まぁ、そういったこじつけ的な背景説明はともかく、@machyさんに教わったテクニックを僕の中だけにおさめておくには勿体無いなぁと思ったのが本当の動機です。

例えばプロセスのメモリ使用量をKB単位で表示したいとします。 こういった場合、実際のメモリ使用量は1500バイトでも、多めに見積った方が好まれるため、1024の倍数に切り上げて2048/1024で2KBと表示します。 ではこの倍数への切り上げ処理を素直に書いてみます。

//nをmの倍数に切り上げる関数
size_t _ceil(size_t n, size_t m){
    if(n % m == 0)
      return n;
    else
      return (n / m + 1) * m;
}

条件分岐が入ってしまいましたし、ちょっと関数化しないとこの処理を毎回書くのは面倒です。 一応次のように一行で簡素には書けますが……条件分岐を消すことができません。

1.    n = (n % m) ? (n / m + 1) * m : n;
2.    if(n % m) n = (n / m + 1) * m;

で、教えてもらったのが以下のイディオムです。

size_t _ceil(size_t n, size_t m){
    return (n + m - 1) / m * m;
}

パフォーマンスとしては、条件分岐を使った場合と結局あまり変わらないかもしれませんが、あらかじめm-1を足してやるだけで条件分岐がなくなるスマートな解だと思います。

次回、次々回は以下の記事を書く予定です。 ・【算術演算小話 その二】 負の剰余について ・【算術演算小話 その三】 コンパイラの除算最適化