せかいや

いまいるここを、おもしろく http://sekai-in-the-box.appspot.com/

【Ruby】【メタプログラミング】callerメソッド。method_missingを使ったメソッド呼び出しのトレーシング

　
　
■topic summary
study about meta-programming with Ruby.

　

プログラミング言語 Ruby

プログラミング言語 Ruby

この本で、最後に大切に残していた、メタプログラミングの章を勉強するよ。
分かるかな。。


　

callerメソッド

引数なしの場合は、スタックフレームが1個省略された形になる

class Hoge
  def meth1
    meth2
  end
  def meth2
    p caller
    p caller(0)
  end
end
Hoge.new.meth1

　
■実行結果

["C:/Users/Hoge_ADMIN/Desktop/test/fizzbazz.rb:4:in `meth1'", "C:/Users/Hoge_ADMIN/Desktop/test/fizzbazz.rb:12:in `<main>'"]
["C:/Users/Hoge_ADMIN/Desktop/test/fizzbazz.rb:8:in `meth2'", "C:/Users/Hoge_ADMIN/Desktop/test/fizzbazz.rb:4:in `meth1'", "C:/Users/Hoge_ADMIN/Desktop/test/fizzbazz.rb:12:in `<main>'"]

　
なるほど。

　

method_missingを使ったメソッド呼び出しのトレーシング

class Object
  def trace(name, stream=STDOUT)
    return TraceObject.new(self, name, stream)
  end
end
class TraceObject
  #TraceObjectの既存インスタンスメソッドを消す
  instance_methods.each do |m|
    next if m == :inspect || m == :object_id ||  m == :__id__ || m == :__send__
    undef_method m
  end
  def initialize(o, name, stream)
    @o, @n, @trace = o, name, stream
  end
  def method_missing(*args, &b)
    p method_name = args.shift
    arglist = args.map{|ar| ar.inspect}.join(",")
    @trace << "Invoking: #{@n}.#{method_name}(#{arglist}) called at #{caller[0]}\r\n"
    begin
      result = @o.send(method_name, *args, &b)
      @trace << "Returning: #{result} from #{@n}.#{method_name}(#{arglist}) called at #{caller[0]}\r\n"
      result
    rescue Exception=>e
      @trace << "Raising: #{e.class}:#{e} from #{@n}.#{method_name}(#{arglist})}\r\n"
      raise
    end
  end
  def __delegate
    @o
  end
end
a = [1,2,3].trace("target")
p a  #<= TraceObjectオブジェクトは出力できない
p a.__delegate
a.<<(4)
a.fetch(10)

　
■実行結果

Invoking: target.inspect() called at fizzbazz.rb:34:in `p'
Returning: [1, 2, 3] from target.inspect() called at fizzbazz.rb:34:in `p'
[1, 2, 3]  #<= 委譲元オブジェクトが出力される
[1, 2, 3]
Invoking: target.<<(4) called at fizzbazz.rb:36:in `<main>'
Returning: [1, 2, 3, 4] from target.<<(4) called at fizzbazz.rb:36:in `<main>'
Invoking: target.fetch(10) called at fizzbazz.rb:37:in `<main>'
Raising: IndexError:index 10 outside of array bounds: -4...4 from target.fetch(10)}


　

注意（？）

委譲先オブジェクトを出力したいときは、
pメソッド内で実行されるinspectメソッドを消去対象からはずす。

next if m == :inspect || m == :object_id ||  m == :__id__ || m == :__send__

　
■実行結果

#<TraceObject:0x2e3e138 @o=[1, 2, 3], @n="target", @trace=#<IO:<STDOUT>>>
[1, 2, 3]


　
ふむふむ。


　

【Ruby】？記法、応用編　　視力検査

さっき、クエスチョンマークが連続した問題を解いたけど
Goroさんが応用問題を作ったんだって。

　

これは、さっきの？記法が分かったら簡単だねー。

　

ポイント

最初の「Q. 」は、質問って意味で、構文には含まれない！
これ嵌った。
もー。

回答

？記法と条件演算子の組み合わせ。
　
構文全体

??.a??????:??

を分けて考えると、

　
　
まず 頭の部分、

??.a???

は

"?".a?("?")

なわけで、こう書くと分かりやすい。
　

class String
  def a?(str)
    p str
  end
end
??.a???

　
■実行結果

"?"

　
　
そうすると構文は、

"?"???:??

となって、これはもう条件演算子。
Rubyはnil以外はtrueになる。
　
　
こうやって書き直すと分かりやすい。

p "?"? "hoge":"aa"
p !"?"? "hoge":"aa"

　
■実行結果

"hoge"
"aa"


　
なるほどねー。
視力検査みたいだね。

【Ruby】クエスチョンマークが三つで何になる？　？？？　？記法

　
　
■topic summary
what means -> a???


タイトル意味分からないね。
　

　
そらはさんのツイートでこんなのを見つけたよ。

　
へー？
なんでなんだろう？
わからないなー。
しらべてみよう！


　

本当？

まずは本当かしらべてみよう

class Q
  def self.foo
  end
end
Q. foo.a???

　
■実行結果

:in `<main>': undefined method `a?' for nil:NilClass

