クロッシング問題を解いてみた

CodeIQにあったクロッシング問題。

この前のNiigata.rbの懇親会でも話題になったので、 このためにCodeIQのアカウント作ってやってみたら、 もう締めきりになっていたので、 個人的にやってみました。

元ネタはこちら。

実行環境

考え方1

まずは、以下のように考えてみました。

  1. 素子数分の要素を持つ配列aを作成する。
    • [1,2,3,…,n]
  2. ファイルの素子番号順に、binary searchをして配列aのindexを得る。
    • indexは 0..n-1ですね。
  3. 配列aから要素番号に該当する要素を削除する
  4. 各々得られたindexを加算すると、求める値が得られる。

コードは以下。

start_time = Time.now

def bsearch(ary, key, left, right)
  return nil if left > right
  mid = (left + right) / 2
  key < ary[mid] ? (right = mid - 1) : (left = mid + 1)
  key == ary[mid] ? mid : bsearch(ary, key, left, right)
end

fname = "./crossing.txt"

File.open(fname, "r") do |f|
  j = f.read.count("\n")
  f.rewind

  tops = [*1..j]
  cross = 0
  f.each do |line|
    n = line.chomp.to_i
    j -= 1
    i = bsearch(tops, n, 0, j)
    cross += i
    tops.delete_at(i)
  end

  puts cross
end

puts Time.now - start_time

交差点数は24,689,222,839。
実行速度は約9.9秒。

プロファイリングをすると、やはり、binary search と delete_at で時間がかかっています。

別のアルゴリズムを考える必要がありそうです。

考え方2

出力元と出力先の素子番号が同じように並んでいるのであれば、交差点はありません。 しかし、そのうち2つが入れ替わっていると、交差点は1つ発生します。

そこで、出力先の素子番号のファイルを読み込んで それがソート中に数値が入れ替わった分が交差点数になると考えました。

今回はマージソートでやってみました。

コードは以下。 マージソートの部分はWikipediaからパクりました。(^^)

start_time = Time.now
@cross = 0

def merge_sort lst
  return msort lst.dup
end

def msort lst
  return lst if (len = lst.size) <= 1

  lst2 = lst.pop(len >> 1)
  return merge(merge_sort(lst), merge_sort(lst2))
end

def merge lst1, lst2
  len1, len2 = lst1.size, lst2.size
  result = Array.new(len1 + len2)
  a, b = lst1.first, lst2.first
  i, j, k = 0, 0, 0

  loop do
    if a <= b
      result[i] = a
      i += 1; j += 1
      break unless j < len1
      a = lst1[j]
    else
      @cross += (len1 + k - i)
      result[i] = b
      i += 1; k += 1
      break unless k < len2
      b = lst2[k]
    end
  end

  while j < len1 do
    result[i] = lst1[j]
    i += 1; j += 1
  end
  while k < len2 do
    result[i] = lst2[k]
    i += 1; k += 1
  end

  return result
end

fname = "./crossing.txt"

a = []
File.open(fname, "r") do |f|
  f.each do |line|
    a << line.chomp.to_i
  end

  merge_sort a
  pp @cross
end

puts Time.now - start_time

交差点数は24,689,222,839。
実行速度は約1.7秒。

これで、速度要件は満たしました。 でも、クロッシング社の要求は速ければ速いほどいいということなので、 もっと速いアルゴリズムを考えた方がいいのでしょうけれど、 とりあえずこれまでとします。

JRubyで実行してみる

考え方1をJRuby 1.7.4(1.9.3p392)で実行してみると、 実行速度は約6.8秒。

考え方2を同じようにJRuby 1.7.4で実行してみると、 実行速度は約2.4秒。

考え方1はJRubyが速いけど、考え方2はRubyが速いのは、なかなか興味深いですね。

まとめ

結局、解答は提出できなかったので、本当にあっているのかどうかはわかりません。 また、Cなどruby以外の言語であれば、実行速度は変わってくると思います。

最近プログラミングしてなかった自分としては、 他の言語についてじっくり考える余裕がなかったのは残念です。 でも、速度向上を得るためにアルゴリズムについて考えることは最近できてなかったので、 とても参考になりました。

別のアルゴリズムでさらに効率的にできるのであれば、学びたいと思います。

アルゴリズムは奥が深い。

comments powered by Disqus
#ruby