名古屋で数学するプログラマ(仮)

@antimon2 が趣味兼一部本職の数学で何かするときのブログ。

もっと「クロッシング問題」(=転倒数計算問題)

一昨日 の続き。

通称「クロッシング問題」(実質「転倒数計算問題」)について、結城 浩 氏からフィードバックが届きました。
(解答投稿した人しか見られないらしいのでURLとか貼れませんのでご了承ください)

その中で、こちらの想定していたアルゴリズム以外のものが紹介されていたので、ちょっと試してみました。

改めて、転倒数計算アルゴリズム

結城氏の紹介していたアルゴリズムは、以下の 3+1 つでした。

  • ナイーブな方法(=バブルソートと同等の素朴な方法、計算量 O(n2)
  • マージソートを使う方法(計算量 O(n log n))
  • 転倒表(逆転表)を使う方法(計算量 O(n log n))
  • (おまけ)BIT を利用する方法

最後の「BIT を利用する方法」を(おまけ)と表記したのは、結城氏は想定しておらず「皆さんの解答でこんなのを利用したものがありました」という紹介をされていたからです(サンプルコードは示されていませんでした)。
私の考えていた「二分探索利用」は端から眼中になかった(笑)模様ですが、そこには私の知らなかったもう一つの方法が与えられていました。

「転倒表(逆転表)*1」というものを利用する方法。

ということで理解のために、自分で改めて書いて動作を試してみました。

転倒表を利用する方法

転倒表とは、2 進数の仕組みを利用して転倒を管理する表、のようです。
その基本概念は、文章で書き下すと以下のような感じ:

  • 比較する 2 数を、同じ桁数の 2 進数表記(先頭 0 埋め)で考える。
  • 上位ビットから順に、以下を確認する。
    • ビット値が同じなら次のビットを見る。
    • ビット値が異なり、左が 1 で右が 0 なら「転倒」の状態である。

これを利用して、実際のアルゴリズムは以下のような感じ:

  • 上位 k ビットが同じ数どうしをグループにまとめる。
  • そのグループ内の各数で、k+1 ビット目を見て以下を処理:
    • 1 ならば、転倒表の値に 1 を加算する。
    • 0 ならば、転倒表の値(=そのグループ内で、その数より左にあるその数より大きな数の個数)を転倒数に加算する。

これを最大ビット数(= 2 進数表記したときの最大桁数)だけ繰り返すので、計算量は O(n log n) となる、というわけです。

実際に私の言葉でプログラムに書き下ろし直してみました*2

今までに作ったプログラムと速度比較してみました。

Ruby 二分探索版 マージソート 転倒表版 BIT 版
1.8.7 17.37s 10.34s 3.98s 4.08s
1.9.3 11.06s 2.24s 2.08s 1.34s
2.0.0 10.85s 1.94s 1.48s 0.91s

Ruby1.9.3、2.0.0 では、BIT 版には及ばないもののマージソート版よりは高速なことが見て取れます。
マージソート版と結果的にやってることがかなり似ていて、コードが比較的シンプルなので、それは想像の範囲内ですね。

ところがなんと、Ruby1.8.7 では BIT 版より高速に動作しています。0.1 秒差は誤差の範囲でしょうか?
いいえ、ちょっと考えたら、その理由は見えてきました。メソッド呼出のオーバーヘッドです。

BIT 版を改良してみた

私の作った解答プログラムの BIT の実装は、可読性や構造・振る舞いを考えて BIT を丁寧にクラス化したものですが、スピードを求めるならそんなに馬鹿丁寧に作る必要はなかったんですね。
元々私が作ったその他の没プログラムも、改良の余地はありながら深入りせずそのままにしていたわけですが、せっかくだからこの BIT 版だけでも改良しとこうかな*3、と思い立ちまして。

ということで。改良しました。主な方針は「インライン化」。

ポイントは、BIT 本体の配列をそのままローカル変数で扱い、read/update の動作もそのまま記述し、直接転倒数を計算。
まー見てくれや可読性をもっと犠牲にしてもっと最適化することもできるんですけど、取り敢えずこれで速度比較。

Ruby 二分探索版 マージソート 転倒表版 BIT 版 BIT 版(改)
1.8.7 17.37s 10.34s 3.98s 4.08s 3.85s
1.9.3 11.06s 2.24s 2.08s 1.34s 1.24s
2.0.0 10.85s 1.94s 1.48s 0.91s 0.83s

見事、転倒表版にも勝ちました(^-^)
いや、勝ち負けはあまり大きな意味は無いんですけれどね。
でもクロッシング社の担当者様に気に入っていただけるためには、少しでも高速に動くアルゴリズム(とその実装)の方が望ましいのではないかと(^-^)

さらなる展望?

あと、結城氏のフィードバックの中に、@ 氏のスライドの URL が含まれていました。
http://www.slideshare.net/tmaehara/inversion-counting
これによると、おそらくさらに高速な、計算量 O(n log n / log log n) や O(n √(log n)) のアルゴリズムも見つかっている(or 理論的に提唱されている?)ようです。
実際に動作するものがプログラムで実装できるのか、それが本当に高速になるのか、は、ちゃんと調べて実装してみないと分かりません。
でも、夢がありますよねo(^▽^)o

*1:「転倒」も「逆転」も英語の inversion の訳語であり、結城氏は「逆転」の方を使用していましたが、私は「転倒」の方がなじみがあるのでこの記事では「転倒表」で通します。

*2:結城氏の示したサンプルコードをなるべく見ずに書きましたが、結果として処理のメイン部分はほぼ同じになりました。

*3:Ruby1.8.7 というもはやサポート外の過去のバージョンで、とはいえ負けたのがちょっと悔しかったしw