【Ruby】【アルゴリズム】関数呼び出しはコストが高い

　
■topic summary
study about 8puzzle.
see more

今日のブログは感動だよ！（当社比）

またいつものように高橋さんのアルゴリズムをもとにお勉強。
やわらか頭でアルゴリズムを10倍生かす - 第3回 8パズル：ITpro

問題

1から8までのパネルと一つの空欄で構成される、3×3のスライドパズルがあります。パネルがばらばらに並べられた状態から始めて、左上から1、2、…、8と並べられたら完成です（図1）。このパズルを解くプログラムを作成してください。

7パズルは以前解いたから余裕
と思っていたけど、甘かった。
発見がいろいろありました。

ちなみに7パズルはメモリを爆発させたり、色々ありました

以前の実装

幅優先＆キューで解いた。
以前のコードでは、「Queから要素をとりだす」をやっていなかった。
つまりQueは要素分だけ、たらたらと長くなっていく実装。
i番目の要素を検証し、iをインクリメントさせていく。

def _solve(idx, que)
  i = 0
  while i < que.length
    if que[i].val == [9,1,2,3,4,5,6,7]
      #goal
    else
      que.add_next_pattern(i)
      i += 1
    end
  end
end

なぜこうしたかというと、過去の状態を取得したかったから。
Queのインデックスをさかのぼることで、過去状態を取得できる。

でも、Queを使った実装は、
Queから先頭要素を取り出していくことで実装するのがオーソドックスなやり方。

高橋さんのコードも
Queの要素を取り出していく方式。

じゃあ過去状態をどうやって取り出すのか？
というと、
Patternクラスの要素としてPatternクラスインスタンスを持つ。
マトリョーシカのイメージ？

これを見たときに、自分は
メモリが爆発しないのかな？？？ってすこし不思議に思った。

でも考えたらそんなことはないね。
あくまで参照（ポインタ）を渡しているだけだから、メモリを食うことはない。

ってスマートに書いてるけど
最初はどうしても理解できなくてコードを全量写経したけど。
秘密だから！

なぜ高橋さんのコードはこんなに早いのか

自分の実装したコード（※１）と大した違いはなさそうなのに、
実行時間が雲泥の差。

どうしてか考えてみるに、
お手本コードはhash化するものの、dehashしていない。
私のコードはこうやってdehashしている。

def _dehash(int)
  int.to_s.split("").map!{|ch| ch.to_i}
end

お手本では、ゼロの位置を別要素としてインスタンスに持っている。
最初見たとき「どうしてわざわざ重複する情報を持つんだろう」と思ったけど
こうすることで処理が早くなるのかもしれない。
次の記事でやってみよう。

関数呼び出しのコスト

そんなこんなで、インスタンスに過去状態を持つことで
オーソドックスなQue使用パターンを実装してみました。

そしたら、stack level too deep。
原因は、whileの中で再帰を使っていたため。

■NGパターン
stack level too deepで落ちちゃう。

def _solve(que, checked_set)
  now_pattern = que.shift
  if now_pattern.val == 91234567
    #goal
  else
    que.add_next_pattern(now_pattern, checked_set)
    _solve(que, checked_set)  #<= 再帰にしていた
  end
end

　
■OKパターン

def _solve(que, checked_set)
  while now_pattern = que.shift
    return show(now_pattern) if now_pattern.val == 91234567
    que.add_next_pattern(now_pattern, checked_set)
  end
  puts "not solve"
end

queをwhileでまわして、shiftで先頭を取っていく。
変に再帰を使うから混乱してしまった。
「過去状態がマトリョーシカだからメモリが足りないのか？？」と混沌としていた。
ごめんね。。

　
師匠に喜びのメールを打つと、、

うわー！
再帰を使ってたらstack level too deepだったのが
ただのwhile文に書き直したら動くようになった！！！！

関数呼び出しはコスト高いんですよ
普段は気にならないレベルやけど、関数呼び出しが深くなるとコストが目に付く

ふむふむ。
まさに今のパターンだね。

なので、関数呼び出しを消せると判断すると
関数呼び出しを消すテクニックは昔から知られています

コンパイルする段階でということ？

コンパイルする段階でやる場合と
実行中にやる場合があります

なるほどね。

　
※１

実装コード

こんなコードになりました。

#表示用
def show(now_pattern)
  state = now_pattern
  while state
    puts state.val.to_s[0..3]
    puts state.val.to_s[4..7]
    puts "------"
    state = state.parent
  end
end

class Pattern
  attr_accessor :val, :parent
  def initialize (val, parent)
    @val = val
    @parent = parent
  end
end

class PatternQue < Array
  def add_next_pattern(now_pattern, checked_set)
    now = _dehash(now_pattern.val)
    blank = now.index(9)
    if blank < 4
      copy = now.dup
      copy[blank], copy[blank+4] = copy[blank+4], copy[blank]
      checkdone_and_add(checked_set, _hash(copy), now_pattern)
    elsif
      copy = now.dup
      copy[blank], copy[blank-4] = copy[blank-4], copy[blank]
      checkdone_and_add(checked_set, _hash(copy), now_pattern)
    end
    if blank != 3 && blank != 7
      copy = now.dup
      copy[blank], copy[blank+1] = copy[blank+1], copy[blank]
      checkdone_and_add(checked_set, _hash(copy), now_pattern)
    end
    if blank != 0 && blank != 4
      copy = now.dup
      copy[blank], copy[blank-1] = copy[blank-1], copy[blank]
      checkdone_and_add(checked_set, _hash(copy), now_pattern)
    end
  end
  def checkdone_and_add(checked_set, candidate, now_pattern)
    return if checked_set.index(candidate)
    checked_set << candidate
    self << Pattern.new(candidate, now_pattern)
  end
end

def _hash(arr)     
  return arr.join.to_i
end
def _dehash(int)
  int.to_s.split("").map!{|ch| ch.to_i}
end
def solve(val)
  first_hash = _hash(val)
  que = PatternQue.new
  que << Pattern.new(first_hash, nil)
  checked_set = []
  checked_set << first_hash
  return _solve(que, checked_set)
end

def _solve(que, checked_set)
  while now_pattern = que.shift
    return show(now_pattern) if now_pattern.val == 91234567
    que.add_next_pattern(now_pattern, checked_set)
  end
  puts "not solve"
end
solve([2, 7, 4, 1, 5, 9, 3, 6])

　
　
長くなってきたのでいったん終了。