0

Xử lý bài toán chuỗi vô hạn trong Ruby

Các ngôn ngữ lập trình chức năng như Clojure có một khái niệm gọi là Sequences (chuỗi). Chuỗi khá thú vị, chúng ta có thể coi các thuật toán như cấu trúc dữ liệu, có thể gọi các hàm thực thi trên dữ liệu được tạo ra, cho phép chúng ta tương tác với kết quả trả về như 1 collection, kể cả khi chuỗi đó là vô hạn.

Thư viện chuẩn Ruby không bao gồm 1 class hay module sequence chính thống, nhưng thay vào đó, Ruby cung cấp cho chúng ta module Enumerable. Lập trình viên Ruby thường biết tới Enumerable thông qua các phương thức với mảng, ví dụ như map hay select. Mảng, ví dụ như [1, 2, 3, 4] thường được coi là mảng hữu hạn, hay 1 chuỗi eagerly loaded, chúng chứa sẫn tất cả các phần tử mà chúng ta muốn liệt kê thông qua methods.

Liệt kê dãy Fibonacci

Dãy Fibonacci cũng được xem là 1 dãy vô hạn. Chúng ta có thể định nghĩa 1 hàm khởi tạo n phần tử đầu tiên trong dãy, với n là tham số truyền vào. Việc thực hiên sẽ như sau:

def eager_fibonacci n
  a = b = 1
  result = []

  loop do
    break if result.size >= n

    result << a
    a, b = b, a + b
  end

  result
end

Hàm này thực thi hoàn toàn ổn, nhưng chúng ta có thể sử dụng một cách khác tối ưu hơn. Thay vì trả về 1 mảng đã được eagerly-loaded, chúng ta có thể trả về 1 Enumerator. Ta sẽ đưa từng phần tử vào Enumerator ngay khi nó được khởi tạo.

def fibonacci
  Enumerator.new do |y|
    a = b = 1

    loop do
      y << a
      a, b = b, a + b
    end
  end
end

Enumerator là một enumberable object (đối tượng tập đếm được) có thể sử dụng cho phép liệt kê trong hoặc ngoài 1 collection

Phương thức khởi tạo Enumerator lấy 1 block hoạt động như 1 template cho thuật toán enumerable. Block này lấy 1 tham số y - là instance của Enumerator::Yielder, cho phép yield từng phần tử Enumerator tới các blocks được truyền tới các lệnh gọi phương thức. Nói 1 cách dễ hiểu hơn, 1 Enumerator có thể được sử dụng như 1 Array.

Để lấy ra 10 phần tử đầu tiên của phép liệt kê Fibonacci, ta có thể làm như sau:

fibonacci.take 10

Chúng ta cũng có thể sử dụng phép liệt kê đối với chuỗi Fibonacci:

fibonacci.take(10).each{|i| puts i}

Sử dụng phương thức Enumerator#lazy, ta có thể hạn chế việc liệt kê trước, và chỉ query hoặc thực thi các phép toán khi mà mỗi phần tử được tạo ra. Điều này mở ra một vài use-cases hay ho, ví dụ như:

fibonacci.lazy.select(&:even?).first(10)
#=> [2, 8, 34, 144, 610, 2584, 10946, 46368, 196418, 832040]

fibonacci.lazy.select(&:odd?).first(10)
#=> [1, 1, 3, 5, 13, 21, 55, 89, 233, 377]

Với ví dụ trên, có thể thấy ta đã lọc ra 10 phần tử chẵn hoặc lẻ được tạo ra bởi dãy Fibonacci. Thêm vào phương thức with_index, ta sẽ thấy có bao nhiêu phần tử được liệt kê ra để có thể lấy được 10 số chẵn hoặc lẻ:

fibonacci.lazy.with_index.select { |n, i| n.odd? }.first(10)
#=> [[1, 0], [1, 1], [3, 3], [5, 4], [13, 6], [21, 7], [55, 9], [89, 10], [233, 12], [377, 13]]

