Nghiên cứu của một sinh viên đại học chứng minh việc cải thiện tốc độ tìm kiếm trong bảng băm

Giới thiệu

• Vào mùa thu năm 2021, Andrew Krapivin, một sinh viên đại học tại Rutgers University, đã bắt gặp một bài báo có thể thay đổi cuộc đời mình.
• Bài báo này nói về những “con trỏ nhỏ” dùng để trỏ tới thông tin trong bộ nhớ máy tính.
• Krapivin đã nghĩ ra cách làm cho các con trỏ nhỏ hơn để giảm mức tiêu thụ bộ nhớ.

Phát hiện ra một bảng băm mới

• Krapivin đã tiến hành thí nghiệm bằng cách sử dụng bảng băm, một phương pháp phổ biến để lưu trữ dữ liệu.
• Trong quá trình thí nghiệm, Krapivin đã phát minh ra một loại bảng băm mới hoạt động nhanh hơn các loại hiện có.
• Phát hiện này đã dẫn đến kết quả lật đổ một giả thuyết 40 năm tuổi trong khoa học dữ liệu.

Tầm quan trọng của bảng băm

• Bảng băm là một trong những cấu trúc dữ liệu lâu đời nhất trong khoa học máy tính, mang lại hiệu quả trong việc lưu trữ dữ liệu.
• Bảng băm được thiết kế để có thể thực hiện ba chức năng: tìm kiếm, xóa và chèn phần tử.

Giả thuyết của Yao và sự bác bỏ

• Năm 1985, nhà khoa học máy tính Andrew Yao đã đưa ra một giả thuyết về cách tìm phần tử trong trường hợp xấu nhất đối với các bảng băm có những thuộc tính nhất định.
• Bảng băm mới của Krapivin đã bác bỏ giả thuyết của Yao, đồng thời chứng minh rằng thời gian cần thiết cho truy vấn và chèn trong trường hợp xấu nhất tỉ lệ với (log x)².

Phát hiện mới về thời gian truy vấn trung bình

• Krapivin và nhóm của ông đã cho thấy rằng trong các bảng băm không tham lam, thời gian truy vấn trung bình không phụ thuộc vào x.
• Điều này có nghĩa là có thể đạt được thời gian truy vấn trung bình hằng số bất kể mức độ lấp đầy của bảng băm.

Kết luận

• Nghiên cứu này giúp đào sâu hiểu biết về bảng băm và có thể dẫn tới các ứng dụng thực tiễn.
• Sự hiểu biết này về cấu trúc dữ liệu có thể trở thành nền tảng cho những cải tiến thực dụng trong tương lai.

[GN⁺]

Ý kiến Hacker News

• Krapivin đã tạo ra bước đột phá mà không biết đến phỏng đoán của Yao

  • Nhà phát triển của Balatro đã tạo ra một game deck builder đoạt giải thưởng mà không biết đến các deck builder trước đó
  • Cách tốt nhất để tiếp cận một vấn đề có thể là không biết hoặc phớt lờ những nỗ lực tương tự trước đây
  • Thế giới hiện tại kết nối với nhau quá chặt chẽ, nên rất dễ bị mắc kẹt trong khuôn khổ tư duy cũ
  • Internet rất tuyệt, nhưng có xu hướng đồng nhất hóa thế giới tư duy

• Kết quả rất ấn tượng, nhưng có lẽ nên được gọi là một phỏng đoán của khoa học máy tính

• Tò mò không biết có ai biết một kho lưu trữ GitHub có triển khai này không

• Hay đấy, nhưng kiểu viết "tôn vinh người nổi tiếng" của bài này hơi gây khó chịu

  • Tự hỏi liệu có thực sự cần xem nhiều bức ảnh một người trẻ tạo dáng theo nhiều kiểu khác nhau trong bối cảnh đại học hay không
  • Có vẻ như cần một phiên bản La La Land để tô hồng những người sống sót sau thành công trong máy tính nhằm lôi kéo thêm nhiều người tham gia

• Trong bảng băm mới, thời gian cần cho truy vấn và chèn trong trường hợp xấu nhất tỉ lệ với (log x)²

  • Kết quả của nhóm có thể sẽ không dẫn đến ứng dụng ngay lập tức
  • Tôi không hiểu vì sao lại không dẫn đến ứng dụng ngay lập tức
  • Tò mò liệu có phải đây là trường hợp mà phân tích các ca sử dụng thực tế có thể tinh chỉnh triển khai băm tốt hơn một cách tiếp cận thuần toán học hay không

• Đọc bài này giống như đọc lời giải thích về bài toán Monty-Hall

  • Kết luận dường như trái với trực giác, nhưng có thể chứng minh được
  • Việc có thể đạt được thời gian truy vấn trung bình hằng số bất kể mức độ lấp đầy của bảng băm là điều mà ngay cả các tác giả cũng không ngờ tới

• Đây là một bài kiểm tra thú vị gần đây

  • Hãy xem liệu nghiên cứu sâu có thể đưa ra kết quả này mà không sao chép hay không
  • gpt4, Gemini 2, Claude đã không gặp may
  • Khoa học máy tính do con người dẫn dắt vẫn an toàn

• Tò mò không biết có ai có một triển khai đơn giản của 'Tiny pointers' không

  • Trong đầu tôi, code/mã giả luôn đến trước phần chứng minh

• Như phản diện trong <i>Scooby Doo</i> luôn nói:

  • <i>"Và nếu không có lũ trẻ phiền phức đó, tôi đã thành công rồi!"</i>

• Đọc lướt bài báo thì có vẻ khác biệt chính mà họ dùng là thuật toán chèn của bảng băm sẽ dò xa hơn thay vì tham lam lấp ngay ô trống đầu tiên

  • Kết hợp với một thứ tự dò có thể chứng minh được để tìm ô trống hiệu quả ngay cả khi bảng gần như đầy kín
  • Khi bảng băm ít đầy hơn thì việc chèn sẽ chậm hơn, nhưng có thể tránh được kịch bản tệ nhất là không tìm ra ô trống cuối cùng còn lại

• Một kết quả lý thuyết thú vị, nhưng trong thực tế có vẻ "mẹo" hiện nay là cấp phát bảng lớn hơn mức cần thiết vẫn sẽ là lời giải tốt hơn

  • Ví dụ, hashbrown của Rust để trống 1/8 bảng (12.5%), dùng nhiều bộ nhớ hơn một chút nhưng chèn/tra cứu rất nhanh