Rubyでアルゴリズム

Pocket
LINEで送る

どうもこんにちは!新人の有安です。

いきなりですけどアルゴリズムって興味ありますか?

アルゴリズムってね、例えばWebアプリ作るだけなら必要ないなんて思って手を出していない人も結構いるんじゃないでしょうか。

もったいないぜ!

アルゴリズムは非常に役に立ちます。勉強した方がいいです。僕すこーし手を出しただけですけど、実務でめちゃくちゃ活きてます。

例えば、計算量ってWebアプリ作る時にも気にすると思うんです。でも中々クエリ発行抑える以外のパフォーマンスチューニングって難しいですよね。

アルゴリズムをちょっとかじると、そんな時に色々アイデアが出てくるように思うのです。

ということで、今回はあるアルゴリズムの問題を通して、工夫次第でどれだけ処理が速くなるか見てみましょう!

【問題】

——————————————————————————————

あなたは中学生です。新学期を迎え、席替えをしようとしています。

「前後左右のいずれかに必ず異性が座る」ような席替えをすることになりました。

あなたが男だとすると、前後左右いずれかには絶対に女の子がいないといけません。

前後左右全部女の子なら当然OK(むしろ歓迎)、前後男で右も男でも左に女の子がいてくれればOK、でも全部いないのは絶対にイヤ!

自分が左端で1番後ろの席の場合、前か右もしくは両方に女の子がいないと駄目。

そんな席替えを考えてみましょう。

男女それぞれ15人ずつ、横6 x 縦5の座席配置だとします。

上記の条件を満たすような男女の配置は何通りあるでしょう?

左右、前後などの反転は別々とカウントすることにします。

また、個々の生徒がどこに座るかは無関係で、男女の配置のみを考えるものとします。

スクリーンショット 2018-06-01 13.10.08

—————————————————————————————

【考え方】

まずは何も工夫せずに実装してみましょう。

NGな配置を設定して、これを満たさない場合にカウントしていきます。


# 1~30の配列で座席を表現
seats = (1..30).to_a

# 条件を満たさない配置は除外対象、左前から横に1,2,3...と数える
ng = [
  [1,2,7],[5,6,12],[19,25,26],[24,29,30],[1,2,3,8],
  [2,3,4,9],[3,4,5,10],[4,5,6,11],[1,7,8,13],[7,13,14,19],
  [13,19,20,25],[6,11,12,18],[12,17,18,24],[18,23,24,30],
  [20,25,26,27],[21,26,27,28],[22,27,28,29],[23,28,29,30],
  [2,7,8,9,14],[3,8,9,10,15,],[4,9,10,11,16],[5,10,11,12,17],
  [8,13,14,15,20],[9,14,15,16,21],[10,15,16,17,22],
  [11,16,17,18,23],[14,19,20,21,26],[15,20,21,22,27],
  [16,21,22,23,28],[17,22,23,24,29]
]
cnt = 0
seats.combination(15) do |boy| # 男子の配置の組み合わせ
  girl = seats - boy # 女子の配置の組み合わせ
  if ng.all?{|n| boy & n != n} && ng.all?{|n| girl & n != n}
    cnt += 1
  end
end
puts cnt

コードは分かりやすいですが、これだと1時間半くらいかかるそうです。

2時間目始まっちゃうよ!

ということで、色々工夫をします。

W, H = 5, 6
ALL = (1 << W) - 1
# 各行の男子の人数を保持
@boys = (0..ALL).map{ |i| i.to_s(2).count("1") }

# 3つの行の配置が可能か(上の2行に次の行を続けられるか)
def check(r1, r2, r3)
  result = true
  W.times do |i| # 1行の各位置について確認
  m1 = (0b111 << (i -1)) & ALL # 左右に並んでいるかのチェック
  m2 = 1 << i # 上下に並んでいるかのチェック
  if (r1 & m2 == m2) && (r2 & m1 == m1) && (r3 & m2 == m2)
    result = false # 男子が並んでいる場合はNG
  end
  if ((r1 ^ ALL) & m2 == m2) && ((r2 ^ ALL) & m1 == m1) && ((r3 ^ ALL) & m2 == m2)
    result = false # 女子が並んでいる場合もNG
    end
  end
  result
end

# 上の2行に続く行のハッシュを作成
@next = {}
(1 << W).times do |r1| # 1行目
  (1 << W).times do |r2| # 2行目
    @next[[r1, r2]] = (0..ALL).select{ |r3| check(r1, r2, r3) }
  end
end

@memo = {}
def search(pre1, pre2, line, used)
  if @memo.has_key?([pre1, pre2, line, used])
    return @memo[[pre1, pre2, line, used]] # 過去に探索済みの場合
  end
  if line >= H
    @memo[[pre1, pre2, line, used]] = (used == W * H / 2) ? 1 : 0
    return @memo[[pre1, pre2, line, used]]
  end
  result = 0
  if line == H - 1
    @next[[pre2, pre1]].each do |row|
      if (@next[[row, row]].include?(pre1)) && (used + @boys[row] <= W * H / 2)
        result += search(row, pre1, line + 1, used + @boys[row])
      end
    end
  else
    @next[[pre2, pre1]].each do |row|
      if used + @boys[row] <= W * H / 2
        result += search(row, pre1, line + 1, used + @boys[row])
      end
    end
  end
  @memo[[pre1, pre2, line, used]] = result
end

count = 0
(1 << W).times{ |r0| count += search(r0, r0, 1, @boys[r0]) }
puts count

工夫しまくり!ようわからん

みた通り再帰を使っていますが、これはいわゆる「メモ化再帰」ですね。知らない方はメモ化とか動的計画法とかでググってみてくださいね。

一旦探索した結果を保持しておいて、同じ探索をしなくて済むようにしています。

他にも「枝刈り」というテクニックも使われています。

こちらは不要な探索の打ち切りを行なっています。

このコードなら、なんと2秒ほどで正解を得ることが出来ます。あ、正解は13374192通りです。

アルゴリズムを工夫することでこんなにも速くなるんですね。

ここまで極端じゃなくても、例えば3秒を2秒にとか、頭をひねってそれくらいパフォーマンスチューニング出来たらとても楽しいですよね!

ということで、オススメのアルゴリズム入門書貼ってお別れです!さよなら!

アルゴリズムとデータ構造

Pocket
LINEで送る