おお！
たしかに！

　
クエスチョンマークが３つっていうのが怪しいよね。
２つだとどうなるんだ？
　
■実行結果

syntax error, unexpected end-of-input

へー！？

　

クエスチョンマークをつかったリテラル記法

数値リテラル
?a
文字 a を表す String

http://docs.ruby-lang.org/ja/2.0.0/doc/spec=2fliteral.html

　
こんなヒントをみつけた。
　
なるほどね！

p ??

　
■実行結果

"?"

　
だから、この↓結果は

a(??)

■実行結果

 undefined method `a' for main:Object (NoMethodError)

これは、aメソッドに引数「？」を渡していると解釈されているんだね。



　
括弧でくくらないと、クエスチョンマークはメソッド名の一部としてパースされる

p a??

　
■実行結果

syntax error, unexpected end-of-input

これは、a?メソッドに渡す引数が?記法を使っていると解釈されていて、
その？記法に対する引数が期待されているのに渡してないから、
シンタックスエラーになってしまう。



　
本題の

a???

は、

a?(??)

と書き直すと分かりやすく、
　
■実行結果

undefined method `a?' for main:Object (NoMethodError)

つまり、引数として「？」を渡したa?メソッドを実行しようとしているけど、
a?メソッドががみつからないよ、というエラー。




なるほどー。
　

【HELP済】【JavaScript 】bind関数を引数なしで呼ぶと。bindでクロージャー。

　
■topic summary
what means -> callback.bind() ???


　
この本を読んでるんだけど、すごいボリューム。

パーフェクトJavaScript (PERFECT SERIES 4)

パーフェクトJavaScript (PERFECT SERIES 4)

頭わいてる！

　

引数なしのbind呼び出し？

21章にこんなサンプルコードが。

event_source.on('foo', callback.bind());
event_source.removeListener('foo', callback.bind());

　

本には、

これらのコードは、イベントハンドらを意図通り削除できていません。なぜなら2つのbindの呼び出しはそれぞれ別の関数オブジェクトの参照を返すからです

とある。

なんでbindメソッドを引数なしで呼んでいるの？？
　
うーん、、

The value is ignored if the bound function is constructed using the new operator.

https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Function/bind

Mozilla仕様にはこう書いてあるけど、
EventEmitter.onメソッドの引数でbindメソッドが実行されると
newを使ってるのと同等とみなされているのかな。。？
よく分からないな。

引数の省略はできないとIEには書いてあるし。。
bind メソッド (Function) (JavaScript)


まだ自分はthisの概念が分かってないのかもしれない。
とりあえずメモしておこう。。。



　

追記

　
ピタゴラさんからコメントをもらったよ！
f:id:sekaiya:20131116082630j:plain

なるほど。
bindが別々の関数オブジェクト（クロージャ）を返すことを表現したかったのか！
別にNode.jsは関係のない話なんだね。

なら手元で実際に動かして試してみよう。
ありがとうピタゴラさん。。！

　

bind関数、引数あり

fn=function(){
console.log(this);
}
var a={x:"aaa"};
fn.bind(a)();

　
■実行結果

Object {x: "aaa"}

　
fnメソッドのレシーバーはaオブジェクト。



　

bind関数、引数なし（ケースA）

fn=function(){
console.log(this);
}
var a;
fn.bind()();

　
■実行結果

Window {top: Window, window: Window, location: Location, Proxy: Object, external: Object…}

　
なるほど。
エラーになるわけではないのか。
ただ、thisがWindowオブジェクト参照になるのは
クライアントサイドJavaScriptでのグローバルオブジェクトが
Windowオブジェクト だからであって、
ここに依存したコーディングは避けたほうがよさそう。

　

bind関数、引数がundifined（ケースB）

fn=function(){
console.log(this);
}
var a;
fn.bind(a)();

　
■実行結果

Window {top: Window, window: Window, location: Location, Proxy: Object, external: Object…}

　
引数なしと同じ結果。

　

参考

上記のケースA ケースB について、
通りすがりさんから、コメントをもらったよ。
f:id:sekaiya:20140101212654p:plain
　
ふむふむ。通りすがりさんありがとう！
なるほど。
thisがwindowオブジェクトになった場合は
引数でレシーバの指定が出来てない可能性があるかもしれない、と頭に入れておこう。
　

別の関数オブジェクトの参照を返す？

　
以上を踏まえて、本に書いてあった

2つのbindの呼び出しはそれぞれ別の関数オブジェクトの参照を返す

