5

私がルビーによく夢中になっていることの1つは、再帰パターンです。たとえば、配列があり、その配列に無制限の深さの要素として配列が含まれているとします。したがって、たとえば：

my_array = [1, [2, 3, [4, 5, [6, 7]]]]

配列をに平坦化できるメソッドを作成したいと思います[1, 2, 3, 4, 5, 6, 7]。

私はそれでうまくいくことを知って.flattenいますが、この問題は私が定期的に遭遇する再帰の問題の例として意図されています-そのため、私はより再利用可能な解決策を見つけようとしています。

要するに、この種のものには標準的なパターンがあると思いますが、特にエレガントなものを思いつくことはできません。どんなアイデアもありがたい

4

3 に答える 3

5

再帰は方法であり、言語に依存しません。アルゴリズムは、関数を再度呼び出すケース（再帰ケース）と関数を壊すケース（基本ケース）の2種類のケースを念頭に置いて作成します。たとえば、Rubyで再帰的なフラット化を行うには、次のようにします。

class Array
  def deep_flatten
    flat_map do |item|
      if item.is_a?(Array)
        item.deep_flatten
      else
        [item]
      end
    end
  end
end 

[[[1]], [2, 3], [4, 5, [[6]], 7]].deep_flatten
#=> [1, 2, 3, 4, 5, 6, 7]

これは役に立ちますか？とにかく、ここに示されている便利なパターンは、配列で再帰を使用している場合、通常は（ + /flat_mapの機能的な代替手段）が必要になることです。eachconcatpush

于 2012-05-21T07:43:53.293 に答える
4

Cについて少し知っている場合は、ドキュメントにアクセスし、ruby関数をクリックしてCソースを取得するだけで、すべてが完了します。

http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-flatten

そしてこの場合、ここにRubyの実装があります

def flatten values, level=-1
  flat = []
  values.each do |value|
    if level != 0 && value.kind_of?(Array)
      flat.concat(flatten(value, level-1))
    else
      flat << value
    end
  end
  flat
end

p flatten [1, [2, 3, [4, 5, [6, 7]]]] 
#=> [1, 2, 3, 4, 5, 6, 7]
于 2012-05-21T07:43:51.463 に答える
2

これは、末尾再帰スタイルで記述されたフラット化の例です。 

class Array

  # Monkeypatching the flatten class
  def flatten(new_arr = [])
    self.each do |el|
      if el.is_a?(Array)
        el.flatten(new_arr)
      else
        new_arr << el
      end
    end

    new_arr
  end
end

p flatten [1, [2, 3, [4, 5, [6, 7]]]] 
#=> [1, 2, 3, 4, 5, 6, 7]

ルビーは常に末尾再帰用に最適化されているわけではないように見えますが、ルビーは末尾呼び出しの最適化を実行しますか？

于 2013-12-11T07:34:21.887 に答える