Những điều cần biết về Ruby: Bộ nhớ tạm LRU và cây nhị phân

Ta thường thấy các vấn đề về thuật toán và cấu trúc dữ liệu xuất hiện trong phỏng vấn tuyển dụng cho vị trí phát triển phần mềm. Với Ruby, việc luyện tập hoàn toàn có thể giúp bạn xử lý dễ dàng các vấn đề nêu trên. Chúng tôi đã đề cập đến các phần cơ bản như: danh sách liên kết (linked lists) và hash table. Lần này, chúng ta sẽ tìm hiểu sâu hơn, cụ thể là về cây nhị phân và cách thức thực thi bộ nhớ tạm LRU bằng ngôn ngữ Ruby.

LRU Cache

Giả dụ ta muốn xây dựng một bộ nhớ tạm chỉ có thể ghi nhớ một lượng phần tử cố định. Giả dụ này đặt ra một câu hỏi: Nếu ta muốn thêm phần tử khi bộ nhớ tạm đã đầy thì sao? Quy tắc trục xuất LRU – Least Recently Used là một giải pháp thường thấy. Cụ thể hơn, những phần tử có tầng suất sử dụng ít nhất trong bộ nhớ tạm sẽ bị loại bỏ và thay bằng phần tử mới hơn.

Từ đó lại nảy sinh một vấn đề nữa: ta cần thực thi bộ nhớ tạm LRU như thế nào sao cho hiệu quả? Bộ nhớ tạm phải có khả năng thực hiện các công việc như sau. Đầu tiên, bộ nhớ tạm phải thêm được phần tử lẫn khóa đi kèm nó. Hơn nữa, bộ nhớ tạm phải cho phép ta xuất được phần tử thông qua khóa đi kèm tương ứng.

Đây là vấn đề rất hay được hỏi đến trong các cuộc phỏng vấn, ngay từ vòng đầu tiên. Để có câu trả lời phù hợp, ta cần kết hợp nhiều khái niệm khác nhau. Bộ nhớ tạm LRU thường được thực thi dưới dạng hash table và danh sách liên kết kép (ta có thể dùng cây splay, tuy cách này ít được ưa chuộng hơn). Nguyên lý làm việc của giải pháp như sau. Các khóa trong hash table bao gồm khóa trong bộ nhớ tạm, và các giá trị (values) thực ra chính là node trong danh sách liên kết kép.

Ta phải liên tục kiểm tra phần đầu và đuôi danh sách này. Khi cần xuất một giá trị khỏi bộ nhớ tạm, ta sẽ tìm khóa trong hash table và được trả về node tương ứng trong danh sách liên kết kép. Tiếp đó, ta sẽ dời node này về cuối danh sách. Khi đó, phần tử có tầng suất sử dụng ít nhất sẽ luôn ở đầu danh sách. Và khi ta muốn thêm phần tử mới vào bộ nhớ tạm đã đầy, chỉ cần loại bỏ một phần tử khỏi đầu danh sách.

Với Ruby, để thực thi lệnh này, ta trước hết cần một danh sách liên kết kép. Đây là công việc dễ thực hiện:

Đây chỉ mới đơn thuần là việc theo dõi các node trước và sau. Tiếp tới, ta sẽ thực thi bộ nhớ tạm. Như đã đề cập, ta cần theo dõi: đầu danh sách, cuối danh sách và số phần tử trong bộ nhớ tạm.

Tiếp đó, hãy tìm cách thực thi phương pháp set(key, value)

Đoạn code trên đã khá rõ ràng. Đầu tiên, ta sẽ kiểm tra xem bộ nhớ tạm đã đầy chưa. Nếu đầy, loại bỏ phần đầu danh sách liên kiết kép để tạo chỗ trống.  Kế tiếp, ta sẽ tạo một node mới với giá trị tương ứng và gán và cuối danh sách. Cuối cùng, ta sẽ thêm node mới này (hiện đã ở cuối danh sách liên kết kép) vào bảng với khóa tương ứng. Quá trình “get” sẽ cần đến một số code khá phức tạp:

Mục tiêu của phương pháp “get” là để trả về node đi kèm và khóa, sau đó chuyển node này đến cuối danh sách. Nếu  node đi kèm đã ở cuối danh sách, thì ta sẽ quay lại (đây cũng là lý do ta phải kiểm tra “next_node” trong “res”). Nếu node ta chọn ra lại ở đầu danh sách, ta sẽ phải chuyển phần đầu. Nếu node cũng không ở đầu danh sách, ta phải “chọn” ra từ phần giữa danh sách. Cuối cùng, chuyển node này xuống cuối danh sách. Khi đã hoành thành, ta có thể thử thực thi bộ nhớ tạm một cách dễ dàng:

Nếu bạn muốn chắc chắn rằng bạn đã hiểu rõ quy trình, hãy thử dự đoán kết quả hiển thị của đoạn code. Nếu bạn đã hiểu rõ cách xây dựng hash table và danh sách liên kết kép,  những việc như thực thi bộ nhớ tạm LRU sẽ không quá khó khăn.

