Ruby - 优雅地比较两个枚举器

Question

我有两个来自不同来源（二进制数据）的长数字流，使用Ruby（1.9.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

那么，有没有更简单、更优雅的方法来完成这个任务呢？

- kikito

---

Enumerable#zip可能更加优雅，但在性能方面很可能没有任何改进。 - Steve Jorgensen

在Ruby 1.9中处理这个问题的高性能方式似乎是使用纤程/协程。请参见http://www.infoq.com/news/2007/08/ruby-1-9-fibers。 - Steve Jorgensen

@Steve：zip 的问题在于它会在内部创建数组，无论你传递什么 Enumerable。还有一个问题是输入参数的长度。 - Mladen Jablanović

@Mladen：我知道，这就是为什么我说它很可能不会有任何性能上的改进。 - Steve Jorgensen

@Mladen: 1.times.zip(1.times) {|x,y| puts x, y; 42} 输出 0，0 并返回 nil。 - Andrew Grimm

Answer 1

稍微重构了一下你的代码，假设你的流并不包括一个元素: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这样的方法更快。

- sawa

---

我非常喜欢这个。我没有想到我可以使用“守卫”值，比如你的例子中的:eof符号。谢谢！ - kikito

哦——我一直认为我们需要一个解决方案，可以枚举重复调用传递给#each的块。只要我们能够拉取，这就是一个很好的解决方案。如果它必须与可枚举对象一起使用，则需要协程。 - Steve Jorgensen

Answer 2

逐个比较它们可能是你能做到的最好方法，但你可以比“呃”解决方案更好地完成它：

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

难点在于区分只有一个流程结束和两个都结束的情况。将StopIteration异常推入单独的函数中，并使用哈希表中键值的缺失是一种相当方便的方法。如果检查vals[:s1]，则在流程包含false或nil时会出现问题，但检查键的存在性可以解决这个问题。

- mu is too short

---

谢谢你的回答。我更喜欢sawa的，但还是感谢你花时间回答！ - kikito

@kikito：很酷，我也点赞了sawa的答案。Sawa和我使用的基本上是相同的逻辑，只是我使用缺少哈希键来表示结束，而不是哨兵值。如果您知道您的流中永远不会有:eof符号，则无需使用额外的机制来避免使用哨兵。 - mu is too short

你说得对。我的代码可能会与 :eof 发生冲突。比我的方案更通用，所以加一分。 - sawa

@sawa：但是:eof可能是哨兵的最佳选择，特定情况涉及“数字流”，如果在数字流中出现:eof符号，则kikito面临的问题比保留的哨兵值更多。 - mu is too short

Answer 3

这里介绍一种方法，通过创建一个替代品来实现Enumerable#zip，它可以懒加载并且不会创建整个数组。它将Closure的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

- Mladen Jablanović

---

“which works lazily and doesn't create an entire array” - zip 通常也不会创建整个数组：请参见 https://dev59.com/jVjUa4cB1Zd3GeqPTKTr 和 https://dev59.com/8VjUa4cB1Zd3GeqPTaU6 - Andrew Grimm

我的评论链接到了这个问题。非常抱歉，这是我犯的低级错误！ - Andrew Grimm

Answer 4

根据评论讨论，这里提供了一种基于zip的解决方案。首先在Enumerator中封装了zip的块版本，然后使用它来比较相应的元素。

它可以工作，但已经提到了一个极端情况：如果第一个流比另一个短，那么来自另一个流的剩余元素将被丢弃（见下面的示例）。

我已将此答案标记为社区维基，因为其他成员可以对其进行改进。

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

- Mladen Jablanović

Answer 5

这是一个使用纤程/协程的双源示例。它有点冗长，但非常明确地说明了其行为，这很好。

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

- Steve Jorgensen