CodeIQ のアルゴリズム問題「交差点をすばやく数えよう！」by @hyuki に解答しました

【2013/09/04 23:00 解答フィードバックを受けて、続編書きました。⇒ もっと「クロッシング問題」（＝転倒数計算問題）】

CodeIQ のアルゴリズム問題（出題者：結城浩氏 @hyuki）にまた挑戦してきました。

挑戦者求む！【アルゴリズム】交差点をすばやく数えよう！ by The Essence of Programming 結城浩│CodeIQ

通称「クロッシング問題」（出題者本人公認）。
約半年前の「チョコ問題」から、結城浩氏の問題にはほぼすべて*1解答しているのですが、今回は個人的にちょっと思い入れがあるので、久々に自分の解答コードを公開してみます。

解答の前に…

転倒数

この問題は、数学的に一言で説明すると「与えられた順列の転倒数を算出する問題」です。
たぶん、そのあたりの詳しい説明は解答のフィードバックで結城氏から与えられると思うので、細かいことは省略します。
一応、転倒数というのを簡単に説明しておくと、以下のような感じです。

a₁, … , a_n を、相異なる n 個の数値 1, … , n からなる順序づけられた数列（＝順列）とするとき、以下で表される順序対の個数を『転倒数』という：

$#\{(i, j)|1\le i \lt j \le n; a_i \gt a_j\}$

すなわち、「i < j であって、a_i > a_j であるような (i, j) の組の総数」のことである。

より厳密な定義とかは例えば wikipedia:転倒_(数学) とかを参照してください。

で。
これをそのまま計算しようとすると、すぐに思いつく方法は、
「配列の左から順に、その数より左にその数より大きい数がいくつあるかを数えて、それを全部足す」
ということなのですが、これは容易に想像がつくように、バブルソートと同じアルゴリズムであり、計算量は O(n²) となります。情報量が多かったらとてもじゃないけど現実的な時間内に解くことは出来ません。
そこで、「転倒数算出の高速化（アルゴリズムの選定）」が必要になる、というわけですね。というのが、この問題。

転倒数を算出するアルゴリズム

私が試したのは、以下の 3 つです。

二分探索（binary search）を利用したもの
マージソートを利用したもの
Binary Indexed Tree (Fenwick Tree) を利用したもの

最終的に採用し提出した回答コードは、最後の「Binary Indexed Tree を利用したもの」になりますが、それ以外の 2 つも順に説明していくことにします。

二分探索を利用したもの

「二分探索」は、「その数より前にあるその数より大きな数の個数」を算出するのに、「今までに出てきた数をソート済（降順ソート）で用意して index を求める」てことすればいいじゃん、と思い立って試行。

実際に組んだコードが以下です：

# -*- coding: utf-8 -*-
# bots_answer_1.rb

# == 開始時間計測 ==
tm1 = Time.now

# == 二分探索（逆順ソートされた配列に対して挿入位置 index を返す） ==
def find_index_b_r arr, n
  return 0 if arr.empty? || arr[0] < n
  return arr.size if arr[-1] > n
  lb, ub = 0, arr.size
  loop do
    return ub if ub == lb + 1
    m = arr[i = (lb+ub)>>1]
    # return i if m == n
    if m > n
      lb = i
    else
      ub = i
    end
  end
end

# == Main ==
# ファイルを読み込みながら転倒数を順次計算
inv = 0
a = []
File.foreach("crossing/crossing.txt") do |line|
  next if line.chomp.empty?
  n = line.to_i
  inv += i = find_index_b_r(a,n)
  a[i, 0] = n
end

# == 終了時間計測 ==
tm2 = Time.now

# == 結果出力 ==
puts "#{inv},#{(tm2-tm1).floor}"
puts "ENV: Ruby"
puts

結果はちゃんと得られましたが、かかった時間は約 11 秒（実行環境は、Mac OS X 10.8.4, Core i7 2.7GHz, Ruby 2.0.0-p247。以下同）。毎回ソート済の配列を利用する（配列に随時値を挿入していく）のが一番ボトルネックになった感じです。
上記サンプルコードは普通に Ruby の配列を利用していますが、配列ではなく線形リスト（連結リスト）を実装して利用すれば挿入は少しマシになるかもしれません。けれどそれでも、二分探索自体も、いくら O(n log n) とは言え、要素数が多いとそれなりに負荷がかかっているような感じでした。
ので、この方向性はとっとと諦めました。

マージソートを利用したもの

バブルソート以外で、転倒数が計算できるような高速ソートアルゴリズムはないか？と探していて見付けたのが、「マージソート」。
元の配列を A と B に分割して、A, B それぞれを何らかの手段でソート状態にして、それをソート順を満たすようにマージする、その「マージ」フェーズで、「A からの要素を抽出するときに、それより先に B から抽出した要素がいくつあるか」を数えると、その合計が転倒数になります。計算量は O(n log n)。
コードはこちら：

