Lời giải 'thanh lịch' O(n log n) thua một vòng for tầm thường 20 lần

Có một sự cám dỗ trong nghề: lời giải càng trông "cao cấp" thì ta càng tin nó tốt. Giống như một người thợ mới sắm bộ đồ nghề điện xịn thì muốn dùng nó cho cả việc đóng một cái đinh — trong khi cây búa cũ vẫn nhanh hơn. Chia để trị (divide and conquer) đúng là bộ đồ nghề xịn ấy: merge sort, quicksort, tìm nhị phân — nhiều bài đầu sê-ri này — đều là nó. Ý tưởng đẹp và tổng quát tới mức khi gặp bài khó, phản xạ tự nhiên là "chia đôi rồi ghép lại". Bài này lấy một bài toán mà chia để trị cho lời giải rất thanh lịch, đo nó, rồi phát hiện một điều khiêm nhường: đẹp và tổng quát không có nghĩa là tối ưu, và đôi khi một vòng lặp tầm thường đánh bại cả một kiến trúc đệ quy tinh xảo.

Khuôn chia để trị, và bước gộp quyết định tất cả

Chia để trị có ba nhịp: chia bài toán thành các bài con nhỏ hơn, trị (giải) từng bài con bằng đệ quy, rồi gộp (combine) các lời giải con thành lời giải chung. Độ phức tạp của cả thuật toán được tóm trong định lý thợ (master theorem): T(n) = a·T(n/b) + chi phí gộp — với a bài con mỗi lần chia, kích thước n/b, cộng công sức để gộp. Điểm mấu chốt ít người để ý: chính bước gộp thường quyết định độ phức tạp cuối cùng. Nếu gộp rẻ, thuật toán nhanh; nếu gộp đắt, mọi công chia nhỏ có thể đổ sông đổ biển.

Bài toán để đo: mảng con tổng lớn nhất — cho một dãy số (có âm có dương), tìm đoạn liên tiếp có tổng lớn nhất. Lời giải chia để trị rất đẹp: đoạn tốt nhất hoặc nằm gọn trong nửa trái, hoặc gọn trong nửa phải, hoặc bắc qua giữa. Hai trường hợp đầu giải bằng đệ quy trên hai nửa; trường hợp bắc qua giữa là bước gộp — quét từ điểm giữa ra hai phía tìm tổng lớn nhất chạm giữa, tốn O(n). Ghép lại theo định lý thợ: T(n) = 2T(n/2) + O(n) cho ra O(n log n). Nghe chặt chẽ, thông minh, và tối ưu cho một bài trông hóc búa. Tôi đo, và mang theo cả một lời giải ngây thơ lẫn một lời giải khác để so.

Cả ba cùng đáp số, nhưng lệch nhau 20 lần

Tôi cài ba cách: brute O(n²) thử mọi đoạn; chia để trị O(n log n); và Kadane O(n) — một vòng quét tuyến tính duy nhất, giữ "tổng tốt nhất kết thúc tại đây" và cập nhật khi đi. Trước hết kiểm cả ba cho cùng đáp số (chúng khớp), rồi bấm giờ.

Brute O(n²) đúng như dự đoán, thời gian gấp bốn mỗi khi n gấp đôi (6 → 24 → 99 → 389 mili giây ở n = 5.000 đến 40.000), và ở n vài trăm nghìn thì vô dụng. Câu chuyện thật nằm ở hai lời giải "nhanh":

n            chia để trị (O(n log n))   Kadane (O(n))
1 triệu          9,6 ms                    0,5 ms
10 triệu       111,9 ms                    5,3 ms   (chia để trị chậm hơn ~21 lần)

Chia để trị, lời giải thanh lịch O(n log n) mà sách giáo khoa tự hào, chậm hơn Kadane khoảng 20 lần — và khoảng cách còn nới rộng khi n lớn hơn (đúng cái thừa số log n). Đây là chỗ tôi phải xét lại kỳ vọng của mình.

Đẹp và tổng quát không phải tối ưu

Tôi vào bài với ngầm định rằng chia để trị, vì là kỹ thuật "cao cấp" và cho O(n log n) trên một bài trông khó, hẳn là lời giải tốt. Nó cảm giác tối ưu — có cấu trúc đệ quy đẹp, có bước gộp thông minh, có phân tích định lý thợ gọn gàng. Nhưng đồng hồ chỉ ra một lời giải khiêm tốn hơn nhiều thắng đậm: Kadane chỉ là một vòng for, đi qua mảng đúng một lần, ở mỗi phần tử quyết định "nối vào đoạn đang có hay bắt đầu đoạn mới", giữ lại tổng lớn nhất từng thấy. Không đệ quy, không bước gộp, không chia nhỏ — O(n) thuần, và nhanh hơn 20 lần.

