Nghiên cứu của một sinh viên đại học lật ngược giới hạn tìm kiếm của bảng băm
(quantamagazine.org)- Khi còn là sinh viên đại học tại Rutgers, Andrew Krapivin đã nghĩ ra một bảng băm mới từ bài báo Tiny Pointers, và cho thấy có thể vượt qua giới hạn vốn được xem là cố hữu của hiệu năng tìm kiếm/chèn
- Trong bài báo tháng 1/2025, Krapivin, Martín Farach-Colton và William Kuszmaul đã bác bỏ phỏng đoán 40 năm tuổi của Yao về một nhóm bảng băm cụ thể
- Phỏng đoán trước đây cho rằng với x biểu thị mức độ gần đầy của bảng, thời gian tìm kiếm/chèn trong trường hợp xấu nhất không thể tốt hơn x, nhưng cấu trúc mới đạt thời gian tỷ lệ với (log x)²
- Nhóm nghiên cứu cũng chỉ ra rằng trong nhóm bảng băm phổ biến mà Yao xem xét, (log x)² là cận tối ưu không thể hạ thấp thêm, và với bảng băm không tham lam thì thời gian tìm kiếm trung bình có thể đạt mức hằng số, không phụ thuộc vào x
- Dù chưa dẫn ngay tới ứng dụng thực tế, đây là nền tảng lý thuyết tái xác lập giới hạn hiệu năng của bảng băm, một cấu trúc dữ liệu lâu đời, qua đó mở ra khả năng cải thiện trong thực tế
Một bảng băm mới bắt đầu từ Tiny Pointers
- Andrew Krapivin lần đầu tiếp xúc với bài báo Tiny Pointers vào mùa thu năm 2021 khi còn là sinh viên đại học tại Rutgers University, và hai năm sau, khi đọc kỹ hơn, anh đã nghĩ ra cách tạo ra các con trỏ nhỏ hơn nữa
- Vì cần tổ chức tốt hơn dữ liệu mà các con trỏ đó trỏ tới, bảng băm — một cách lưu trữ dữ liệu rất phổ biến — đã trở thành đối tượng nghiên cứu
- Trong quá trình thử nghiệm, Krapivin đã tạo ra một bảng băm mới không phụ thuộc vào thăm dò đồng đều (uniform probing), và phát hiện rằng thời gian cùng số bước để tìm một phần tử cụ thể ít hơn dự kiến
- Ban đầu Martín Farach-Colton hoài nghi thiết kế này, nhưng William Kuszmaul nhận định rằng cấu trúc của Krapivin không chỉ là một bảng băm thú vị mà còn là kết quả lật đổ một phỏng đoán 40 năm tuổi
Bài toán về giới hạn hiệu năng của bảng băm
- Bảng băm là một cấu trúc dữ liệu dùng để lưu trữ và truy cập dữ liệu, về cơ bản hỗ trợ ba thao tác
- Truy vấn (query) một phần tử
- Xóa một phần tử
- Chèn một phần tử vào ô trống
- Bảng băm đầu tiên có thể truy về đầu thập niên 1950, và từ đó đến nay vẫn là một cấu trúc dữ liệu lâu đời liên tục được nghiên cứu và sử dụng trong khoa học máy tính
- Giới hạn tốc độ của thao tác tìm kiếm hay chèn thường gắn với thời gian cần để tìm một ô trống trong bảng băm
- Mức độ đầy của bảng băm có thể biểu diễn bằng tỷ lệ tổng thể, nhưng khi xử lý các bảng gần như đầy, các nhà nghiên cứu dùng giá trị x
- Nếu x là 100, bảng đầy 99%
- Nếu x là 1.000, bảng đầy 99,9%
- Với một số bảng băm phổ biến, người ta đã biết rằng thời gian kỳ vọng của thao tác chèn tệ nhất — chẳng hạn chèn phần tử vào ô trống cuối cùng còn lại — tỷ lệ với x
Phỏng đoán năm 1985 của Yao và sự bác bỏ
- Trong bài báo năm 1985, Andrew Yao cho rằng trong các bảng băm có những tính chất nhất định, cách tốt nhất để tìm một phần tử riêng lẻ hay một ô trống là thăm dò đồng đều, tức quét ngẫu nhiên qua các vị trí khả dĩ
- Trong trường hợp xấu nhất, tức khi phải tìm ô trống cuối cùng còn lại, ông phỏng đoán rằng không thể làm tốt hơn x, và điều này trong 40 năm qua phần lớn được chấp nhận là đúng
- Không biết tới phỏng đoán của Yao, Krapivin đã tiếp tục nghiên cứu liên quan tới Tiny Pointers và tạo ra một bảng băm mới không dựa vào thăm dò đồng đều
- Bài báo tháng 1/2025 của Krapivin, Farach-Colton và Kuszmaul cho thấy trong bảng băm mới này, thời gian tìm kiếm/chèn trong trường hợp xấu nhất tỷ lệ với (log x)²
- Kết quả này mâu thuẫn trực tiếp với phỏng đoán của Yao, và nhóm nghiên cứu còn chứng minh rằng trong nhóm bảng băm phổ biến mà Yao xét tới, (log x)² chính là cận tối ưu không thể hạ thấp thêm
Kết quả còn đáng kinh ngạc hơn về thời gian tìm kiếm trung bình
- Năm 1985, Yao không chỉ bàn về thời gian tìm kiếm trong trường hợp xấu nhất mà còn xét thời gian trung bình trên toàn bộ các truy vấn có thể có
- Ông chứng minh rằng trong các bảng băm có những tính chất nhất định, đặc biệt là bảng băm tham lam (greedy) — nơi phần tử mới phải được đặt vào vị trí khả dĩ đầu tiên — thời gian trung bình không thể tốt hơn log x
- Farach-Colton, Krapivin và Kuszmaul muốn kiểm tra liệu cùng giới hạn đó có áp dụng cho bảng băm không tham lam hay không, và họ đã cho thấy là không thông qua một phản ví dụ
- Phản ví dụ này, một bảng băm không tham lam, có thời gian tìm kiếm trung bình tốt hơn log x rất nhiều, và trên thực tế hoàn toàn không phụ thuộc vào x
- Việc có thể đạt thời gian tìm kiếm trung bình hằng số bất kể bảng băm đầy tới mức nào là một kết quả ngay cả chính nhóm nghiên cứu cũng không ngờ tới
Cập nhật lý thuyết cho một cấu trúc dữ liệu lâu đời
- Alex Conway đánh giá rằng bảng băm vừa là một trong những cấu trúc dữ liệu lâu đời nhất, vừa vẫn là một trong những cách hiệu quả nhất để lưu trữ dữ liệu
- Guy Blelloch cho rằng kết quả này đẹp ở chỗ nó xử lý và giải quyết một bài toán kinh điển
- Sepehr Assadi nhận xét rằng nhóm nghiên cứu không chỉ bác bỏ phỏng đoán của Yao mà còn tìm ra câu trả lời tốt nhất cho câu hỏi của ông
- Conway cho rằng dù kết quả này không dẫn ngay tới ứng dụng thực tế, việc hiểu rõ hơn các cấu trúc dữ liệu như vậy vẫn rất quan trọng
- Kết quả lần này, bằng cách tái xác lập các giới hạn lý thuyết của bảng băm, tạo nền tảng để sau này có thể dẫn tới những cải thiện về hiệu năng thực tế
1 bình luận
Ý kiến trên Hacker News
Có lẽ Krapivin tạo ra bước đột phá này vì không biết đến phỏng đoán của Yao, và nhà phát triển Balatro cũng làm ra tác phẩm đoạt giải vì không biết rõ các game deck-builder trước đó
Tôi chợt nghĩ rằng 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ờ, phần lớn những nỗ lực tương tự trước đây
Thế giới hiện nay kết nối quá chặt chẽ, nên sự mới mẻ không bị mắc kẹt trong khuôn khổ tư duy của những người đi trước trở nên hiếm thấy; Internet thì tuyệt vời, nhưng thật đáng tiếc là nó cũng làm tư duy trở nên đồng nhất
Thông thường, nếu bỏ qua các ví dụ thành công trong quá khứ, bạn sẽ lại gieo hạt trên mảnh đất vốn đã cằn cỗi
Nếu đọc nghiên cứu trước đó quá sớm, bạn sẽ bị nhốt trong lối tư duy hiện có; còn nếu hoàn toàn không đọc, bạn sẽ bỏ lỡ những điều quan trọng mà tự mình không nghĩ ra được
Ngay cả khi cách tiếp cận của bạn kém hơn mức tiên tiến nhất hiện có, việc so sánh vẫn có thể cho bạn những insight quan trọng về lý do vì sao cách tiếp cận tiên tiến nhất lại tốt hơn
Theo trích dẫn trực tiếp từ nhà phát triển, ảnh hưởng lớn nhất đối với Balatro là Luck be a Landlord; sau khi xem vài video Northernlion chơi, anh ấy thích ý tưởng về một roguelike tấn công điểm số với chủ đề phi fantasy, nên đã biến game bài đang làm lúc đó thành roguelike
Từ thời điểm đó, anh ấy cố ý giữ khoảng cách với thể loại này, muốn tự mắc lỗi và khám phá không gian thiết kế một cách ngây thơ
Dù thường bị đem so với Slay the Spire, khi thiết kế Balatro anh ấy chưa từng chơi hay xem video về game đó, và mãi về sau mới tiếp xúc với nó
https://www.reddit.com/r/Games/comments/1bdtmlg/comment/kup7...
“Nhưng nếu không có sự giúp đỡ của tất cả mọi người thì cháu chắc chắn đã không làm được.” [Milo] phản bác
“Có thể là vậy.” Reason nghiêm trang nói. “Nhưng cháu đã có can đảm để thử, và những gì cháu có thể làm thường phụ thuộc vào điều cháu định làm.”
King Azaz nói. “Vì vậy có một điều rất quan trọng trong cuộc phiêu lưu của cháu mà chúng ta không thể nói cho cháu biết cho đến khi cháu trở về.”
“Cháu nhớ.” Milo háo hức nói. “Giờ hãy nói cho cháu biết đi.”
“Điều đó là bất khả thi.” nhà vua nói, nhìn Mathemagician
“Hoàn toàn bất khả thi.” Mathemagician nói, nhìn nhà vua
“Vậy thì….” con bọ đột nhiên choáng váng nói
“Đúng, chính thế.” cả hai cùng nói. “Nhưng nếu lúc đó chúng ta nói cho cháu biết, có lẽ cháu đã không đi… và như cháu đã biết, rất nhiều việc thực sự là có thể, miễn là ta không biết rằng chúng là bất khả thi.”
— The Phantom Tollbooth (1961)
Vì nhiều chuyện, tôi trượt môn đó và phải học lại, rồi nhận ra một thói quen
Mỗi học kỳ, trong một bài tập ở nửa sau kỳ học, trong bộ khoảng 30 câu, ông ấy sẽ đưa vào một câu thực ra là bài toán mở, rồi một hai ngày trước hạn nộp lại gửi bản sửa và nói “À, tôi nhầm”
Việc đó luôn xảy ra đúng một lần, nên tôi nghĩ chắc không phải ngẫu nhiên
monort [0] đã đưa liên kết video [1], giúp ích rất nhiều
Đây là phần tóm tắt nhanh sau khi xem video một lần; tên của nó là Funnel Hashing
Ý tưởng là chia mảng thành các mảng con nhỏ hơn theo cấp số nhân. Khối đầu tiên là n/m, khối thứ hai là n/(m^2), cứ giảm dần như vậy cho đến một phần tử đơn lẻ. Nếu gọi chúng là A0, A1, v.v. thì |A0| = n/m, |A1| = n/(m^2), và tổng cộng có k bước
Thử chèn vào A0 c lần; nếu thất bại thì thử ở A1 c lần. Nếu vẫn thất bại thì tiếp tục đi xuống theo “phễu” cho đến khi tìm được ô trống
Họ gọi \delta là tỷ lệ ô trống, nhưng tôi không rõ đây là tham số được xác định khi tạo bảng băm hay là giá trị được cập nhật động. Nếu đặt c = log(1/d), k = log(1/d) thì độ phức tạp thời gian trong trường hợp xấu nhất là O(log^2(1/d))
Tôi hiểu rằng cách này né được kết quả của Yao vì nó không tham lam. Kết quả của Yao áp dụng cho chính sách chèn và tìm kiếm tham lam, còn cách trên đi xuống dây chuyền theo phễu nên là không tham lam
Chắc còn nhiều chi tiết phức tạp, nhưng ý tưởng tôi hiểu được là như vậy. Nếu tôi hiểu sai hoàn toàn thì mong được chỉ ra
Nó làm tôi nhớ nhiều đến ý tưởng “Distinct Elements in Streams” của Chakraborty, Vinodchandran, Meel [2]
[0] https://news.ycombinator.com/item?id=43007860
[1] https://www.youtube.com/watch?v=ArQNyOU1hyE
[2] https://arxiv.org/pdf/2301.10191
Funnel Hashing là “tham lam” và phá vỡ phỏng đoán của Yao về các cơ chế băm tham lam
Elastic Hashing là “không tham lam” và cung cấp thời gian khấu hao tốt hơn các thuật toán tham lam
Không rõ bài viết sai hay tôi hiểu sai paper, nhưng tôi tò mò liệu tác giả bài viết có đang chỉ ra một điểm mà họ không biết hay không
Có vẻ liên quan đến “bước cuối đặc biệt để bắt một vài khóa” ở khoảng 14:41 trong video, nhưng nếu bước đó cũng phải có kích thước cố định thì nó có thể bị đầy. Khi đó phải làm thế nào?
[quảng cáo trắng trợn]: nếu quan tâm đến bảng băm thì Dandelion Hashtable [0] cũng đáng xem
Chúng tôi đang dùng nó trong cơ sở dữ liệu thế hệ tiếp theo của mình, đã trình bày tại HPDC'24, và hiện là bảng băm in-memory nhanh nhất theo tiêu chuẩn sử dụng thực tế
Nó cải thiện closed addressing bằng chaining giới hạn theo cache line, xử lý hơn 1 tỷ yêu cầu in-memory mỗi giây trên máy chủ thông thường
[0] https://dandelion-datastore.com/#dlht
Bài trình bày của người phát minh: https://www.youtube.com/watch?v=ArQNyOU1hyE
Nó trông như một trong những mẹo quản lý tài nguyên mà bạn dùng khi bị ràng buộc và thiếu tài nguyên
Chia theo mức ưu tiên là cách tiếp cận phổ biến trong phân bổ tài nguyên, và đây là một biến thể của nó
Tôi tự hỏi trong số những “mẹo dưới chiến hào” khác mà mọi người đã làm ngoài thực địa, có bao nhiêu thứ mà chính người phát minh cũng không biết là quan trọng nhưng lại có thể lật lại một điều được chấp nhận rộng rãi. Kiểu như “khi có nhiều thứ phải giao, tôi đã nghĩ ra một cách thông minh để thường vẽ tuyến đường nhanh nhất…”
Tất nhiên việc nhận ra, hình thức hóa, triển khai nghiên cứu và xuất bản thành paper là công sức lớn. Tôi không có ý hạ thấp công lao đó
Tôi ước paper cứ bao gồm luôn bài thuyết trình video
Tuy nhiên cách tiếp cận này cũng cấp phát thêm bộ nhớ thông qua mảng phụ, nên tôi thấy hơi lạ là nó tốt hơn thế nào so với việc chỉ cấp phát dư để giảm xác suất đụng độ khóa và làm trường hợp xấu nhất bớt tệ hơn
Lướt qua paper [1], khác biệt cốt lõi có vẻ là thuật toán chèn của bảng băm không tham lam lấp ô trống đầu tiên tìm thấy, mà tìm xa hơn nữa
Họ kết hợp điều này với thứ tự probing thông minh và chứng minh rằng có thể tìm ô trống hiệu quả ngay cả khi bảng gần như đầy
Nói cách khác, việc chèn khi bảng chưa đầy lắm sẽ chậm hơn, nhưng tránh được tình huống xấu nhất là phải tìm kiếm mà không biết vài ô trống cuối cùng còn lại ở đâu
[1]: https://arxiv.org/pdf/2501.02305
Đây là một kết quả lý thuyết thú vị, nhưng trong thực tế tôi đoán “mẹo” hiện tại là cấp phát bảng lớn hơn mức cần thiết vẫn sẽ là giải pháp tốt hơn
Ví dụ hashbrown của Rust cố ý để trống 1/8 bảng, tức 12,5%; dùng thêm chút bộ nhớ nhưng khiến chèn và truy vấn rất nhanh với xác suất cao
Cách này làm tăng số vị trí probing trung bình ngay cả khi bảng chưa đầy lắm
Dù vậy, trong chiến lược này vẫn đặt mục vào ô trống đầu tiên nhìn thấy
“Bỏ qua slot” liên quan đến việc nhảy về phía trước trong thứ tự băm
Có ai có bản triển khai đơn giản của ‘Tiny pointers’ không? Đầu tôi thích xem code hoặc mã giả trước hơn là chứng minh
Hay thật. Tôi luôn tự hỏi liệu có cách nào container hóa bảng theo kiểu này không
Bảng thông thường giống như một con tàu hàng rời nhồi mọi thứ vào. Nếu có thể tổ chức tốt hơn như tàu container thì có lẽ sẽ chở được nhiều hơn, hiệu quả hơn nhiều, và cũng dỡ xuống nhanh hơn
Chuyển các hàng của bảng thành thứ gì đó như chuỗi hoặc JSON, rồi áp dụng base16 cho biến đó thì sẽ có chuỗi base16 của dữ liệu đó
Tạo một bảng băm và đặt giá trị khóa cho chuỗi base16 đó, vậy là có một container chứa dữ liệu
Giờ chỉ cần giải mã chuỗi thập lục phân là lấy được dữ liệu base32
Các tính chất lý thuyết của bảng băm lúc nào cũng ấn tượng gần như ma thuật, và kết quả lần này còn mở rộng điều đó hơn nữa
Điều từng khiến tôi thấy lạ là làm sao bảng băm lại có thể tốt hơn nhiều so với cây, thứ trực giác cho thấy dường như là cách lưu dữ liệu hiệu quả nhất
Điều tôi nhận ra là lý thuyết bảng băm xử lý một tập đối tượng có kích thước cố định. Ta tạo hàm băm cho tập cố định này, rồi dùng nó như chỉ số vector để lưu vào một vector đã cấp phát trước. Vì vậy mới có công thức giúp chèn, xóa, tra cứu gần O(1). Trong khi đó các cấu trúc cây khác nhau không giả định một kích thước cụ thể
Vấn đề là phải định trước kích thước, và khi vector gần đầy thì các thao tác như chèn có thể chậm đi
Đọc lướt bài viết thì kết quả lần này có vẻ giải quyết phần bị chậm đó, cho phép chèn nhanh ngay cả với bảng gần đầy
Thú vị và thông minh, nhưng có lẽ không phải là một bước tiến thực dụng lớn. Trong thực tế, thay vì nghĩ cách lấp bảng thật khéo, tôi nghĩ chỉ cần tăng kích thước giả định lên là được
Tôi viết để kiểm tra xem mình hiểu có đúng không, nếu sai thì cứ sửa giúp
Ở lần chèn xảy ra resize, sẽ tốn thời gian lớn hơn nhiều, tuyến tính theo kích thước bảng, nhưng thời gian đó được khấu hao trên tất cả các lần chèn đã thực hiện
Mỗi khi bảng bắt đầu quá đầy, nếu tăng đủ lớn thì tần suất xảy ra sẽ ngày càng giảm, nên trung bình vẫn là thời gian hằng số
Trong thế giới hàm, rất có thể cây vẫn phù hợp hơn
Tôi chưa có thời gian hiểu hết bài báo, nhưng họ tuyên bố cách này giúp chèn nhanh một cách ổn định. Tôi hiểu được đến mức 75% tổng dung lượng, nhưng không biết khi mọi hàng đều đạt 75% thì có chế độ khác không
Họ cũng tuyên bố tra cứu nhanh, nhưng tôi chưa đọc đủ để biết tra cứu hoạt động thế nào hoặc vì sao lại nhanh
Có rất nhiều tình huống mà nếu bảng băm gần đầy vẫn hoạt động tốt thì thật sự tuyệt. Không phải lúc nào trong khi chương trình chạy cũng có thể đổi kích thước, và trong một số môi trường bộ nhớ cực kỳ quan trọng
Dù vậy tôi vẫn muốn xem implementation và tự thử. Tôi không chắc trong trường hợp thông thường nó có “đáng công” không
Hiệu quả cache cũng có khả năng không tốt. Phần lớn bảng băm đều vậy, ngoại trừ trường hợp đọc bằng linear probing trong bảng khá đầy, khi đó có thể lấy liên tiếp từ bộ nhớ ra để kiểm tra
Từ góc độ hiệu năng thì vẫn chưa rõ có đáng không, nhưng đây là một ý tưởng mới thú vị nên tôi muốn hiểu cho trọn vẹn
Tôi không hiểu đoạn vừa nói “trong bảng băm mới này, thời gian cần cho truy vấn và chèn ở trường hợp xấu nhất tỉ lệ với (log x)2, nhanh hơn x rất nhiều”, lại vừa nói “kết quả của nhóm có thể không dẫn tới ứng dụng tức thì”
Vì sao lại không dẫn tới ứng dụng tức thì? Ý là qua phân tích các use case thực tế, ta có thể tinh chỉnh implementation băm tốt hơn so với cách tiếp cận toán học thuần túy à?
Có những trường hợp phải cần dataset lớn phi thực tế mới thấy tăng tốc
Khi đó x sẽ không lớn hơn 4, nên cải thiện O(x) thành O((log x)^2) cũng chẳng có ý nghĩa khi x nhỏ như vậy
Một số ứng dụng đặc thù bị ràng buộc bộ nhớ có thể để x lớn hơn, nhưng cá nhân tôi chưa gặp trường hợp như thế
Mỗi khi cần hệ số tải rất cao, chẳng hạn trên 90%, thì cuckoo hashing là đủ; còn ở mức 70–80% trở xuống, linear probing rất nhanh và đủ tốt
Kết quả mới cũng có cái giá là làm chậm các lần chèn trong “trường hợp tốt”
Tôi không thấy trong bài báo có gì có thể ảnh hưởng đến thực tiễn
Kết quả này có vẻ chỉ quan trọng khi bảng băm gần đầy
Vậy chẳng phải chỉ cần đặt kích thước bảng lớn hơn 10%, hoặc nếu có thể thay đổi kích thước thì resize sớm hơn là xong sao?
Khi khả năng đụng độ băm trở nên quá lớn, nó tự thay đổi kích thước
Khi bảng quá đầy thì chỉ cần cấp phát thêm gấp đôi bộ nhớ hoặc theo một bội số nhất định rồi sao chép các mục cũ sang
Hầu hết bảng thăm dò phi tuyến, ví dụ cuckoo hashing, đều bị thiệt vì thực tế RAM hoàn toàn không “ngẫu nhiên”
Có ai biết GitHub repository có implementation này không?