1

私は自分のアルゴリズムのために配列の順列のかなり大きなセットを生成しています:

argeArray.permutation(permSize) do |perm|
  # Do something with perm
end

現在、停止したインデックスで続行できるようにアプリケーションを更新する作業を行っています。

少し見回した後、permutation（スキップできるようにするために0..startIndex）開始インデックスを持つ代替方法が見つかりませんでした。

次に、順列列挙子から最初の数の要素を切り取ることができるdrop()メソッドを見つけました。

startIndex = 3000000000 # skip first 3 billion combinations
argeArray.permutation(permSize).drop(startIndex) do |perm|
  # Do something with perm
end

しかし、実験では、これにより組み合わせの完全なセットが作成されることが示されました。これは、非常に多くのメモリを必要とするため、あまり効率的ではありません...最初の 30 億の組み合わせをスキップする必要がある場合でも...

startIndex別の解決策は、に達するまでアルゴリズムをスキップすることです。

startIndex = 3000000000 # skip first 3 billion combinations
argeArray.permutation(permSize).with_index() do |perm, index|
  next if index < startIndex # Skip until startIndex is reached
  # Do something with perm
end

欠点は、アルゴリズムが (最終的に) 機能し始める前に 30 億の組み合わせがテストされることです (そして、無駄startIndexに達しているかどうかをチェックし続けます) 。

この問題に対する他の (より効率的な) 解決策はありますか? どういうわけかpermutation()、最初の数の組み合わせをスキップするように指示できるようにするには? （常に同じ順序を使用すると仮定）

4

1 に答える 1

1

Ruby 2.0 が導入されましEnumerator::Lazyた。多分それを調べることはあなたを助けるかもしれません。

module Enumerable
  def filter_map(&block)
    map(&block).compact
  end
end

class Enumerator::Lazy
  def filter_map
    Lazy.new(self) do |yielder, *values|
      result = yield *values
      yielder << result if result
    end
  end
end

(1..Float::INFINITY).lazy.filter_map{|i| i*i if i.even?}.first(5)
    # => [4, 16, 36, 64, 100]

おそらく、順列をインスタンスとして作成し、特定の位置にスキップするためにEnumerator::Lazy使用できます。drop

于 2013-06-04T08:25:47.630 に答える