Ruby 用 Ruby 的 Enumerator 实现的流

cicholgricenchos · 2015年06月04日 · 最后由 yanguango 回复于 2015年06月04日 · 1914 次阅读

啃SICP到第三章,想试试将无穷流应用在Ruby里,顺便研究一下Enumerator的用法。

Enumerator可以直接用下面的代码创建:

e = Enumerator.new do |yielder|
  yielder.yield 1
  yielder.yield 2
  loop do
    yielder.yield 3
  end
end

e.next # => 1
e.next # => 2
e.next # => 3
e.next # => 3

这段代码挺好懂,但也有些诡异。可以看到每次执行e.next会要求enumerator返回一个值,这个值就是proc里的代码yield出来的值。因为proc里有个死循环,所以这就是一个无穷流,会yield出1,2,3,3,3,3,3……的序列。

每次yield完毕之后proc的代码执行会暂停,等待下次调用e.next之后才会继续执行,这里不涉及返回什么的,就是单纯的控制跳转。

不过这和方法对块参数的yield很不一样,一般用yield是把控制权从方法移交到块里,块里yield又可以移交到哪里呢?

查了一些资料,这种yield和Fiber的yield很相似,但是Enumerator本质上是不是用Fiber构建的还不清楚。

f = Fiber.new do
  Fiber.yield 1
  Fiber.yield 2
end

f.resume # => 1
f.resume # => 2

Fiber是一种可控的Thread,控制权可以通过yield和resume随意转移,yield之后Fiber就会被冻结,等待resume的唤醒。

Enumerator大概搞明白之后,就开始Stream类的构建。

class Stream
  def initialize &p
    @enumerator = Enumerator.new &p
    @evaluated = 0
    @values = []
  end

  def [] n
    if n >= @evaluated
      (@evaluated..n).each do |n|
        @evaluated += 1
        @values[n] = @enumerator.next
      end
    end
    @values[n]
  end

  def first n = 1
    n == 1 ? self[0] : (0..n-1).map{|i| self[i]}
  end

  # y << 等价于 y.yield
  def rest n = 1
    Stream.new do |y|
      loop do
        y << self[n]
        n += 1
      end
    end
  end

  def map &p
    Stream.new do |y|
      n = 0
      loop do
        y << p.call(self[n])
        n += 1
      end
    end
  end

  def accumulate &p
    Stream.new do |y|
      n = 0
      loop do
        y << (0..n).collect{|n| self[n]}.reduce(&p)
        n += 1
      end
    end
  end

end

Enumerator只是一段不断向前执行的代码,所以要把每次执行的结果保存起来,并提供索引访问的方法,才是一个真正的序列。而且缓存可以避免每次访问,Eumerator都要从头开始计算。

我把.next求出来的值存到一个数组里,并保存现在计算到第几项,如果访问已经计算过的项就从values数组中返回,否则就进行计算。这就实现了lazy evaluation(或者说Enumerator本身就是lazy的)。

之后还要提供一些处理流的方法,比如map,这些方法也应该返回lazy的流,所以方法体都是流的创建。

实际上这里有很多重复的代码,还有频繁地赋值,但是我还没想到该怎么去抽象。

试试按书上的做法去计算圆周率:

# 根据π/4 = 1 - 1/3 + 1/5 - 1/7 + ...

# seq 是 1, -1/3, 1/5, -1/7, ... 的流
seq = Stream.new do |y|
  n = 1
  a = 1
  loop do
    y << a * (1.0 / n)
    n = n + 2
    a = -a
  end
end

#sum是seq n项和的流
sum = seq.accumulate{|s,x| s + x}
#把sum每项扩大4倍就是pi的流
pi = sum.map{|x| x*4}

pi.first(10) # => [4.0, 2.666666666666667, 3.466666666666667, 2.8952380952380956, 3.3396825396825403, 2.9760461760461765, 3.2837384837384844, 3.017071817071818, 3.2523659347188767, 3.0418396189294032]

#但是这个流收敛得很慢,用书上给的欧拉加速收敛的方法变形一遍
def eular_transform s
  Stream.new do |y|
    n = 1
    loop do
      s0, s1, s2 = s[n-1], s[n], s[n+1]
      y << s2 - ((s2 - s1) ** 2) / (s0 + -2 * s1 + s2)
      n += 1
    end
  end
end

(eular_transform pi).first(10) # => [3.166666666666667, 3.1333333333333337, 3.1452380952380956, 3.13968253968254, 3.1427128427128435, 3.1408813408813416, 3.142071817071818, 3.1412548236077655, 3.1418396189294033, 3.141406718496503]

#快了不少,对变形后的流还可以不断地应用变形,实现更快的加速
def accelerate s
  Stream.new do |y|
    loop do
      s = eular_transform s
      y << s.first
    end
  end
end

(accelerate pi).first(10) # => [3.166666666666667, 3.142105263157895, 3.141599357319005, 3.1415927140337785, 3.1415926539752927, 3.1415926535911765, 3.141592653589778, 3.1415926535897953, 3.141592653589795, NaN]

Ruby实现计算出的结果和Scheme是完全一致的,但是Ruby的实现总是有点怪,因为Scheme里的流本质上是链表,而我做出来的是数组。这样就没办法递归地去创建流,比如下面这样:

;ones是生成1, 1, 1, ...的流,把首项设为1,把下一项指向自身,这样访问下一项就是访问自身的首项

(define ones
  (cons-stream 1 ones))

不过流的本质就是迭代,scheme是用一个proc去迭代,ruby是用loop去迭代,ruby把Enumerator写成一段迭代的代码,还是很酷的。

实际上单纯用lambda也是可以实现Enumerator的构造的,只是没有Fiber那样magic:

class Enum
  def initialize &p
    @enumerator = p.call
  end

  def next
    @enumerator.call
  end
end

e = Enum.new do
  n = 0
  ->{ n += 1 }
end

p e.next  # => 1

联动: [译] Ruby 2.0 Works Hard So You Can Be Lazy Why do we need fibers

共收到 1 条回复

Enumerator 和 Fiber其实就是 Coroutine

需要 登录 后方可回复, 如果你还没有账号请点击这里 注册