9

Ruby（1.9.2）の2つの異なるソース（バイナリデータ）からの2つの長い数値ストリームがあります。

2つのソースは、2つの列挙子の形式でカプセル化されます。

2つのストリームが完全に等しいことを確認したいと思います。

私はいくつかの解決策を持ってきましたが、どちらも非常にエレガントではないようです。

最初のものは、単に両方を配列に変換します。

def equal_streams?(s1, s2)
  s1.to_a == s2.to_a
end

これは機能しますが、特にストリームに大量の情報がある場合は、メモリに関してはあまりパフォーマンスが高くありません。

他のオプションは...うーん。

def equal_streams?(s1, s2)
  s1.each do |e1|
    begin
      e2 = s2.next
      return false unless e1 == e2 # Different element found
    rescue StopIteration
      return false # s2 has run out of items before s1
    end
  end

  begin
    s2.next
  rescue StopIteration
    # s1 and s2 have run out of elements at the same time; they are equal
    return true
  end

  return false

end

それで、これを行うためのより簡単でよりエレガントな方法はありますか？

4

5 に答える 5

10

ストリームに要素が含まれていないと仮定して、コードを少しリファクタリングします:eof。

def equal_streams?(s1, s2)
  loop do
    e1 = s1.next rescue :eof
    e2 = s2.next rescue :eof
    return false unless e1 == e2
    return true if e1 == :eof
  end
end

のようなキーワードを使用すると、のloopようなメソッドを使用するよりも高速になりますeach。

于 2011-06-26T20:11:06.333 に答える
7

一度に1つの要素を比較することは、おそらくあなたができることになる最善の方法ですが、あなたの「難しい」解決策よりもうまく行うことができます。

def grab_next(h, k, s)
  h[k] = s.next
rescue StopIteration
end

def equal_streams?(s1, s2)
  loop do
    vals = { }
    grab_next(vals, :s1, s1)
    grab_next(vals, :s2, s2)
    return true  if(vals.keys.length == 0)  # Both of them ran out.
    return false if(vals.keys.length == 1)  # One of them ran out early.
    return false if(vals[:s1] != vals[:s2]) # Found a mismatch.
  end
end

トリッキーな部分は、1つのストリームが不足している場合と両方が不足している場合を区別することです。例外を別の関数にプッシュStopIterationし、ハッシュにキーがないことを使用することは、それを行うためのかなり便利な方法です。vals[:s1]ストリームにキーが含まれている場合、falseまたはnilキーの存在をチェックするだけで問題が解決する場合は、チェックするだけで問題が発生します。

于 2011-06-26T20:36:08.640 に答える
2

これは、の代替を作成することによってそれを行うショットですEnumerable#zip。これは、遅延して機能し、配列全体を作成しません。これは、クロージャの実装と他の2つの答えをここで組み合わせていinterleaveます（番兵の値を使用して、終わりにEnumerable到達したことを示します。問題の原因は、終わりに達したらnext巻き戻すことです）。Enumerable

このソリューションは複数のパラメーターをサポートしているため、 n個の構造を一度に比較できます。

module Enumerable
  # this should be just a unique sentinel value (any ideas for more elegant solution?)
  END_REACHED = Object.new

  def lazy_zip *others
    sources = ([self] + others).map(&:to_enum)
    Enumerator.new do |yielder|
      loop do
        sources, values = sources.map{|s|
          [s, s.next] rescue [nil, END_REACHED]
        }.transpose
        raise StopIteration if values.all?{|v| v == END_REACHED}
        yielder.yield values.map{|v| v == END_REACHED ? nil : v}
      end
    end
  end
end

したがって、zip遅延して動作し、最初の列挙型が最後に達したときに反復を停止しないバリアントがある場合は、またはを使用して、対応する要素が等しいかどうall?かを実際にチェックできます。any?

# zip would fail here, as it would return just [[1,1],[2,2],[3,3]]:
p [1,2,3].lazy_zip([1,2,3,4]).all?{|l,r| l == r}
#=> false

# this is ok
p [1,2,3,4].lazy_zip([1,2,3,4]).all?{|l,r| l == r}
#=> true

# comparing more than two input streams:
p [1,2,3,4].lazy_zip([1,2,3,4],[1,2,3]).all?{|vals|
  # check for equality by checking length of the uniqued array
  vals.uniq.length == 1
}
#=> false
于 2011-06-27T07:27:00.793 に答える
1

コメントでの議論に続いて、ここにzipベースのソリューションがあります。最初にブロックバージョンをzip内にラップしEnumerator、次にそれを使用して対応する要素を比較します。

それは機能しますが、すでに述べたエッジケースがあります。最初のストリームが他のストリームよりも短い場合、他のストリームの残りの要素は破棄されます（以下の例を参照）。

他のメンバーが改善できるので、私はこの回答をコミュニティwikiとしてマークしました。

def zip_lazy *enums
  Enumerator.new do |yielder|
    head, *tail = enums
    head.zip(*tail) do |values|
      yielder.yield values
    end
  end
end

p zip_lazy(1..3, 1..4).all?{|l,r| l == r}
#=> true
p zip_lazy(1..3, 1..3).all?{|l,r| l == r}
#=> true
p zip_lazy(1..4, 1..3).all?{|l,r| l == r}
#=> false
于 2011-06-27T13:44:01.000 に答える
0

これは、ファイバー/コルーチンを使用した2ソースの例です。少し時間がかかりますが、その動作については非常に明確であり、それは素晴らしいことです。

def zip_verbose(enum1, enum2)
  e2_fiber = Fiber.new do
    enum2.each{|e2| Fiber.yield true, e2 }
    Fiber.yield false, nil
  end
  e2_has_value, e2_val = true, nil
  enum1.each do |e1_val|
    e2_has_value, e2_val = e2_fiber.resume if e2_has_value
    yield [true, e1_val], [e2_has_value, e2_val]
  end
  return unless e2_has_value
  loop do
    e2_has_value, e2_val = e2_fiber.resume
    break unless e2_has_value
    yield [false, nil], [e2_has_value, e2_val]
  end
end

def zip(enum1, enum2)
  zip_verbose(enum1, enum2) {|e1, e2| yield e1[1], e2[1] }
end

def self.equal?(enum1, enum2)
  zip_verbose(enum1, enum2) do |e1,e2|
    return false unless e1 == e2
  end
  return true
end
于 2011-07-06T02:35:15.813 に答える