3

Rubyの学習実験として、Pascalの三角形ジェネレーターの実装をメモしようとしています。私は次の作業コードを持っています：

module PascalMemo
  @cache = {}
  def PascalMemo::get(r,c)
    if @cache[[r,c]].nil? then 
      if c == 0 || c == r then 
        @cache[[r,c]] = 1
      else
        @cache[[r,c]] = PascalMemo::get(r - 1, c) + PascalMemo::get(r - 1, c - 1)
      end
    end
    @cache[[r,c]]
  end
end

def pascal_memo (r,c)
  PascalMemo::get(r,c)
end

これをもっと簡潔にすることはできますか？具体的には、これよりも簡単にローカルクロージャを使用してグローバルスコープの関数を作成できますか？

4

3 に答える 3

2 
def pascal_memo
  cache = [[1]]
  get = lambda { |r, c|
    ( cache[r] or cache[r] = [1] + [nil] * (r - 1) + [1] )[c] or
      cache[r][c] = get.(r - 1, c) + get.(r - 1, c - 1)
  }
end

p = pascal_memo
p.( 10, 7 ) #=> 120

上記の構成はメモ化を実現することに注意してください。これは単純な再帰的な方法ではありません。

于 2012-11-06T06:02:07.463 に答える
1

これをもっと簡潔にすることはできますか？

それはかなり明確に思えます、IMO、そしてmoduleingは通常良い本能です.

これよりも簡単に、ローカル クロージャーを使用してグローバル スコープの関数を作成できますか?

別のオプションは再帰的lambdaです：

memo = {}

pascal_memo = lambda do |r, c|
  if memo[[r,c]].nil?
    if c == 0 || c == r
      memo[[r,c]] = 1
    else
      memo[[r,c]] = pascal_memo[r - 1, c] + pascal_memo[r - 1, c - 1]
    end
  end
  memo[[r,c]]
end

pascal_memo[10, 2]
# => 45
于 2012-11-06T05:38:21.180 に答える
0

ラムダではなく関数を生成するため、私が望むことを達成する方法を見つけました。

class << self
  cache = {}

  define_method :pascal_memo do |r,c|
    cache[[r,c]] or 
    (if c == 0 or c == r then cache[[r,c]] = 1 else nil end) or 
    cache[[r,c]] = pascal_memo(r-1,c) + pascal_memo(r-1,c-1)
  end
end

これにより、メイン オブジェクトのメタクラス/シングルトン クラスが開き、define_method を使用してキャッシュ変数を閉じる新しいメソッドが追加されます。これは、pascal_memo メソッド以外のすべてのスコープから外れます。

于 2012-11-08T00:24:57.713 に答える