Điều rút ra: chia để trị là một công cụ mạnh và tổng quát, nhưng "mạnh và tổng quát" không đồng nghĩa với "tối ưu cho bài này". Sự tổng quát của nó có giá — chi phí đệ quy, chi phí bước gộp lặp lại ở mỗi tầng — và với một số bài, tồn tại một lời giải tuyến tính khéo léo mà cấu trúc đệ quy không bao giờ đấu lại. Nhìn qua lăng kính định lý thợ thì rõ: O(n log n) của chia để trị đến từ bước gộp O(n) nhân với log n tầng; Kadane xóa bỏ cả cái log n ấy bằng cách không chia gì cả, chỉ tích lũy thông tin trong một lần đi. Tôi suýt viết cả bài ca ngợi lời giải chia để trị "thông minh" mà bỏ qua rằng cái đơn giản hơn vừa nhanh hơn vừa dễ hiểu hơn. Đẹp trên giấy không phải là tiêu chí; đồng hồ mới là.

Về đến code hằng ngày

Điều đầu tiên: đừng dừng ở lời giải đẹp đầu tiên; hỏi có cách đơn giản hơn không. Chia để trị hấp dẫn vì nó cho cảm giác "đã giải xong bài khó một cách thanh lịch", và cảm giác đó dễ khiến ta ngừng tìm. Nhưng nhiều bài có một lời giải tuyến tính một-lượt-quét ẩn dưới, thường dựa trên một quan sát về cách thông tin tích lũy dọc mảng (như Kadane). Trước khi hài lòng với O(n log n), hãy hỏi: mình có thực sự cần chia nhỏ không, hay có thể tính lũy tiến trong một lần đi?

Điều thứ hai: khi buộc phải dùng chia để trị, hãy nhìn kỹ bước gộp — đó là nơi chi phí sống. Định lý thợ cho thấy toàn bộ độ phức tạp thường do bước gộp định đoạt. Nếu bạn gộp O(n) mỗi tầng, bạn được O(n log n); nếu tìm được cách gộp rẻ hơn (hoặc chia thành ít bài con hơn), bạn được nhanh hơn. Tối ưu một thuật toán chia để trị gần như luôn là tối ưu bước gộp, không phải bước chia.

Và chia để trị vẫn là vua ở đúng sân của nó — chỉ là bạn nên biết sân đó ở đâu. Nó thắng lớn khi bài toán chia được song song: Fork/Join của Java (RecursiveTask) và parallelStream chia mảng ra nhiều lõi đúng theo khuôn này; MapReduce/Spark là chia-để-trị ở quy mô cụm máy (chia dữ liệu ra nhiều máy — map, rồi gộp — reduce); và bộ tối ưu truy vấn của cơ sở dữ liệu dùng merge-sort ngoài (external merge sort, chính là chia để trị) để sắp dữ liệu lớn hơn RAM. Ở những chỗ đó cái "log n tầng" là đường để rải việc ra nhiều bộ xử lý, nên nó đáng. Nhưng cho một bài tuần tự trên một lõi mà có lời giải một-lượt-quét, vòng for thắng. Mẫu số chung: một kỹ thuật danh giá không phải câu trả lời đúng cho mọi bài — đôi khi câu trả lời đúng là một vòng lặp mà bạn suýt bỏ qua vì nó trông quá tầm thường.

Muốn tự nhắc mình thì lần tới khi giải xong một bài bằng chia để trị và thấy hài lòng với O(n log n), dừng một nhịp và hỏi: mình có thật sự cần chia đôi không? Thử hình dung đi qua dữ liệu đúng một lần, mang theo vài giá trị tích lũy (tổng đang chạy, cực trị đã thấy, trạng thái gọn) — liệu có đủ để trả lời không? Rất nhiều bài "trông cần đệ quy" hóa ra có một lời giải một-lượt như thế, và nó thường nhanh hơn nhờ bỏ được thừa số log n và thân thiện cache hơn. Nếu tìm được, hãy đo cả hai; nếu vòng quét đơn giản thắng — như Kadane thắng ở đây — bạn vừa học lại rằng lời giải đẹp nhất trên bảng không phải lúc nào cũng là lời giải tốt nhất trên máy.