Rubyの内部列挙

Ruby Magicの別のエディションへようこそ！ 1年前、RubyのEnumerableについて学びました モジュール。配列、範囲、ハッシュなどの列挙可能なオブジェクトを操作するときに使用するメソッドを提供します。

当時、私たちはLinkedListを作成しました #eachを実装してオブジェクトを列挙可能にする方法を示すクラス その上でメソッド。 Enumerableを含めることによって モジュールでは、#countのようなメソッドを呼び出すことができました 、#map および#select 自分で実装しなくても、リンクリストに追加できます。

列挙型の使用方法を学びましたが、どのように機能しますか？ Rubyの列挙型の魔法の一部は、すべて単一の#eachに基づく内部実装に由来します。 メソッド、さらには列挙子を連鎖させることもできます。

今日は、Enumerableのメソッドがどのように機能するかを学習します クラスの実装方法とEnumerator オブジェクトを使用すると、列挙メソッドを連鎖させることができます。

慣れてきたら、独自のバージョンのEnumerableを実装して詳しく説明します。 モジュールとEnumerator クラス。だから、あなたの過剰設計のヘルメットをかぶって行きましょう！

リンクリスト

始める前に、以前に作成したリンクリストクラスの新しいバージョンから始めましょう。

class LinkedList
  def initialize(head = nil, *rest)
    @head = head
 
    if rest.first.is_a?(LinkedList)
      @tail = rest.first
    elsif rest.any?
      @tail = LinkedList.new(*rest)
    end
  end
 
  def <<(head)
    @head ? LinkedList.new(head, self) : LinkedList.new(head)
  end
 
  def inspect
    [@head, @tail].compact
  end
 
  def each(&block)
    yield @head if @head
    @tail.each(&block) if @tail
  end
end

以前のバージョンとは異なり、この実装では、空のリスト、および3つ以上のアイテムを含むリストを作成できます。このバージョンでは、別のリンクリストを初期化するときに、リンクリストをテールとして渡すこともできます。

irb> LinkedList.new
=> []
irb> LinkedList.new(1)
=> [1]
irb> LinkedList.new(1, 2)
=> [1,[2]]
irb> LinkedList.new(1, 2, 3)
=> [1,[2,[3]]]
irb> LinkedList.new(1, LinkedList.new(2, 3))
=> [1,[2,[3]]]
irb> LinkedList.new(1, 2, LinkedList.new(3))
=> [1,[2,[3]]]

以前は、LinkedLIst クラスにはEnumerableが含まれていました モジュール。 Enumerableのいずれかを使用してオブジェクトにマッピングする場合 のメソッドでは、結果は配列に格納されます。今回は、独自のバージョンを実装して、メソッドが代わりに新しいリンクリストを返すようにします。

列挙可能なメソッド

RubyのEnumerable モジュールには、#mapなどの列挙メソッドが付属しています 、#count 、および#select 。 #eachを実装する メソッドとEnumerableを含む クラスのモジュールでは、リンクリストでこれらのメソッドを直接使用できます。

代わりに、DIYEnumerableを実装します Rubyのバージョンの代わりにそれをインポートします。これは通常行うことではありませんが、列挙が内部でどのように機能するかについて明確な洞察を得ることができます。

#countから始めましょう 。 Enumerableのインポート可能な各メソッド クラスは#eachを使用します LinkedListに実装したメソッド オブジェクトをループして結果を計算するクラス。

module DIYEnumerable
  def count
    result = 0
    each { |element| result += 1 }
    result
  end
end

この例では、#countを実装しました 新しいDIYEnumerableのメソッド リンクリストに含めるモジュール。ゼロからカウンターを開始し、#eachを呼び出します ループごとに1つをカウンターに追加するメソッド。すべての要素をループした後、メソッドは結果のカウンターを返します。

module DIYEnumerable
  # ...
 
  def map
    result = LinkedList.new
    each { |element| result = result << yield(element) }
    result
  end
end

#map メソッドも同様に実装されます。カウンターを保持する代わりに、空のリストとして開始するアキュムレーターを使用します。リスト内のすべての要素をループし、各要素で渡されたブロックを生成します。各歩留まりの結果は、アキュムレータリストに追加されます。

このメソッドは、入力リスト内のすべての要素をループした後、アキュムレータを返します。

class LinkedList
  include DIYEnumerable
 
  #...
end

DIYEnumerableを含めた後 LinkedListで 、新しく追加した#countをテストできます および#map メソッド。

irb> list = LinkedList.new(73, 12, 42)
=> [73, [12, [42]]]
irb> list.count
=> 3
irb> list.map { |element| element * 10 }
=> [420, [120, [730]]]

どちらの方法でも機能します。 #count メソッドはリスト内のアイテムを正しくカウントし、#map メソッドはアイテムごとにブロックを実行し、更新されたリストを返します。

反転リスト

ただし、#map メソッドがリストを元に戻したようです。 #<<として、それは理解できます リンクリストクラスのメソッドは、アイテムを追加するのではなく、リストに追加します。これは、リンクリストの再帰的な性質の機能です。

