Giới thiệu
- Một thuật toán mới đưa ra cách giải quyết bài toán sắp xếp trong thư viện.
- Bài toán này không chỉ áp dụng cho việc sắp xếp sách mà còn có thể áp dụng cho việc bố trí tệp trên ổ cứng và trong cơ sở dữ liệu.
- Cách tiếp cận mới kết hợp nội dung lịch sử của giá sách với tính ngẫu nhiên để tạo ra kết quả gần với mức lý tưởng về mặt lý thuyết.
Thu hẹp giới hạn
- Cách phổ biến để đo độ tốt của một giá sách được sắp xếp là xem thời gian cần để chèn từng mục riêng lẻ.
- Một bài báo năm 1981 đã đặt ra câu hỏi liệu có thể thiết kế một thuật toán có thời gian chèn trung bình nhỏ hơn rất nhiều so với n hay không.
- Nghiên cứu năm 2004 phát hiện rằng cận dưới tối ưu của bài toán sắp xếp thư viện là log n.
- Nó cho thấy các thuật toán trơn tru hoặc xác định không thể đạt thời gian chèn trung bình tốt hơn (log n)².
Lịch sử bí mật
- Năm 2022, Bender và các cộng sự đã thử một thuật toán ngẫu nhiên và không trơn tru, giảm thời gian chèn trung bình xuống còn (log n)¹.⁵.
- Thuật toán này không phụ thuộc vào lịch sử ghi chép trước đó của giá sách, điều này có thể hữu ích vì lý do bảo mật.
Thu hẹp khoảng cách
- Bender và Kuszmaul đã hạ cận trên xuống (log n) × (log log n)³, tiến rất gần tới cận dưới lý thuyết.
- Thuật toán này sử dụng mức độ phụ thuộc lịch sử có giới hạn để lập kế hoạch cho các sự kiện trong tương lai.
- Kết quả này dựa trên các nghiên cứu trước đó và sử dụng tính ngẫu nhiên theo một cách hoàn toàn khác.
Kết luận
- Nghiên cứu này thể hiện một cải thiện quan trọng về mặt lý thuyết, đồng thời cũng có tiềm năng cải thiện lớn về mặt ứng dụng.
- Tuy vậy, hạng tử log log n vẫn đang cản trở một lời giải hoàn chỉnh; giải pháp có thể là hạ cận trên xuống thấp hơn hoặc nâng cận dưới lên cao hơn.
1 bình luận
Ý kiến Hacker News
Thật thú vị khi các kỹ thuật mật mã có thể được dùng để cải thiện hiệu năng. Hiệu năng không chỉ là thực thi nhiều lệnh hơn, mà là chọn cách làm ít việc hơn. Thuộc tính bảo mật gọi là "tính độc lập với lịch sử" có nghĩa là không phải thực hiện công việc truy vết quá khứ
Rất khó tìm được các bài báo chính được nhắc đến trong bài viết. Sẽ hữu ích hơn cho độc giả nếu Quanta liệt kê toàn bộ tài liệu tham khảo ở cuối bài
Có những thuật toán phức tạp để giải quyết bài toán đặt các mục vào vị trí tùy ý trong bảng cơ sở dữ liệu. Tuy nhiên, một cách giải quyết đơn giản cho vấn đề này là dùng giá trị phân số và thỉnh thoảng sắp xếp lại danh sách
Tôi nhớ đã từng đưa bài toán này cho sinh viên dựa trên thuật toán 'Library Sort'. Tên của bài báo gốc là 'Insertion Sort is O(n log n)'
Tôi tự hỏi liệu có lý do nào để nó thực sự nhanh hơn các thuật toán đang được dùng hiện nay không. Trong mảng của các nút B-tree, dùng
memmove()có thể nhanh hơn. Với các mảng lớn, dùng cây B sẽ dễ hơnTôi thắc mắc liệu phát biểu bài toán có giả định một mảng được cấp phát trước với độ dài cố định hay không
Tôi ngạc nhiên về cách Thư viện Anh quản lý sách. Khi sách đến nơi, danh mục điện tử xử lý phần còn lại nên không cần phải sắp xếp lại sách
Tôi muốn biến hoạt ảnh ở đầu bài viết thành trình bảo vệ màn hình
Đây là các liên kết gọn gàng dành cho người dùng di động
Đúng là cận trên được hạ xuống còn (log n) nhân với (log log n)^3. Thật thú vị khi log cung cấp các giá trị tiệm cận rất nhỏ trong độ phức tạp big-O khi dùng lớp tham chiếu đa thức