Thuật toán sắp xếp sách mới đạt hiệu năng gần như hoàn hảo
(quantamagazine.org)- Bài toán sắp xếp thư viện không chỉ là chuyện sắp xếp giá sách mà còn chi phối chi phí lưu trữ tuần tự trên ổ cứng và cơ sở dữ liệu; nghiên cứu mới đã hạ thời gian chèn trung bình xuống rất gần giới hạn lý thuyết
- Thuật toán năm 1981 bảo đảm thời gian chèn trung bình ((log n)^2) theo cách tất định và mượt (smooth), nhưng hơn 40 năm qua không có cận trên nào thấp hơn xuất hiện
- Các nghiên cứu cận dưới sau đó cho thấy mức tốt nhất của thuật toán tổng quát là (log n), còn giới hạn của thuật toán mượt và thuật toán tất định là ((log n)^2), khiến cách tiếp cận ngẫu nhiên, không mượt trở nên cần thiết
- Năm 2022, Bender, Kuszmaul và cộng sự hạ cận trên xuống ((log n)^{1.5}) bằng một thuật toán ngẫu nhiên độc lập lịch sử (history independent); nghiên cứu mới nhất tiếp tục đạt ((log n)(log log n)^3) bằng cách tận dụng thêm thông tin quá khứ ở mức hạn chế
- Khoảng cách còn lại nằm ở hạng tử (log log n), và bước tiến này có thể giúp tăng tốc các ứng dụng như lưu trữ và xử lý đồ thị động dựa trên gán nhãn danh sách
Bài toán sắp xếp thư viện đặt ra điều gì
- Bài toán sắp xếp thư viện là bài toán tối thiểu hóa thời gian di chuyển cần thiết khi chèn một mục mới mà vẫn duy trì thứ tự đã sắp xếp
- Nếu dồn sách về một phía, bạn sẽ phải dời rất nhiều sách khi cần chèn một cuốn mới vào giữa
- Khi thêm sách của Isabel Allende, có thể phải dời cả dãy sách
- Sau đó nếu thêm sách của Douglas Adams, công việc tương tự có thể lặp lại
- Nếu phân bố khoảng trống hợp lý trên toàn bộ giá sách, chi phí chèn có thể giảm đi, nhưng mấu chốt là phải để trống ở đâu và bao nhiêu
- Ở dạng hình thức hơn, đây được gọi là bài toán gán nhãn danh sách (list labeling), được đưa ra trong bài báo năm 1981
- Phạm vi ứng dụng vượt xa giá sách, sang cả việc bố trí tệp và mục trong ổ cứng và cơ sở dữ liệu
- Số lượng mục có thể lên tới hàng chục tỷ
- Cách bố trí kém hiệu quả dẫn đến thời gian chờ dài và chi phí tính toán lớn
Hiệu năng nhìn từ cận trên và cận dưới
- Hiệu năng của một cách bố trí có thứ tự thường được đánh giá bằng thời gian cần để chèn một mục mới
- Khi có (n) mục, nếu phải dời toàn bộ sách thì thời gian chèn tỉ lệ với (n)
- Có thể xem đây là cận trên cho thời gian thêm một mục mới
- Bài báo năm 1981 đặt câu hỏi liệu có thể giảm mạnh thời gian chèn trung bình xuống thấp hơn nhiều so với (n) hay không, và đưa ra thuật toán bảo đảm ((log n)^2)
- Đây là thuật toán tất định, không dựa vào tính ngẫu nhiên
- Nó có tính chất mượt (smooth), nghĩa là các mục phải được phân bố đều trong khoảng đang có chèn hoặc xóa xảy ra
- Các nhà nghiên cứu cố thu hẹp khoảng cách giữa cận trên và cận dưới; khi hai giá trị này trùng nhau, thuật toán được xem là tối ưu
Những ràng buộc do các kết quả cận dưới trước đó tạo ra
- Nghiên cứu năm 2004 cho thấy trong phiên bản tổng quát nhất của bài toán sắp xếp thư viện, không thuật toán nào có thể tốt hơn cận dưới cuối cùng là (log n)
- Năm 1990, người ta xác nhận cận dưới của thuật toán mượt là ((log n)^2)
- Năm 2012, có thêm kết quả cho thấy thuật toán tất định không dùng ngẫu nhiên cũng có cùng cận dưới ((log n)^2)
- Những kết quả này có nghĩa là chỉ dùng thuật toán mượt hoặc tất định thì rất khó cải thiện cận trên ((log n)^2) của năm 1981
- Michael Bender kết luận rằng để có kết quả tốt hơn cần một thuật toán ngẫu nhiên và không mượt
- Cách làm không mượt trông có vẻ rủi ro theo trực giác vì không phân bố các mục một cách đồng đều
- Cũng không rõ vì sao lựa chọn ngẫu nhiên lại giúp ích
Năm 2022: hạ cận trên bằng độc lập lịch sử
- Năm 2022, Bender, William Kuszmaul và 4 đồng tác giả khác đã xây dựng một thuật toán độc lập lịch sử, không mượt và ngẫu nhiên
- Thuật toán độc lập lịch sử không để lộ trạng thái quá khứ của giá sách
- Kuszmaul nêu ví dụ rằng khi lấy một cuốn sách từng có trên giá ra, người khác sẽ không thể biết điều đó đã xảy ra
- Tính chất này có thể hữu ích vì lý do riêng tư hoặc bảo mật
- Thuật toán này lần đầu tiên hạ cận trên năm 1981, giảm thời gian chèn trung bình xuống còn ((log n)^{1.5})
- Kuszmaul xem đây là điều bất ngờ, vì một công cụ thường dùng cho quyền riêng tư lại có thể làm thuật toán nhanh hơn
- Helen Xu của Georgia Institute of Technology đánh giá rằng ý tưởng dùng độc lập lịch sử vì lý do ngoài bảo mật có thể ảnh hưởng tới các bài toán khác
Nghiên cứu mới nhất: kết hợp thông tin quá khứ hạn chế và tính ngẫu nhiên
- Trong bài báo mới nhất, Bender, Kuszmaul và cộng sự tiếp tục hạ cận trên xuống ((log n)(log log n)^3)
- Giá trị này tương đương ((log n)^{1.000…1}), tức rất gần với cận dưới cuối cùng là (log n)
- Cách tiếp cận mới vẫn không mượt và ngẫu nhiên, nhưng lần này sử dụng thêm phụ thuộc lịch sử (history dependence) ở mức hạn chế
- Thuật toán quan sát một phần xu hướng trong quá khứ để chuẩn bị cho các lần chèn trong tương lai
- Nếu có nhiều sách của các tác giả có họ bắt đầu bằng N như Nabokov, Neruda và Ng được thêm vào, nó sẽ chừa thêm không gian ở khu vực chữ N
- Tuy vậy, nếu dành quá nhiều chỗ thì sẽ phát sinh vấn đề khi có nhiều sách của tác giả bắt đầu bằng A được thêm vào
- Bender giải thích rằng họ đã làm cho cách tiếp cận này hữu ích bằng cách ngẫu nhiên hóa một cách chiến lược lượng quá khứ mà thuật toán được phép nhìn vào khi ra quyết định
- Seth Pettie nhận xét rằng nghiên cứu lần này sử dụng tính ngẫu nhiên theo cách hoàn toàn khác với bài báo năm 2022
Khoảng cách còn lại và khả năng ứng dụng
- Khoảng cách còn lại là một hạng tử nhỏ (log log n)
- Bender nói rằng hiện chưa rõ nên tiếp tục hạ cận trên hay nâng cận dưới
- Pettie cho rằng khi khoảng cách đã hẹp đến mức này, và một phía có vẻ tự nhiên còn phía kia có vẻ kém tự nhiên, thì thông thường phía tự nhiên hơn sẽ là đáp án đúng
- Ông đánh giá khả năng cao hơn là các cải tiến sắp tới sẽ hạ cận trên xuống (log n)
- Tuy nhiên, ông cũng nói thêm rằng “thế giới đầy những bất ngờ kỳ lạ”
- Brian Wheatman của University of Chicago nhận định rằng các bài báo này là một cải tiến đáng kể về mặt lý thuyết, đồng thời cũng có tiềm năng cải thiện lớn ở khía cạnh ứng dụng
- Helen Xu cho biết gần đây bà quan tâm đến việc lưu trữ và xử lý đồ thị động bằng các cấu trúc dữ liệu dựa trên gán nhãn danh sách, và bước tiến lần này gần như chắc chắn sẽ giúp chúng chạy nhanh hơn
1 bình luận
Ý kiến trên Hacker News
Tôi cũng ngạc nhiên trước việc “một công cụ từng được dùng để bảo vệ quyền riêng tư lại có thể mang đến lợi ích khác”
Nghĩ kỹ thì phần lớn hiệu năng không hẳn là chuyện “thực thi nhiều lệnh hơn mỗi giờ” theo nghĩa đen, mà giống với chọn cách để làm ít việc hơn
Ở đây, thuộc tính bảo mật tính độc lập với lịch sử cũng có nghĩa là “không cần theo dõi lịch sử, và theo nghĩa đen cũng không thể làm vậy”, nên dùng mật mã học như một ràng buộc để ngăn việc không cần thiết có vẻ là một cách tiếp cận hiệu năng thú vị
Theo tôi hiểu, đây là mô hình cho phép dùng thời gian tính toán vô hạn
Ví dụ, nếu biết danh sách đã được sắp xếp thì có thể dùng tìm kiếm nhị phân. Nhưng có lẽ việc chọn bỏ qua bao nhiêu thông tin cũng có thể là điểm then chốt. Chỉ là những trường hợp như vậy ít gặp hơn, và tôi chưa nghĩ ra ngay ví dụ đơn giản nào
Không biết có phải chỉ mình tôi cố tìm các bài báo cốt lõi mà bài viết mô tả, tức bài báo nêu bài toán gốc và bài báo về thuật toán gần tối ưu [1], [2] không
Cả hai dường như được liên kết khá sâu trong bài, nhưng nếu Quanta bắt buộc gom toàn bộ tài liệu tham khảo ở cuối bài thì sẽ rất hữu ích cho độc giả
[1] Nearly Optimal List Labeling:
https://arxiv.org/abs/2405.00807
[2] A sparse table implementation of priority queues:
https://link.springer.com/chapter/10.1007/3-540-10843-2_34
Trong câu “This problem was introduced in a 1981 paper”, cụm “1981 paper” dẫn tới https://link.springer.com/chapter/10.1007/3-540-10843-2_34, còn ở đoạn tiếp theo, câu “Last year, in a study that was presented at the Foundations of Computer Science conference in Chicago, a team of seven researchers”, cụm “a study” dẫn tới https://arxiv.org/abs/2405.00807
Cả hai đều nằm ở đoạn thứ ba và thứ tư của phần mở đầu, trước khi đi vào chi tiết, lịch sử và bối cảnh. Nếu như vậy mà gọi là “khá sâu trong bài”, thì tiêu chuẩn về sâu trong bài hẳn phải khác nhau khá nhiều
Tuần trước tôi vừa xem đúng vấn đề này. Tôi muốn đặt các mục trong bảng cơ sở dữ liệu ở vị trí tùy ý, nhưng nếu có thể thì không muốn đụng tới phần còn lại của danh sách
Chẳng hạn khi người dùng thêm một phần tử mới sau mục số 5, phần tử đó sẽ thành số 6, nhưng các mục vốn nằm sau số 5 thì không bị cập nhật. Thực sự có những thuật toán rất tinh vi để quản lý vấn đề này và giảm thiểu các giới hạn lý thuyết
Tuy nhiên trong phiên bản cụ thể này, dùng chỉ mục phân số và thỉnh thoảng chịu chi phí sắp xếp lại danh sách có vẻ là cách đơn giản nhất
Về cơ bản, nó hoạt động tốt nếu không gian nhãn lớn so với số lượng mục. Nếu không thì cần phương pháp tinh vi hơn. Ví dụ, nếu nhãn chỉ có 4 byte mà có 1 tỷ mục thì sẽ thành vấn đề
Theo tôi nhớ, lời giải thực tế là để chừa khoảng trống giữa các phần tử. Ví dụ thay vì 0, 1, 2 thì dùng 0, 100, 200, rồi đánh lại chỉ mục khi cần. Có vẻ hoạt động đủ tốt
Thứ tôi nghĩ ra là fractional indexing như đã nói, nhưng vì xử lý số thập phân phiền phức nên có thể biểu diễn bằng vector, rồi biểu diễn nó dưới dạng chuỗi số được sắp xếp theo thứ tự từ điển
Phần tử chèn giữa 1 và 2 sẽ có chỉ mục 11. Bất kỳ giá trị nào từ 11 đến 19 đều được. Giữa 1 và 11 thì là 101, giữa 11 và 2 thì là 12, kiểu như vậy. Nhưng các chỉ mục này không phải là số, mà là chuỗi được so sánh theo thứ tự từ điển
Chắc chắn cũng có nhược điểm. Ví dụ, để sắp xếp các chỉ mục kiểu này sẽ tốn nhiều bộ nhớ hơn nhiều, vì chuỗi lớn hơn số rất nhiều. Cũng có cảm giác cách này quá khôn ngoan để không có nhược điểm bất ngờ nào
Trong thực tế, giới hạn đó rất hạn chế, nhưng nếu không chỉ gán nhãn thứ tự cho collection mà còn dùng trực tiếp nhãn này làm chỉ mục mảng để lưu phần tử, thì sự khác biệt đó thực sự trở thành vấn đề. Cách đó mô hình hóa bài toán sắp xếp thư viện theo nghĩa đen hơn
Tôi nhớ vài năm trước từng trình bày cho sinh viên một bài toán dựa trên thuật toán Library Sort
Tựa bài báo gốc đến giờ vẫn còn rất rõ: “Insertion Sort is O(n log n)”
Tiêu đề nghe khá kiểu câu view
Tôi thắc mắc liệu thuật toán này có lý do gì để thực sự nhanh hơn cách đang dùng trong thực tế hay không
Nơi tôi chủ yếu gặp vấn đề này là mảng của các nút B-tree, và ở đó tôi nghi ngờ liệu nó có nhanh hơn việc chỉ dùng
memmove()không; còn nếu là mảng thật sự lớn thì có lẽ dùng B-tree sẽ dễ hơnNếu vậy thì thuật toán này cũng thuộc loại nhanh hơn về mặt tiệm cận nhưng nghịch lý là lại chậm hơn các thuật toán dùng trong thực tế. Ví dụ là các thuật toán nhân ma trận nhanh chậm hơn thuật toán O(n^3) kiểu giáo khoa được triển khai tốt (GEMM)
Ví dụ đầu tiên trên trang có một trích dẫn giải thích khá rõ tính hữu dụng của chúng
“Là một ví dụ về galactic algorithm, phương pháp nhanh nhất đã biết để nhân hai số dựa trên biến đổi Fourier 1729 chiều. Nó chỉ cần O(n log n) phép toán bit, nhưng do hằng số ẩn trong ký hiệu big-O quá lớn nên thực tế không được dùng. Dù vậy, nó vẫn cho thấy vì sao những thuật toán như vậy có thể hữu ích. Các tác giả nói rằng họ ‘hy vọng những cải tiến tiếp theo sẽ khiến nó trở nên thực dụng chỉ với các số có hàng tỷ hoặc hàng nghìn tỷ chữ số’”
Câu
hạ cận trên xuống (log n) × (log log n)^3 — tương ứng với (log n)^(1.000...1)là đúngMột trong những điểm thú vị khi nhìn độ phức tạp big-O theo họ chuẩn đa thức là log cho ra các giá trị vô cùng bé. Đây là một đòn đáp trả với những người nói “vô cùng bé không thực sự tồn tại”
Tôi đã rất ngạc nhiên khi biết British Library quản lý hàng triệu cuốn sách và vô số sách mới mỗi tuần như thế nào
Cuốn sách đầu tiên được nhập vào đầu năm nay được đặt ở vị trí 2025.0000001 trên kệ, cuốn tiếp theo được đặt ngay cạnh ở 2025.0000002. Phần còn lại do catalog điện tử xử lý
Không cần xáo trộn lại sách, nhưng đây không phải là một giải pháp phù hợp với cách đi quanh giá sách để tìm sách
Thậm chí họ còn cố ý tránh sự tương đồng để người lấy hàng không nhặt nhầm một món trông giống nhưng không đúng
Ở nhà tôi cũng thường quên mình đã để những món thỉnh thoảng dùng ở đâu. Chẳng hạn như lưỡi dao thay thế cho dao x-acto nằm trong hộp nào, ở tủ âm tường nào. Vì cố gom các món giống nhau lại với nhau nên có hộp thì đầy tràn, hộp khác lại chỉ vơi một nửa
Đôi khi tôi tưởng tượng nếu theo dõi toàn bộ đồ đạc bằng bảng tính, ghi món nào nằm trong hộp nào, thì sẽ không làm mất đồ và cũng dùng không gian lưu trữ hiệu quả tối đa. Nhưng rõ ràng là khi cất một món mới tôi sẽ quên cập nhật, và cách đó có cảm giác kỳ quặc, phi nhân tính, giống việc robot làm hơn là con người
Hình động ở đầu bài khiến tôi muốn làm một trình bảo vệ màn hình
Tôi đang cố nắm ràng buộc cốt lõi. Định nghĩa bài toán có giả định một mảng độ dài cố định được cấp phát trước không?
insert(X),delete(X),label(X)labellấy nhãn của phần tử X đã được chèn trước đó và chưa bị xóa. Nhãn là một số từ 0 đến n-1, trong đó n là số phần tử hiện đang được lưu trữ