リストの順序を維持することが不可欠な状況では、リストをマッピングするときにリストを逆にする方法が必要です。 RubyはEnumerable#reverse_eachを実装します 、オブジェクトを逆にループします。それは私たちの問題に対する優れた解決策のように聞こえます。残念ながら、リストがネストされているため、このようなアプローチを使用することはできません。リストを完全にループするまで、リストの長さはわかりません。

リストに対してブロックを逆に実行する代わりに、#reverse_eachのバージョンを追加します これはこの2つのステップを実行します。最初にリストをループして、新しいリストを作成してリストを反転します。その後、反転したリストに対してブロックを実行します。

module DIYEnumerable
  # ...
 
  def reverse_each(&block)
    list = LinkedList.new
    each { |element| list = list << element }
    list.each(&block)
  end
 
  def map
    result = LinkedList.new
    reverse_each { |element| result = result << yield(element) }
    result
  end
end

次に、#reverse_eachを使用します #mapで メソッド、正しい順序で返されることを確認します。

irb> list = LinkedList.new(73, 12, 42)
=> [73, [12, [42]]]
irb> list.map { |element| element * 10 }
=> [730, [120, [420]]]

できます！ #mapを呼び出すときはいつでも リンクリストのメソッドを使用すると、元のリストと同じ順序で新しいリストが返されます。

列挙子を使用した列挙の連鎖

#eachを介して リンクリストクラスに実装されたメソッドと含まれているDIYEnumerator 、これで、双方向をループして、リンクリストにマッピングできます。

irb> list.each { |x| p x }
73
12
42
irb> list.reverse_each { |x| p x }
42
12
73
irb> list.reverse_each.map { |x| x * 10 }
=> [730, [120, [420]]]
=> [420, [120, [730]]]

ただし、マップが必要な場合はどうなりますか 逆にリストを超えますか？リストをマッピングする前にリストを逆にするため、常に元のリストと同じ順序で返されます。すでに両方の#reverse_eachを実装しています および#map 、したがって、それらをチェーンして逆方向にマップできるようにする必要があります。幸い、RubyのEnumerator クラスはそれを助けることができます。

前回は、必ずKernel#to_enumを呼び出しました。 LinkedList#eachの場合 メソッドはブロックなしで呼び出されました。これにより、Enumeratorを返すことで、列挙可能なメソッドを連鎖させることができました。 物体。 Enumeratorの方法を確認するには クラスは機能します。独自のバージョンを実装します。

class DIYEnumerator
  include DIYEnumerable
 
  def initialize(object, method)
    @object = object
    @method = method
  end
 
  def each(&block)
    @object.send(@method, &block)
  end
end

RubyのEnumeratorのように 、列挙子クラスは、オブジェクトのメソッドのラッパーです。ラップされたオブジェクトにバブリングすることで、列挙メソッドを連鎖させることができます。

これは、DIYEnumeratorが機能するために機能します インスタンス自体は列挙可能です。 #eachを実装します ラップされたオブジェクトを呼び出すことにより、DIYEnumerableが含まれます モジュールなので、列挙可能なすべてのメソッドを呼び出すことができます。

DIYEnumeratorのインスタンスを返します LinkedList#eachにブロックが渡されない場合のクラス メソッド。

class LinkedList
  # ...
 
  def each(&block)
    if block_given?
      yield @head
      @tail.each(&block) if @tail
    else
      DIYEnumerator.new(self, :each)
    end
  end
end

独自の列挙子を使用して、列挙をチェーンし、空のブロックを#reverse_eachに渡すことなく、元の順序で結果を取得できるようになりました。 メソッド呼び出し。

irb> list = LinkedList.new(73, 12, 42)
=> [73, [12, [42]]]
irb> list.map { |element| element * 10 }
=> [420, [120, [730]]]

熱心で怠惰な列挙

これで、Enumerableの実装についての概要は終わりです。 モジュールとEnumerator 今のところクラス。列挙可能なメソッドのいくつかがどのように機能するか、および列挙子が列挙可能なオブジェクトをラップすることによって列挙を連鎖させるのにどのように役立つかを学びました。

ただし、私たちのアプローチにはいくつかの問題があります。その性質上、列挙は熱心です 、つまり、列挙可能なメソッドの1つがリストで呼び出されるとすぐに、リストをループします。ほとんどの場合、これで問題ありませんが、リストを逆にマッピングすると、リストが2回反転するため、不要です。

ループの数を減らすために、Enumerator::Lazyを使用できます。 ループを最後の瞬間まで遅らせ、重複リストを反転させると、自動的にキャンセルされます。

ただし、将来のエピソードのためにそれを保存する必要があります。それを見逃したくない、そしてRubyの魔法の内部の仕組みへのさらなる遠征？ Ruby Magicの電子メールニュースレターを購読して、新しい記事が公開されるとすぐに受信トレイに配信されるようにします。