Chào mừng các bạn quay lại với một kỳ mới của Ruby Magic! Một năm trước, chúng ta đã tìm hiểu về module Enumerable của Ruby, 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 enumerable như mảng, phạm vi (ranges) và hash.
Lúc đó, chúng ta đã tạo một lớp LinkedList để minh họa cách làm cho một đối tượng trở thành enumerable bằng cách triển khai phương thức #each trên nó. Bằng cách include module Enumerable, chúng ta có thể gọi các phương thức như #count, #map và #select trên bất kỳ linked list nào mà không cần tự triển khai chúng.
Chúng ta đã học cách sử dụng enumerables, nhưng chúng hoạt động như thế nào? Một phần phép màu của enumerables trong Ruby đến từ việc triển khai nội bộ của chúng, hoàn toàn dựa trên phương thức #each đơn lẻ, thậm chí cho phép chuỗi (chaining) các enumerator.
Hôm nay, chúng ta sẽ tìm hiểu cách các phương thức trong module Enumerable được triển khai và cách các đối tượng Enumerator cho phép chuỗi các phương thức enumeration.
Như các bạn đã quen, chúng ta sẽ đi sâu bằng cách triển khai các phiên bản riêng của module Enumerable và lớp Enumerator. Vậy hãy đội nón bảo hiểm "over-engineering" và bắt đầu thôi!
Linked Lists (Danh sách liên kết)
Trước khi bắt đầu, hãy bắt đầu với một phiên bản mới của lớp linked list chúng ta đã 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 endKhác với phiên bản trước, triển khai này cho phép tạo các danh sách rỗ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 truyền một linked list làm tail khi khởi tạo một linked list 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, lớp LinkedList của chúng ta include module Enumerable. Khi map qua một đối tượng sử dụng một trong các phương thức của Enumerable, kết quả được lưu trữ trong một mảng. Lần này, chúng ta sẽ triển khai phiên bản riêng để đảm bảo các phương thức của chúng ta trả về linked list mới thay vì mảng.
Các phương thức Enumerable
Module Enumerable của Ruby đi kèm với các phương thức enumeration như #map, #count, và #select. Bằng cách triển khai phương thức #each và include module Enumerable vào lớp của chúng ta, chúng ta có thể sử dụng các phương thức đó trực tiếp trên linked list.
Thay vào đó, chúng ta sẽ triển khai DIYEnumerable và include 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ẽ cho chúng ta cái nhìn rõ ràng về cách enumeration hoạt động bên trong.
Hãy bắt đầu với #count. Mỗi phương thức có thể include trong lớp Enumerable sử dụng phương thức #each chúng ta đã triển khai trong lớp LinkedList để lặp qua đối tượng và tính toán kết quả.
module DIYEnumerable def count result = 0 each { |element| result += 1 } result end endTrong ví dụ này, chúng ta đã triển khai phương thức #count trên module DIYEnumerable mới mà chúng ta sẽ include vào linked list. Nó khởi tạo một bộ đếm bằng 0 và gọi phương thức #each để cộng 1 vào bộ đếm cho mỗi lần 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 endPhương thức #map được triển khai tương tự. Thay vì giữ một bộ đếm, nó sử dụng một accumulator (bộ tích lũy), bắt đầu là một danh sách rỗng. Chúng ta sẽ lặp qua tất cả các phần tử trong danh sách, và yield block được truyền cho mỗi phần tử. Kết quả của mỗi yield được thêm vào accumulator list.
Phương thức trả về accumulator sau khi lặp qua tất cả các phần tử trong danh sách đầu vào.
class LinkedList include DIYEnumerable #... endSau khi include DIYEnumerable vào LinkedList, chúng ta có thể kiểm tra các phương thức #count và #map mới thêm.
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 thức đều hoạt động! Phương thức #count đếm đúng số mục trong danh sách, và phương thức #map chạy một block cho mỗi mục và trả về một danh sách đã cập nhật.
Danh sách bị đảo ngược
Tuy nhiên, phương thức #map dường như đã đảo ngược danh sách. Điều đó dễ hiểu, vì phương thức #<< trên lớp linked list của chúng ta thêm các mục vào đầu danh sách thay vì thêm vào cuối, đây là một đặc điểm của bản chất đệ quy của linked list.
Đối với các tình huống cần giữ nguyên thứ tự của danh sách, chúng ta cần một cách để đảo ngược danh sách khi mapping qua nó. Ruby triển khai Enumerable#reverse_each, lặp qua một đối tượng theo thứ tự ngược. Điều đó nghe có vẻ như một giải pháp tuyệt vời cho vấn đề của chúng ta. Rất tiếc, chúng ta không thể sử dụng cách tiếp cận đó vì danh sách của chúng ta được lồng nhau. Chúng ta không biết danh sách dài bao nhiêu cho đến khi lặp qua toàn bộ nó.
Thay vì chạy block qua danh sách theo thứ tự ngược, chúng ta sẽ thêm một phiên bản của #reverse_each làm điều này trong hai bước. Nó trước tiê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 block qua 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 endBây giờ, chúng ta sẽ sử dụng #reverse_each trong phương thức #map của mình, để đả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]]] Hoạt động! Bất cứ khi nào chúng ta gọi phương thức #map trên một linked list, chúng ta sẽ nhận được một danh sách mới theo cùng thứ tự với danh sách gốc.
Chuỗi Enumeration với Enumerators
Thông qua phương thức #each được triển khai trên lớp linked list và DIYEnumerable được include, chúng ta hiện có thể lặp cả hai chiều và map qua linked lists.
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, nếu chúng ta cần map qua một danh sách theo thứ tự ngược? Vì chúng ta hiện đảo ngược danh sách trước khi map qua nó, nó luôn trả về theo cùng thứ tự với danh sách gốc. Chúng ta đã triển khai cả #reverse_each và #map, nên chúng ta nên có thể chuỗi chúng lại với nhau để map ngược. May mắn thay, lớp Enumerator của Ruby có thể giúp với việc đó.
Lần trước, chúng ta đã đảm bảo gọi Kernel#to_enum nếu phương thức LinkedList#each được gọi mà không có block. Điều này cho phép chuỗi các phương thức enumeration bằng cách trả về một đối tượng Enumerator. Để tìm hiểu cách lớp Enumerator hoạt động, chúng ta sẽ triển khai phiên bản riêng.
class DIYEnumerator include DIYEnumerable def initialize(object, method) @object = object @method = method end def each(&block) @object.send(@method, &block) end endGiống như Enumerator của Ruby, lớp enumerator của chúng ta là một wrapper xung quanh một phương thức trên một đối tượng. Bằng cách gọi ngược lại đối tượng được wrap, chúng ta có thể chuỗi các phương thức enumeration.
Điều này hoạt động vì một instance của DIYEnumerator chính nó là enumerable. Nó triển khai #each bằng cách gọi đối tượng được wrap, và include module DIYEnumerable để tất cả các phương thức enumerable có thể được gọi trên nó.
Chúng ta sẽ trả về một instance của lớp DIYEnumerator nếu không có block được truyền cho phương thức LinkedList#each.
class LinkedList # ... def each(&block) if block_given? yield @head @tail.each(&block) if @tail else DIYEnumerator.new(self, :each) end end endSử dụng enumerator của chính chúng ta, chúng ta hiện có thể chuỗi enumeration để lấy kết quả theo thứ tự gốc mà không cần truyền một block rỗng cho lời gọi phương thức #reverse_each.
irb> list = LinkedList.new(73, 12, 42) => [73, [12, [42]]] irb> list.map { |element| element * 10 } => [420, [120, [730]]] Enumeration Eager (hiếu hĩ) và Lazy (lười biếng)
Điều này kết thúc buổi tìm hiểu của chúng ta về triển khai module Enumerable và lớp Enumerator cho đến nay. Chúng ta đã học cách một số phương thức enumerable hoạt động và cách một enumerator giúp chuỗi enumeration bằng cách wrap một đối tượng enumerable.
Tuy nhiên, cách tiếp cận của chúng ta vẫn có một số vấn đề. Theo bản chất, enumeration là eager, nghĩa là nó lặp qua danh sách ngay lập tức khi một trong các phương thức enumerable được gọi trên nó. Mặc dù điều đó ổn trong hầu hết các trường hợp, nhưng mapping qua một danh sách theo thứ tự ngược sẽ đảo ngược danh sách hai lần, điều mà nên là không cần thiết.
Để giảm số lần lặp, chúng ta có thể sử dụng Enumerator::Lazy để trì hoãn việc lặp đến phút chót, và để việc đảo ngược danh sách trùng lặp tự hủy bỏ nhau.
Chúng ta sẽ dành điều đó cho một tập sau. Đừng bỏ lỡ tập đó, và các cuộc thám hiểm sâu hơn vào hoạt động bên trong kỳ diệu của Ruby? Đăng ký bản tin email Ruby Magic để nhận các bài viết mới ngay khi chúng được xuất bản.