Inside Enumeration trong Ruby

Chào mừng bạn trở lại với một phiên bản khác của Ruby Magic! Một năm trước, chúng ta đã biết về Ruby’s Enumerable mô-đun này cung cấp các phương thức bạn sử dụng khi làm việc với các đối tượng có thể liệt kê như mảng, phạm vi và hàm băm.

Hồi đó, chúng tôi đã tạo một LinkedList lớp để chỉ ra cách làm cho một đối tượng có thể liệt kê được bằng cách triển khai #each phương pháp trên đó. Bằng cách bao gồm Enumerable mô-đun, chúng tôi có thể gọi các phương thức như #count , #map và #select trên bất kỳ danh sách được liên kết nào mà không cần phải tự triển khai chúng.

Chúng ta đã học cách sử dụng bảng liệt kê, nhưng chúng hoạt động như thế nào? Một phần của sự kỳ diệu trong các phép liệt kê trong Ruby đến từ việc triển khai bên trong của chúng, tất cả đều dựa trên một #each duy nhất và thậm chí cho phép điều tra chuỗi.

Hôm nay, chúng ta sẽ tìm hiểu cách thức các phương thức trong Enumerable lớp được triển khai và cách Enumerator các đối tượng cho phép các phương thức liệt kê chuỗi.

Như bạn đã quen, chúng tôi sẽ đi sâu hơn bằng cách triển khai các phiên bản Enumerable của riêng chúng tôi mô-đun và Enumerator lớp. Vì vậy, hãy đội mũ bảo hiểm quá kỹ thuật của bạn và bắt đầu!

Danh sách được Liên kết

Trước khi bắt đầu, hãy bắt đầu với phiên bản mới của lớp danh sách liên kết mà chúng tôi đã viết trước đây.

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

Không giống như phiên bản trước, việc triển khai này cho phép tạo danh sách trống, cũng như danh sách có nhiều hơn hai mục. Phiên bản này cũng cho phép chuyển một danh sách được liên kết làm đuôi khi khởi tạo một danh sách khác.

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]]]

Trước đây, LinkedLIst của chúng tôi lớp bao gồm Enumerable mô-đun. Khi ánh xạ qua một đối tượng bằng một trong các Enumerable của phương thức, kết quả được lưu trữ trong một mảng. Lần này, chúng tôi sẽ triển khai phiên bản của riêng mình để đảm bảo các phương pháp của chúng tôi trả về danh sách được liên kết mới.

Phương thức có thể liệt kê

Ruby's Enumerable mô-đun đi kèm với các phương pháp liệt kê như #map , #count và #select . Bằng cách triển khai #each và bao gồm Enumerable trong lớp của chúng tôi, chúng tôi có thể sử dụng các phương pháp đó trực tiếp trên danh sách được liên kết của chúng tôi.

Thay vào đó, chúng tôi sẽ triển khai DIYEnumerable và nhập phiên bản đó thay vì phiên bản của Ruby. Đây không phải là điều bạn thường làm, nhưng nó sẽ cung cấp cho chúng tôi cái nhìn sâu sắc hơn về cách hoạt động của phép liệt kê trong nội bộ.

Hãy bắt đầu với #count . Mỗi phương thức có thể nhập trong Enumerable lớp sử dụng #each phương pháp chúng tôi đã triển khai trong LinkedList của chúng tôi lớp lặp qua đối tượng để tính toán kết quả của chúng.

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

Trong ví dụ này, chúng tôi đã triển khai #count trên một DIYEnumerable mới mô-đun mà chúng tôi sẽ đưa vào danh sách liên kết của chúng tôi. Nó bắt đầu một bộ đếm ở số 0 và gọi #each phương pháp để thêm một vào bộ đếm cho mọi vòng lặp. Sau khi lặp qua tất cả các phần tử, phương thức trả về bộ đếm kết quả.

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

#map phương pháp được thực hiện tương tự. Thay vì giữ một bộ đếm, nó sử dụng một bộ tích lũy, bắt đầu như một danh sách trống. Chúng tôi sẽ lặp lại tất cả các phần tử trong danh sách và mang lại khối được truyền trên mỗi phần tử. Kết quả của mỗi lợi nhuận được thêm vào danh sách tích lũy.

Phương thức trả về bộ tích lũy sau khi lặp qua tất cả các phần tử trong danh sách đầu vào.

class LinkedList
  include DIYEnumerable
 
  #...
end

Sau khi bao gồm DIYEnumerable trong LinkedList của chúng tôi , chúng tôi có thể kiểm tra #count mới được thêm vào của chúng tôi và #map phương pháp.

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

Cả hai phương pháp đều hoạt động! #count phương pháp đếm chính xác các mục trong danh sách và #map phương thức chạy một khối cho mỗi mục và trả về một danh sách đã cập nhật.

Danh sách được đảo ngược

Tuy nhiên, #map phương pháp dường như đã hoàn nguyên danh sách. Điều đó có thể hiểu được, vì #<< phương thức trên lớp danh sách liên kết của chúng tôi thêm các mục vào danh sách thay vì nối chúng, đây là một tính năng của bản chất đệ quy của danh sách được liên kết.

