- Trung vị có thể được tìm dễ dàng bằng cách sắp xếp, nhưng do chi phí sắp xếp, ngay cả bài toán chọn một phần tử đơn lẻ cũng bị giới hạn ở O(n log n)
- quickselect chỉ đệ quy tìm kiếm phía cần thiết, nên có thể tìm phần tử kth hoặc trung vị với thời gian trung bình O(n)
- Pivot ngẫu nhiên hoạt động tốt trong thực tế, nhưng nếu liên tục chọn phải pivot xấu, mỗi lần chỉ loại bỏ được một phần tử và có thể suy giảm đến O(n²)
- median-of-medians chọn lại trung vị từ các trung vị của những nhóm 5 phần tử, giúp loại bỏ ít nhất 30% số phần tử ngay cả trong trường hợp xấu nhất
- Trong triển khai thực tế, chi phí tính pivot có thể lớn, nên introselect, kết hợp quickselect và heapselect như trong thư viện chuẩn C++, có thể là lựa chọn thực dụng hơn
Giới hạn khi tìm trung vị bằng cách sắp xếp
- Cách đơn giản nhất để tính trung vị là sắp xếp danh sách rồi chọn giá trị ở chỉ số giữa
- Với danh sách có độ dài lẻ, trả về phần tử ở giữa; với danh sách có độ dài chẵn, trả về trung bình của hai phần tử ở giữa
- Độ phức tạp thời gian nhanh nhất của sắp xếp dựa trên so sánh là O(n log n), nên thời gian chạy của cách này cũng bị chi phối bởi việc sắp xếp
- Ưu điểm là mã đơn giản, nhưng để chỉ tìm một trung vị thì nó làm nhiều việc hơn cần thiết
quickselect tạo ra O(n) trung bình
- quickselect là thuật toán đệ quy do Tony Hoare tạo ra, có thể tìm không chỉ trung vị mà cả phần tử kth bất kỳ trong danh sách
- Luồng cơ bản là chia danh sách theo pivot, rồi chỉ tiếp tục tìm kiếm phía chứa phần tử kth
- Chọn một pivot từ danh sách
- Chia danh sách thành các phần tử nhỏ hơn hoặc bằng pivot và các phần tử lớn hơn pivot
- Xác định phần tử kth cần tìm nằm ở phía nào rồi chỉ gọi đệ quy trên danh sách con tương ứng
- Khi đi xuống danh sách con bên phải, điều chỉnh giá trị k theo số phần tử bên trái đã bị loại trừ
- Trong danh sách ví dụ
[9,1,0,2,3,4,6,8,7,10,5], vì độ dài là 11 nên ta tìm phần tử nhỏ thứ 6; tùy theo pivot mà thu hẹp phạm vi và cuối cùng trả về 5
quickselect_median dùng quickselect để tìm một chỉ số giữa nếu độ dài danh sách là lẻ; nếu là chẵn thì tìm hai chỉ số giữa rồi lấy trung bình- Nếu pivot chia danh sách gần như thành hai nửa, lượng xử lý là
n + n/2 + n/4 + ... = 2n, nên trở thành O(n)
Muốn tránh trường hợp xấu nhất thì cần pivot tốt
- O(n) trung bình của quickselect dựa trên điều kiện rằng việc chọn pivot đủ tốt
- Nếu không may, chẳng hạn mỗi bước đều chọn giá trị lớn nhất làm pivot, thì mỗi bước chỉ loại bỏ được một phần tử và trở thành O(n²)
- Để đảm bảo thời gian tuyến tính ngay cả trong trường hợp xấu nhất, cần cung cấp cho quickselect một pivot đủ tốt trong thời gian tuyến tính
- Thuật toán chọn pivot này được Blum, Floyd, Pratt, Rivest và Tarjan phát triển năm 1973; bài báo liên quan được liên kết tại 1973 paper
Chọn pivot bằng median-of-medians
- median-of-medians là quy trình chọn pivot tốt để quickselect sử dụng
- Luồng triển khai như sau
- Nếu có ít hơn 5 phần tử, dùng hàm tìm trung vị dựa trên sắp xếp hiện có
- Chia danh sách thành các nhóm 5 phần tử
- Để đơn giản, bỏ các nhóm không đủ 5 phần tử
- Sắp xếp từng nhóm và thu thập trung vị ở chỉ số 2
- Tìm lại trung vị trong danh sách các trung vị đã thu thập và trả về làm pivot
- Vì kích thước mỗi nhóm được cố định là 5, việc sắp xếp theo nhóm được coi là thời gian hằng số, và toàn bộ là công việc O(n)
- Lời gọi đệ quy để tìm trung vị của các trung vị được đưa vào phân tích như một bài toán con có kích thước
n/5
Vì sao có thể loại bỏ ít nhất 30%
- Có thể phân tích chất lượng của pivot bằng cách tưởng tượng rằng ta sắp xếp các nhóm 5 phần tử thành từng cột, rồi sắp xếp lại các trung vị của mỗi cột để chọn trung vị của các trung vị
- Ngay cả trong trường hợp xấu nhất khi pivot lệch về phía trước nhiều nhất có thể, các phần tử ở một số phần tư nhất định vẫn được đảm bảo nhỏ hơn hoặc lớn hơn pivot
- Nếu lấy 3 phần tử ở mỗi cột và xét một nửa số cột, ta có thể loại bỏ ít nhất
3/5 * 1/2 * n = 3/10 n phần tử
- Tỷ lệ loại bỏ được đảm bảo: {p:30}
- Tổng thời gian chạy được biểu diễn bằng hệ thức truy hồi sau
T(n) = n + T(n/5) + T(7n/10)
- Ở đây,
n tương ứng với công việc phân hoạch, T(n/5) là tính median-of-medians, còn T(7n/10) là tìm kiếm đệ quy của quickselect
- Vì hệ thức truy hồi này có hai hạng đệ quy, không thể áp dụng định lý Master đơn giản; chứng minh bằng quy nạp là cách trực quan hơn
Kết quả kết hợp: tìm trung vị trong thời gian tuyến tính
- quickselect có thể tìm trung vị trong thời gian tuyến tính nếu được cung cấp pivot đủ tốt
- median-of-medians có thể chọn pivot tốt cần thiết cho quickselect trong O(n)
- Kết hợp hai thuật toán này sẽ tạo thành thuật toán tìm trung vị hoặc phần tử thứ n của danh sách trong thời gian tuyến tính
Lựa chọn trong triển khai thực tế
- Trong thực tế, chọn pivot ngẫu nhiên hầu như luôn là đủ
- median-of-medians cũng có thời gian tuyến tính, nhưng trên thực tế có thể chậm vì chi phí tính pivot lớn
- Thư viện chuẩn C++ sử dụng introselect, kết hợp heapselect và quickselect, với cận trên O(n log n)
- introselect thường bắt đầu bằng một thuật toán nhanh nhưng có cận trên xấu, rồi chuyển sang thuật toán chậm hơn nhưng có cận trên tốt khi không chọn được pivot hiệu quả
- Trong so sánh số phần tử mà hàm quickselect xem xét, pivot tất định hầu như luôn xét ít phần tử hơn pivot ngẫu nhiên, nhưng so sánh này không bao gồm chi phí tính median-of-medians
- new paper xuất bản năm 2017 trình bày cách khiến hướng tiếp cận median-of-medians có thể cạnh tranh với các thuật toán chọn khác
1 bình luận
Các ý kiến trên Hacker News
Khoảng 4 năm trước, tôi đã so sánh nhiều thuật toán tìm trung vị, và bài viết dài hơn dự kiến rất nhiều :)
https://danlark.org/2020/11/11/miniselect-practical-and-generic-selection-algorithms/
Cách đây 10–15 năm, tôi thường xuyên phải tìm trung vị của hàng tỷ giá trị được parse từ các mục log dài nhiều kilobyte. Khi đó chúng tôi dùng MapReduce để xử lý dữ liệu lớn, và với lượng dữ liệu như vậy, không chỉ cần thời gian tuyến tính mà còn cần một cách có thể phân tán trên nhiều máy trong một lượt duyệt, nếu có thể
Việc biết trước độ chính xác và phạm vi của dữ liệu rất hữu ích. Các giá trị là thời gian tính bằng mili giây nguyên nên không âm, và chúng tôi cũng biết phân vị thứ 90 nhỏ hơn 1 giây rất nhiều
Thông thường việc tìm trung vị đòi hỏi thao tác tương tự sắp xếp, nhưng với các điều kiện này thì có thể dùng bucket sort. Chỉ cần tạo một dictionary, tức histogram, với key là thời gian mili giây nguyên và value là số lần xuất hiện
Vì không biết thời gian tối đa, để kích thước dictionary không phình to, mọi giá trị vượt quá 999ms đều được đưa vào bucket 999ms; như vậy chỉ bị giới hạn ở khoảng 2000 số nguyên gồm các key 0–999 và các value. Điểm này khác với bucket sort thông thường, và ngay cả khi phân tán bằng MapReduce cũng có thể xử lý rất dễ trong một lượt duyệt, rồi sau đó lấy trung vị từ histogram
Con số 10.000 chỉ là ví dụ tùy ý, nhưng số mẫu cần cho mức tin cậy mong muốn có thể tính bằng thống kê, và tôi nghĩ nó sẽ không quá lớn
Trong một số hệ thống tôi từng xử lý, Prometheus hoạt động như thể đặt giới hạn khoảng 10 giây cho độ trễ. Vì vậy các request vượt quá giới hạn đó đều được ghi nhận là 10 giây, dù thực tế có thể lâu hơn. Khá thú vị
Có phần tái bút nói rằng năm 2017 đã có một bài báo mới khiến cách tiếp cận median-of-medians có thể cạnh tranh với các thuật toán selection khác, và tác giả bài báo, Andrei Alexandrescu, đã cho biết điều đó
Ông ấy cũng có một bài trình bày về thuật toán của mình vào năm 2016. Ông là người thuyết trình thú vị, nên tôi rất khuyến nghị
There's Treasure Everywhere - Andrei Alexandrescu
https://www.youtube.com/watch?v=fd1_Miy1Clg
Nếu bạn là người dùng phần mềm, tôi khuyên nên nghe và đọc tất cả các bài viết, bài nói chuyện của Andrei mà bạn có thể tìm được. Bài trình bày này cũng thật sự là một kho báu
Hồi đại học tôi đã học thuật toán median-of-medians quickselect và thấy thật sự ấn tượng. Tôi đã thử tự triển khai, nhưng nó chậm kinh khủng. Thời gian chạy tăng tuyến tính, nhưng để điều đó có ý nghĩa thì danh sách phải có ít nhất hàng chục tỷ phần tử
Khi tôi nói chuyện này với một người bạn học cao học, anh ấy nói đại ý rằng: “Nó chậm thật, nhưng điều quan trọng là nó chứng minh rằng có thể selection trên một danh sách chưa sắp xếp trong thời gian O(n). Từng có lúc người ta không biết liệu điều đó có khả thi hay không, và giờ ta biết là có thể, nên cũng có thể tồn tại các thuật toán tuyến tính nhanh hơn”
Đó là một bài học vừa quá đơn giản vừa sâu sắc, đến mức tôi suýt nộp đơn vào cao học. Tôi không biết người bạn đó có còn nhớ cuộc trò chuyện này không, nhưng với việc học của tôi thì đó là một khoảnh khắc mang tính bước ngoặt
Cũng có thể nghĩ rằng “vì ta đã biết có một thuật toán nào đó tồn tại, nên cũng có thể có thuật toán nhanh hơn”. Vì sao sự tồn tại của thuật toán O(n) lại là tín hiệu mạnh hơn sự tồn tại của thuật toán O(n log n)?
Tôi nhớ hệ số hằng số của thuật toán này khoảng 22, nhưng cũng có thể đó là một thuật toán liên quan
Một điểm thú vị của thuật toán median-of-medians là danh sách tác giả hoàn toàn thuộc hàng toàn sao
Manuel Blum - người nhận giải Turing năm 1995
Robert Floyd - người nhận giải Turing năm 1978
Ron Rivest - người nhận giải Turing năm 2002
Bob Tarjan - người nhận giải Turing năm 1986 và là người đầu tiên nhận giải Nevanlinna năm 1982
Vaughan Pratt - người duy nhất trong danh sách không nhận giải Turing, nhưng là giáo sư danh dự Stanford, từng dẫn dắt dự án SUN trước khi nó trở thành Sun Microsystems, đóng vai trò quan trọng thời kỳ đầu của Sun với tư cách trưởng bộ phận nghiên cứu và nhà thiết kế logo Sun, đồng thời để lại nhiều thứ thú vị như chứng chỉ tính nguyên tố Pratt
Bốn giải Turing độc lập cộng thêm cả SPARCstation nữa, bài báo này có đủ
Danh sách tác giả đúng là ấn tượng
Chữ “P” trong thuật toán KMP cũng là Pratt
return l[len(l) / 2]Tôi không phải chuyên gia Python, nhưng trong Python toán tử
/chẳng phải trả về số thực dấu phẩy động sao? Tại sao không dùng phép chia nguyên//thay vì dùng số thực làm chỉ số mảng?Nếu mảng không quá lớn thì có thể không thành vấn đề, nhưng vẫn có mùi code smell khá rõ. Nếu là người mới học Python nên không biết có hai toán tử riêng thì còn có thể bỏ qua, nhưng trong bài còn có đoạn lạ hơn: một nhánh dùng chia nguyên, nhánh khác dùng chia số thực
def quickselect_median(l, pivot_fn=random.choice):if len(l) % 2 == 1:return quickselect(l, len(l) // 2, pivot_fn)else:return 0.5 * (quickselect(l, len(l) / 2 - 1, pivot_fn) +quickselect(l, len(l) / 2, pivot_fn))Đã có tới 50 bình luận mà dường như không ai thấy chuyện này, chỉ càng củng cố định kiến sẵn có của tôi về chất lượng code Python trung bình
Tôi nghĩ dùng số thực để index mảng sẽ gây exception
Tác giả đã chọn một ngôn ngữ lập trình thật trông giống giả mã thay vì dùng giả mã, và để minh họa thì có lẽ đoạn code chạy được ổn
Tôi đọc bài gốc rất thích, nhưng đoạn “nếu ở mỗi bước chọn phần tử lớn nhất làm pivot thì có thể thành O(n²) thay vì O(n)” khiến tôi hơi vướng
Nếu lo đầu vào mang tính đối kháng, có thể shuffle dữ liệu trước trong O(n) để ngăn chuyện đó bị cưỡng ép xảy ra. Nếu dữ liệu quá lớn nên khó shuffle, thì chỉ cần trộn một lần khi bucket đã nhỏ tới kích thước có thể shuffle được
Nếu đã shuffle, xác suất đảm bảo trường hợp xấu nhất thực tế sẽ không xảy ra. Nếu ai đó nói “về mặt kỹ thuật” vẫn có thể, tôi sẽ đáp rằng “về mặt kỹ thuật” kẻ tấn công cũng có thể đoán đúng mọi bit của khóa riêng 256-bit
Thế giới của chúng ta được xây trên xác suất. Mọi khóa riêng đều được bảo vệ bởi sự bất khả về mặt toán học rằng không ai có thể đoán chính xác
Theo cách tôi hiểu, quickselect sau khi shuffle trên thực tế là O(n)
Dù vậy, nếu có thể tin cậy nguồn ngẫu nhiên thì xác suất thời gian chạy vượt quá O(n) là rất thấp
Floyd-Rivest cũng làm được việc đó. Nếu tôi nhớ không nhầm thì còn hiệu quả hơn một chút
Nhưng tôi rốt cuộc vẫn không hiểu được nguyên lý hoạt động của nó
https://en.m.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm
Khi chọn phần tử thứ n, nếu n rất nhỏ hoặc rất lớn thì median-of-medians có thể không phải lựa chọn tốt nhất
Thay vào đó có thể dùng pivot lệch như [1], hoặc cách mà tôi gọi là “phần tử thứ j trong k”. Floyd-Rivest cũng có thể tăng tốc
Tôi có một dự án sở thích đạt thông lượng 1,2~2,0 lần so với quickselect được triển khai tốt: https://github.com/koskinev/turboselect
Nếu có tài liệu về thuật toán chọn tại chỗ tổng quát và nhanh, tôi rất quan tâm
[1] https://doi.org/10.4230/LIPIcs.SEA.2017.24
Cũng có thể dùng thuật toán streaming để tính gần đúng các phân vị tùy ý mà không cần lưu toàn bộ dữ liệu trong bộ nhớ
Có thể cho phép tính gần đúng không? Cần giả định gì về dữ liệu để đặt giới hạn sai số? Làm sao kiểm chứng rằng các giả định đó vẫn còn đúng?
Cá nhân tôi có lẽ sẽ nghiêng về thuật toán quickselect trong bài gốc cho tới khi rơi vào tình huống buộc phải cân nhắc cách xấp xỉ trung vị kiểu streaming