について、実際に確かめてみよう。

　

素朴なクロージャー

まずは素朴なパターン

countup = function(){
  var cnt = 0;
  return function(){console.log(++cnt);}
}
var fn = countup();
fn();
fn();

　
■実行結果

1
2


　　

あえてのbind

bindを使ってみると、

countup = function(){
  var cnt = 0;
  return function(){console.log(++cnt);}
}
countup.bind()()();
countup.bind()()();

　
■実行結果

1
1

丸括弧が3つあるのは、

bindメソッドの引数
bindメソッドで返却される関数オブジェクトの引数
bindメソッドで返却される関数オブジェクトの実行

だよ。


　
ふむふむ。

2つのbindの呼び出しはそれぞれ別の関数オブジェクトの参照を返す

というのは別に、bindだからどうこうって話ではなくて、
単にメソッドを複数回呼び出したら、
そのたびにオブジェクトが生成されて返却されます
というだけの話か。

　
bindの返り値を変数に参照させておいても、
実行時に同じコンテキストを見ることはできない。

countup = function(){
  var cnt = 0;
  return function(){console.log(++cnt);}
}
var fn = countup.bind();
fn()();
fn()();

　
■実行結果

1
1


　　
　
同じコンテキストを見たかったら、こう！

countup = function(){
  var cnt = 0;
  return function(){console.log(++cnt);}
}
var fn = countup.bind();
var gn = fn();
gn();
gn();

　
■実行結果

1
2


　　
なるほどー。
用語がふわっとしててごめんなさい。

そしてピタゴラさん、ありがとう！

【JavaScript 】【Ruby】　＆＆　と　｜｜の便利な合わせ技

　
■topic summary
what's come out? => console.log(a ＆＆ b || "none")


この記事を読んで、jQueryのコードを追っているよ。
第2回 jQueryライブラリ（172行目～469行目）：jquery.jsを読み解く｜gihyo.jp … 技術評論社
　

頻繁に出てくるのが、こういう構文。

return this.setArray(
// HANDLE: $(array)
selector.constructor == Array ＆＆ selector ||

// HANDLE: $(arraylike)
// Watch for when an array-like object, contains DOM nodes, is passed in as the selector
(selector.jquery || selector.length ＆＆ selector != window ＆＆ !selector.nodeType ＆＆ selector[0] != undefined ＆＆ selector[0].nodeType) ＆＆ jQuery.makeArray( selector ) ||

// HANDLE: $(*)
[ selector ] );

Rubyでも||を使うことによって、
nilの場合の値を指定する構文があるのはよく見るけど、
＆＆ってなんだ？

確かめてみよう。

　

var a = "aaa";
var b = "bbb";
var c;
console.log(a ＆＆ b || "none");
console.log(c ＆＆ b || "none");

　
■実行結果

"bbb"
"none"

なるほど。
　
　
これはRubyでもできるのかな？

a = "aaa"
b = "bbb"
c = nil
p (a || b)
p (c || a)
p (c || a ＆＆ b)

　
■実行結果

"aaa"
"aaa"
"bbb"

なるほどー。

【HELP】【Ruby】【アルゴリズム】8パズル　dehashしないVer

　
■topic summary
coding without dehash function
dehash function is here


だめだ。
高橋さんのコードはdehashしていないから早いのかなー
と思ってまねしてみたけど大して早くならなかった。

　

変更点

・クラスプロパティ
・hash関数をPatternクラスのインスタンスメソッドに。
・dehashを使わない

　

処理時間

2回ずつ計測。

■前のコード
    user     system      total        real
5.024000   0.000000   5.024000 (  5.025287)
    user     system      total        real
5.382000   0.015000   5.397000 (  5.404309)

■今のコード
    user     system      total        real
5.086000   0.000000   5.086000 (  5.085291)
    user     system      total        real
4.976000   0.016000   4.992000 (  5.002286)

とくに変わってないよ！
なんでだろう。
　

変更したコード

require 'set'
require 'benchmark'

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

class Pattern
  attr_accessor :nums, :parent
  def initialize (nums, parent)
    @nums = nums
    @parent = parent
  end
  def hash_code
    @nums.join("").to_i
  end
end

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

def solve(nums)
  que = PatternQue.new
  first_pattern = Pattern.new(nums, nil)
  que << first_pattern
  checked_set = []
  checked_set << first_pattern.hash_code
  _solve(que, checked_set)
end

def _solve(que, checked_set)
  while now_pattern = que.shift
    return show(now_pattern) if now_pattern.hash_code == 91234567
    que.add_next_pattern(now_pattern, checked_set)
  end
  puts "not solve"
end
Benchmark.bm do |x|
  x.report { solve([2, 7, 4, 1, 5, 9, 3, 6]) }
end

ふむむむ。
こんど師匠に聞いてみよう。

【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])

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