Bài trước đo cái giá vật lý của đệ quy: ngăn xếp lời gọi. Bài này đo một cái giá âm hiểm hơn — cái giá tính toán của một kiểu đệ quy nhìn có vẻ hoàn toàn vô hại. Hàm Fibonacci đệ quy là đoạn code sạch nhất, tự nhiên nhất bạn có thể viết: fib(n) = fib(n-1) + fib(n-2). Nó đúng, nó gọn, nó khớp y hệt định nghĩa toán học. Và nó là một trong những cái bẫy hiệu năng ngoạn mục nhất trong lập trình. Bài này đo cái bẫy đó nổ lớn tới đâu, rồi đo cách quy hoạch động tháo ngòi nó — một kỹ thuật nghe cao siêu nhưng thực ra chỉ là một ý tưởng tầm thường.
Vấn đề: bài toán con chồng lấn
Nhìn kỹ cây gọi của fib(5): nó gọi fib(4) và fib(3); fib(4) lại gọi fib(3) và fib(2). Vậy fib(3) được tính hai lần, hoàn toàn độc lập, không ai nhớ ai. Xuống sâu hơn, fib(2) được tính ba lần, fib(1) năm lần. Đây là bài toán con chồng lấn: cùng một bài con bị giải đi giải lại ở nhiều nhánh khác nhau của cây đệ quy. Số lần tính lại không cộng dồn tuyến tính — nó nhân lên theo hàm mũ. Tôi đo để thấy con số thật.
Đo: 1,4 tỉ lời gọi cho một số
Tôi chạy Fibonacci đệ quy naive, đếm số lời gọi và bấm giờ, ở vài giá trị n:
n số lời gọi thời gian
30 2 692 537 0,8 ms
35 29 860 703 9,6 ms
40 331 160 281 118,8 ms
43 1 402 817 465 447,3 ms
Nhìn cột số lời gọi: mỗi khi n tăng thêm 5, số lời gọi nhân lên khoảng 11 lần — đó là dáng của tăng trưởng mũ (cụ thể ~1,6ⁿ). Để tính fib(43) — một con số duy nhất — máy phải gọi hàm 1,4 tỉ lần. Không phải vì phép cộng đắt, mà vì gần như toàn bộ 1,4 tỉ lời gọi đó lặp lại công việc đã làm rồi. Ngoại suy tiếp: fib(50) sẽ mất hàng chục giây, fib(60) hàng giờ — cho một phép tính mà lẽ ra chỉ cần 60 phép cộng. Đây là chỗ nhiều người vấp, và tôi cũng vào bài với đúng cái vấp đó.
Một lần tôi đo hớ: DP không phải phép màu, chỉ là "đừng tính lại"
Tôi thú thật đã từng nghĩ về "quy hoạch động" như một kỹ thuật cao cấp, một thứ thuật toán tinh vi cần bảng biểu và công thức truy hồi rắc rối. Đo xong tôi thấy nó tầm thường tới mức gần như thất vọng: nó chỉ là nhớ kết quả để khỏi tính lại. Cả bí quyết nằm ở đó.
Cách đơn giản nhất — memoization — giữ nguyên hàm đệ quy, chỉ thêm một bảng nhớ: trước khi tính fib(k), kiểm tra xem đã tính chưa; nếu rồi thì trả ngay kết quả đã lưu, nếu chưa thì tính rồi lưu lại. Một dòng thêm vào. Đo fib(43) phiên bản memo:
fib(43) naive : 1 402 817 465 lời gọi, 447 ms
fib(43) memo : 85 lời gọi, 0,17 micro giây
Từ 1,4 tỉ lời gọi xuống 85, từ 447 mili giây xuống dưới một micro giây — nhanh hơn khoảng hai triệu lần. Và tất cả khác biệt đó chỉ đến từ việc từ chối tính lại một bài con đã giải. Bài học đo lường: khi một thuật toán chậm theo hàm mũ vì bài con chồng lấn, cái đắt là sự tính lại, và quy hoạch động chỉ là xóa bỏ sự tính lại đó — không có phép màu nào, chỉ là một cái bảng nhớ. "Đừng tính lại" biến hàm mũ thành tuyến tính. Nếu bạn từng thấy DP đáng sợ, hãy nhớ nó chỉ là câu đó.
Memo hay tabulation? Đo cái giá của cách nhớ
Có hai cách hiện thực cái ý "đừng tính lại", và tôi đo cả hai. Memoization (top-down) là cái vừa nói: đệ quy cộng một bảng nhớ. Tabulation (bottom-up) đi ngược: bỏ hẳn đệ quy, điền bảng từ giá trị nhỏ nhất lên bằng một vòng lặp — bảng[i] = bảng[i-1] + bảng[i-2]. Cả hai đều O(n), nhưng đo ra chúng không bằng nhau:
tính fib tới n=5000:
memo (top-down, đệ quy) : 34,8 micro giây
tab (bottom-up, lặp) : 1,24 micro giây (tab nhanh 28 lần)
Tabulation nhanh hơn 28 lần dù cùng độ phức tạp, vì memoization vẫn trả giá cho những thứ bài đệ quy đã đo: chi phí gọi hàm ở mỗi bài con, và một nhánh kiểm tra "đã tính chưa?" mỗi lần. Vòng lặp của tabulation không có gì trong số đó — nó chỉ đọc hai ô rồi ghi một ô, lặp lại, cực gọn. Và tabulation còn một lợi thế quan trọng hơn tốc độ: vì không đệ quy, nó không có trần ngăn xếp. Memoization top-down cho fib(1000000) sẽ đệ quy một triệu tầng và tràn ngăn xếp đúng như bài trước đo; tabulation chỉ là một vòng lặp, chạy sâu bao nhiêu cũng được.
Còn một tinh chỉnh nữa: với Fibonacci, để tính fib(i) ta chỉ cần hai giá trị ngay trước nó, không cần cả bảng. Giữ đúng hai biến (kỹ thuật rolling) cho ra O(1) bộ nhớ thay vì O(n), và đo được nhanh ngang tabulation (1,16 micro giây). Nhiều bài DP thật cho phép thu gọn bộ nhớ kiểu này khi công thức truy hồi chỉ nhìn lại vài dòng.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: cảnh giác với đệ quy tự nhiên khi bài toán có bài con chồng lấn. Một hàm đệ quy khớp đẹp với định nghĩa toán học có thể là một quả bom mũ nếu nó tính lại các bài con — Fibonacci chỉ là ví dụ rõ nhất, nhưng cùng cái bẫy nằm trong đếm số cách, khoảng cách chỉnh sửa chuỗi, chia balô, và vô số bài khác. Dấu hiệu nhận biết: hàm đệ quy gọi chính nó nhiều hơn một lần với các tham số có thể trùng nhau. Thấy dấu hiệu đó, hãy nghĩ tới việc nhớ kết quả.
Hệ quả thứ hai: khi đã quyết định "nhớ để khỏi tính lại", ưu tiên tabulation (bottom-up) nếu độ sâu có thể lớn. Memoization dễ viết hơn (chỉ thêm một bảng vào hàm đệ quy sẵn có), nhưng nó thừa hưởng cả chi phí gọi hàm lẫn trần ngăn xếp của đệ quy. Tabulation cần bạn nghĩ ra thứ tự điền bảng, nhưng đổi lại nhanh hơn (đo được 28 lần với Fibonacci) và miễn nhiễm tràn ngăn xếp. Với n nhỏ và có kiểm soát, memo tiện; với n lớn, tab an toàn hơn.
Hệ quả thứ ba là con số mang theo: đệ quy naive cho bài toán con chồng lấn nổ theo mũ — fib(43) gọi 1,4 tỉ lần trong 447ms — và quy hoạch động chỉ là "nhớ để khỏi tính lại", đưa nó về 85 lời gọi dưới 1 micro giây (mũ thành tuyến tính); giữa hai cách, tabulation bottom-up nhanh hơn memoization top-down 28 lần và không có trần ngăn xếp, còn rolling cho O(1) bộ nhớ. Kỹ thuật nghe cao siêu nhất trong bài này thực ra là ý tưởng tầm thường nhất — và đó là điều đáng nhớ: rất nhiều "thuật toán khó" chỉ là một quan sát đơn giản được đặt tên trang trọng.
Thử ba mươi giây
Viết hàm Fibonacci đệ quy đúng như định nghĩa, rồi gọi fib(45) và bấm giờ — bạn sẽ chờ vài giây cho một số mà máy tính bỏ túi trả về tức thì. Đó là hàm mũ đang hiện hình. Giờ thêm đúng một mảng nhớ (hoặc đổi thành vòng lặp điền từ dưới lên) và gọi lại: tức thì, kể cả fib(90). Cảm giác chờ-vài-giây rồi tức-thì đó là toàn bộ trực giác về quy hoạch động, gói trong ba mươi giây. Và mỗi khi gặp một hàm đệ quy gọi chính nó nhiều lần, hãy tự hỏi: nó có đang tính lại cùng một thứ không? Nếu có, bạn vừa tìm thấy chỗ để nhớ — và biến một quả bom mũ thành một vòng lặp tuyến tính.