Đối với các tình huống cần giữ lại thứ tự của danh sách, chúng tôi cần một cách để đảo ngược danh sách khi ánh xạ qua nó. Ruby thực hiện Enumerable#reverse_each , vòng lặp ngược lại trên một đối tượng. Đó có vẻ là một giải pháp tuyệt vời cho vấn đề của chúng tôi. Đáng buồn là chúng tôi không thể sử dụng cách tiếp cận như vậy vì danh sách của chúng tôi được lồng vào nhau. Chúng tôi không biết danh sách dài bao lâu cho đến khi chúng tôi lặp lại toàn bộ.

Thay vì chạy ngược lại khối trên danh sách, chúng tôi sẽ thêm một phiên bản của #reverse_each thực hiện hai bước này. Đầu tiên, nó lặp qua danh sách để đảo ngược nó bằng cách tạo một danh sách mới. Sau đó, nó chạy khối trên danh sách đã đảo ngược.

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

Bây giờ, chúng tôi sẽ sử dụng #reverse_each trong #map của chúng tôi để đảm bảo nó được trả về theo đúng thứ tự.

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

Nó hoạt động! Bất cứ khi nào chúng tôi gọi #map của mình trên danh sách được liên kết, chúng tôi sẽ lấy lại danh sách mới theo thứ tự như ban đầu.

Chuỗi điều tra với điều tra viên

Thông qua #each được triển khai trên lớp danh sách được liên kết của chúng tôi và DIYEnumerator được bao gồm , giờ đây chúng tôi có thể lặp lại cả hai cách và ánh xạ qua các danh sách được liên kết.

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]]]

Tuy nhiên, điều gì sẽ xảy ra nếu chúng ta cần bản đồ qua một danh sách ngược lại? Vì bây giờ chúng ta đảo ngược danh sách trước khi ánh xạ qua nó, nó luôn trả về theo thứ tự như danh sách ban đầu. Chúng tôi đã triển khai cả #reverse_each và #map , vì vậy chúng ta có thể xâu chuỗi chúng lại với nhau để có thể lập bản đồ ngược. May mắn thay, Enumerator của Ruby lớp học có thể giúp bạn điều đó.

Lần trước, chúng tôi đã đảm bảo gọi Kernel#to_enum nếu LinkedList#each phương thức được gọi mà không có khối. Điều này cho phép chuỗi các phương thức có thể liệt kê bằng cách trả về một Enumerator sự vật. Để tìm hiểu cách thức Enumerator lớp học hoạt động, chúng tôi sẽ triển khai phiên bản của riêng mình.

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

Giống như Enumerator của Ruby , lớp enumerator của chúng ta là một lớp bao bọc xung quanh một phương thức trên một đối tượng. Bằng cách tạo bọt cho đối tượng được bọc, chúng ta có thể xâu chuỗi các phương pháp liệt kê.

Điều này hoạt động vì một DIYEnumerator cá thể có thể liệt kê được. Nó thực hiện #each bằng cách gọi đối tượng được bọc và bao gồm DIYEnumerable mô-đun để tất cả các phương thức có thể liệt kê có thể được gọi trên nó.

Chúng tôi sẽ trả lại một bản sao của DIYEnumerator của chúng tôi nếu không có khối nào được chuyển đến LinkedList#each phương pháp.

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

Sử dụng bảng liệt kê của riêng chúng tôi, giờ đây chúng tôi có thể liệt kê chuỗi để lấy kết quả theo thứ tự ban đầu mà không cần phải chuyển một khối trống cho #reverse_each cuộc gọi phương thức.

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

Liệt kê háo hức và lười biếng

Điều này kết thúc cái nhìn của chúng tôi về việc triển khai Enumerable mô-đun và Enumerator lớp cho bây giờ. Chúng ta đã tìm hiểu cách hoạt động của một số phương thức liệt kê và cách một điều tra viên giúp xâu chuỗi kiểu liệt kê bằng cách bao bọc một đối tượng có thể liệt kê.

Tuy nhiên, có một số vấn đề với cách tiếp cận của chúng tôi. Về bản chất, phép liệt kê là háo hức , nghĩa là nó lặp lại danh sách ngay khi một trong các phương thức liệt kê được gọi trên đó. Mặc dù điều đó tốt trong hầu hết các trường hợp, nhưng việc ánh xạ ngược danh sách sẽ đảo ngược danh sách hai lần, điều này không cần thiết.

Để giảm số vòng lặp, chúng tôi có thể sử dụng Enumerator::Lazy để trì hoãn việc lặp lại đến giây phút cuối cùng và tự hủy bỏ việc đảo ngược danh sách trùng lặp.

Tuy nhiên, chúng tôi sẽ phải để dành điều đó cho một tập trong tương lai. Bạn không muốn bỏ lỡ điều đó và tiếp tục khám phá cơ chế hoạt động kỳ diệu bên trong của Ruby? Đăng ký nhận bản tin e-mail của Ruby Magic, để nhận các bài viết mới được gửi đến hộp thư đến của bạn ngay sau khi chúng được xuất bản.