fibonacci.lazy.with_index.select { |n, i| n.even? }.first(10)
#=> [[2, 2], [8, 5], [34, 8], [144, 11], [610, 14], [2584, 17], [10946, 20], [46368, 23], [196418, 26], [832040, 29]]

Hãy để ý rằng, chúng ta chỉ cần liệt kê ra 13 phần tử để lấy được 10 số lẻ đầu tiên trong dãy Fibonacci, trong khi cần tới 29 phần tử để lấy được 10 số chẵn. Kết quả này thực sự không dễ để trả về nếu chúng ta sử dụng cách khai triển trước đó, khi mà số lượng phần tử mong muốn lấy được phải được truyền vào từ đầu.

Sequence Functions

Clojure cung cấp 1 số phương thức hữu dụng cho phép chúng ta khởi tạo chuỗi từ các functions khác. Ví dụ, phương thức repeatedly sẽ lặp lại việc gọi 1 hàm cho trước và trả về kết quả là 1 chuỗi. Để lấy ra được 1 chuỗi 5 số ngẫu nhiên từ 0 đến 100, ta có thể làm như sau:

(take 5 (repeatedly #(rand-int 100)))

Đối với những người chưa tiếp cận nhiều với Clojure câu lệnh trên nhìn có vẻ hơi kỳ, nhưng nó có thể được hiểu là lấy ra 5 kết quả đầu tiên từ việc lặp đi lặp lại hành động yêu cầu 1 số ngẫu nhiên từ 0 đến 100, và kết quả của hành động đó được trả về bằng 1 chuỗi.

Chúng ta có thể làm điều tương tự trong Ruby sử dụng Enumerator. Hãy thử định nghĩa phiên bản Ruby của phương thức repeatedly, phương thức này sẽ liên tục gọi tới 1 block cho trước.

def repeatedly_foo(&block)
 loop do
    block.call
  end
end

Cách triển khai sử dụng vòng lặp như trên khá là ngây ngô, và có vẻ không được thực tế cho lắm bởi hàm đó sẽ không bao giờ trả về - một vòng lặp vô hạn. Để cải thiện, chúng ta sẽ truyền thêm một tham số n là số phần tử tối đa có thể trả về, và break khỏi vòng lặp sử dụng bộ đếm:

def repeatedly_foo(n, &block)
  result = []

  loop do
    break if result.size >= n

    result << block.call
  end

  result
end

Khá ổn, nhưng cũng như ví dụ về dãy Fibonacci trước đó, chúng ta phải load trước 1 số lượng mong muốn trong mảng trả về. Để tối ưu hóa, 1 lần nữa chúng ta sẽ bọc vòng lặp trong 1 lớp Enumerator để có thể sử dụng kết quả trả về như 1 chuỗi:

def repeatedly &block
  Enumerator.new do |y|
    loop do
      y << block.call # "yield" the result to the Enumerator::Yielder
    end
  end
end

Thông qua cách định nghĩa trên, chúng ta có 1 lớp trừu tượng, có thể được chained tới các phương thức enumrator khác. Và việc gọi hàm trông khá giống với cảm hứng lấy từ Clojure trước đó:

repeatedly { rand(100) }.take(5)
#=> [48, 48, 72, 41, 70] # your results will vary... they're random!

Lời kết

Tất nhiên, sequence không phải là khái niệm duy nhất có thể được mô hình hóa theo cách này trong Ruby. Bất kỳ collection có kích thước không xác định, ví dụ, kết quả từ việc truy vấn, tài nguyên được phân trang được trả về từ API, dữ liệu từ thu thập web crawler, v.v., cũng là các use-cases hay để hiển thị dưới dạng liệt kê. Hãy cân nhắc việc gói các collection được khởi tạo bằng Enumerator có thể xử lý việc gọi hàm 1 cách linh hoạt hơn.


Bài viết được dịch từ Infinite Sequences in Ruby


All rights reserved

Viblo
Hãy đăng ký một tài khoản Viblo để nhận được nhiều bài viết thú vị hơn.
Đăng kí