CÂY NHỊ PHÂN

Một câu hỏi nữa thường thấy trong các cuộc phỏng vấn là về cây nhị phân “cơ bản”. Giải pháp cho vấn đề này cũng khá đơn giản. Ta sẽ dùng đến hai liên kết hay vì chỉ dùng một liên kết cho mỗi node như thường thấy với danh sách liên kết đơn. Hai liên kết này sẽ dẫn đến “con cái” của node đó. Chắc bạn đã có thể hình dung được đại khái cách thể hiện bằng Ruby:

Nếu ta muốn hiện quá trình này? Ta có thể lựa chọn trong số các cách thức sau: “pre-order”,”in-order”, và “post-order traversal”. Dùng “pre-order” khi ta xem xét node trước, rồi đến cây-phụ trái và cây-phụ phải. Dùng “in-order” cho cây-phụ trái, cây-phụ phải rồi mới đến node. Hãy tìm hiểu cách thực thi in-order traversal. Thay vì phải xây dựng biến lặp thể hiện quá trình loại bỏ, ta chỉ cần trình diễn các giá trị node như sau:

Phương pháp sẽ theo đúng như định nghĩa. Miễn là các cây phụ không trống, ta sẽ loại bỏ chúng và hiện giá trị của node “current” gặp được. Ta có thể chạy thử:

Đoạn code này sẽ hiện một, hai và ba trên các dòng khác nhau. Tiếp đến, ta phải làm gì để thực thi lệnh này dưới dạng liệt kê để kết hợp với “each”? Hãy xem thử:

Đoạn code này có chút đặc biệt vì nó hiện rõ block với “&block”.Ta cần phải làm như vậy vì ta đang đệ quy trong “inorder”. Nói cách khác, mỗi bước đệ quy phải đi sâu vào block. Phương pháp này rất dễ thực hiện:

Thực thi pre-order và post-order traversal hầu như chỉ xoay quanh “yield”. Vậy nên, hãy tập trung vào vấn đề khác hơn.

Cây tìm kiếm nhị phân cũng là một chủ đề hay được hỏi đến trong phỏng vấn. Kiểu cây nhị phân này mang một tính chất rất đặc biệt và cực kỳ hữu ích. Với mỗi node, giá trị kèm theo node thường lớn hơn hoặc bằng với giá trị của nó trong bảng-phụ trái, hay nhỏ hơn hoặc bằng với bảng-phụ phải. Từ đó dấy lên câu hỏi (thường được hỏi nhất): làm sao ta có thể phân biệt được một cây nhị phân có phải là cây tìm kiếm nhị phân (binary search tree – BST) hay không?

Việc suy nghĩ theo lối đệ quy rất cần thiết với các vấn đề liên quan đến cây nhị phân. Mỗi node đều có một cây-phụ trái và một cây-phụ phải (hai cây này có thể trống) và tương tự đối với mỗi node ở hai cây-phụ. Ta hãy tập trung vào vấn đề này trước.

Trước hết, hãy bắt đầu với trường hợp cơ bản. Nếu ta có một node duy nhất với cả hai cây-phụ trống (ví dụ như node lá), vậy thì node đơn lẻ này chắc chắn là BST vì nó đáp ứng được tính chất của BST.

Bây giờ, hãy xét đến một node chỉ có một subtree, và khi ta đã chắc chắn sub-tree đó là BST. Nếu node được xét đến mang giá trị lớn hơn hoặc bằng root của subtree (của node), ta sẽ luôn có một BST.

Đến đây, ta có thể thấy rằng, nếu cả hai subtree của một node nhất định đều là BST và node xét đến mang giá trị nằm giữa giá trị của hai nhánh con, thì cả cây này sẽ là BST. Hãy chuyển ý tưởng này thành một đoạn code:

May mắn thay, khi ta đã hình dung được cách đệ quy trong đầu, việc chuyển đổi thành code sẽ trở nên rất dễ dàng. Ta sẽ kiểm tra xem, liệu node hiện hành có phá vỡ định nghĩa về BST hay không. Đồng thời kiểm tra theo cách đệ quy liệu cách cây-phụ cũng có hiện tượng tương tự. Ta có thể dùng (sử dụng “root” được xác định trước đó):

Thử nghiệm với các phương pháp trên có thể giúp bạn hiểu rõ hơn về cách thức làm việc của phép đệ quy và giá trị của definition BST.

LỜI KẾT

Hôm nay, ta đã nghiên cứu về bộ nhớ tạm LRU và cây nhị phân trong ngôn ngữ Ruby (hay bất cứ dạng ngôn ngữ nào, nếu bạn chỉ quan tâm đến cách thức giải quyết vấn đề trong phỏng vấn) dưới dạng một số câu hỏi phỏng vấn thường gặp. Ở bài tiếp theo, ta sẽ tìm hiểu một số vấn đề khó nhằn hơn liên quan đến khái niệm từ nhiều kiểu cấu trúc dữ liệu và thuật toán khác nhau.

Topdev via Sitepoint