# -*- coding: utf-8 -*-
# bots_answer_2.rb

# == 開始時間計測 ==
tm1 = Time.now

# == マージソートしながら転倒数計算 ==
def calc_inv_with_mergesort arr
  # 転倒数
  inv = 0

  # マージフェーズ
  _merge = lambda do |arr1,arr2|
    sz1, sz2 = arr1.size, arr2.size
    result = Array.new(sz1 + sz2)
    a, b = arr1[0], arr2[0]
    i = j1 = j2 = t = 0
    loop do
      if a <= b
        inv += t  # 転倒数に加算
        result[i] = a
        i += 1
        break unless (j1 += 1) < sz1
        a = arr1[j1]
      else
        t += 1  # 転倒数に加算する値を加算
        result[i] = b
        i += 1
        break unless (j2 += 1) < sz2
        b = arr2[j2]
      end
    end
    while j1 < sz1
      inv += t  # 転倒数に加算
      result[i] = arr1[j1]
      i += 1
      j1 += 1
    end
    while j2 < sz2
      result[i] = arr2[j2]
      i += 1
      j2 += 1
    end
    result
  end

  # マージソート本体
  mergesort = lambda do |arr|
    return arr if (sz = arr.size) <= 1
    arr2 = arr.pop(sz >> 1)
    _merge[mergesort[arr],mergesort[arr2]]
  end

  # マージソート実施
  mergesort[arr.dup]

  # 算出された転倒数を返却
  inv
end

# == Main ==
# STEP1. ファイル読み込み
arr = File.foreach("crossing/crossing.txt").map(&:to_i)

# STEP2. 転倒数計算
inv = calc_inv_with_mergesort arr

# == 終了時間計測 ==
tm2 = Time.now

# == 結果出力 ==
puts "#{inv},#{(tm2-tm1).floor}"
puts "ENV: Ruby"
puts

結果は 2 秒弱。指定の目標値 3 秒未満は達成。
割と高速ではありますが、これはどう考えても CPU のおかげ。少しスペックの低いマシン（Core i5 1.6GHz）で実行すると簡単に 3 秒超えました。
やはり「実際にソートしながら」という部分にどうしても負荷がかかってしまい、これ以上の抜本的な高速化はあまり望めないな、別のソートアルゴリズムでも状況はそう変わらないだろう、という結論に。

Binary Indexed Tree を利用してみた

そこでもっと根本的に違うアルゴリズムを探して、見付けたのが、Binary Indexed Tree（google:Binary Indexed Tree）（以下 BIT と略記）。
これは累積度数を算出するのに適したデータ構造で、構造もシンプルで累積度数の算出も高速。これを利用して、「配列を最後尾から走査（値を a に代入）して、BIT から 1 〜 a の累積度数を算出（⇒この合計が転倒数になる）してから、BIT に a を登録」という方法*2を取ることに。
結果は見事、1 秒未満。Core i5 1.6GHz でも 1 秒台。ということで、解答にはこれを採用しました。
解答コードは gist に上げました。最後に埋め込みます。

スピードについての考察

ちなみに、二分探索版・マージソート版・BIT 版ともに、特に難しいことしてないので、Ruby1.9.x はもちろん 1.8.7 でも動作します。
ということで、比較してみました。/usr/bin/time -l コマンドで計測（CPU時間を採用）：

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

Ruby1.8.7 の結果を見れば、BIT 版がいかに高効率か（結果として高速か）、ということがよく分かりますね。
またどの列を見ても、Ruby1.8.7>>Ruby1.9.3>Ruby2.0.0 という分かりやすい結果。Ruby2.0 でかなり高効率化・高速化されたと聞いていましたけれど、その成果がこんなにも如実に現れるとは、とちょっと感動。
またもっと低レベルな言語で同じ処理を記述すれば、もっと高速に動作するんだろうな、と素直な感想。

ということで満足してこれを解答として提出したわけです。
けれど、もっと効率の良いアルゴリズムとかデータ構造とかあるのかな。結城氏のフィードバック解説に期待o(^-^)o

解答（言語：Ruby）

お待たせしました。最後に、提出した私の解答プログラムを公開します。

BIT は仕様を見て自分で実装しました*3が、シンプルですよね。これで期待した動作が高速に得られる。今回は良い収穫でした(^-^)

*1:所謂「ウチに来ない？」問題は解答提出していない or 解いていないのですがそれ以外の結城氏の問題はすべて解答しています

*2:先ほどまでは「その数より左にその数より大きな数がいくつあるか」を数えていて、こちらは「その数より右にその数より小さな数がいくつあるか」を数えていますが、どちらも転倒数の計算として結果は同じになります。

*3:正直に言うと http://d.hatena.ne.jp/naoya/20090606/1244284915 で公開されている Perl のソースをほぼそのまま Ruby に移植しただけです(^-^;

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

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