Thuật toán tôi yêu thích: Tìm median trong thời gian tuyến tính (2018)

Tìm median trong O(n log n)

• Cách đơn giản nhất là sắp xếp danh sách rồi chọn giá trị ở giữa
• Độ phức tạp thời gian của sắp xếp dựa trên so sánh là O(n log n)
• Ví dụ mã:

  def nlogn_median(l):  
      l = sorted(l)  
      if len(l) % 2 == 1:  
          return l[len(l) // 2]  
      else:  
          return 0.5 * (l[len(l) // 2 - 1] + l[len(l) // 2])  
  

Tìm median trong O(n) trung bình

• Có thể dùng thuật toán "quickselect" để tìm median với thời gian tuyến tính trung bình

• Thuật toán đệ quy do Tony Hoare phát triển

• Quy trình:

  1. Chọn một chỉ số ngẫu nhiên trong danh sách và đặt làm pivot
  2. Chia danh sách thành hai nhóm dựa trên pivot:
     • các phần tử nhỏ hơn hoặc bằng pivot
     • các phần tử lớn hơn pivot
  3. Đệ quy tìm tiếp trong nhóm có chứa median

• Ví dụ mã:

  import random  
  
  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))  
  
  def quickselect(l, k, pivot_fn):  
      if len(l) == 1:  
          assert k == 0  
          return l[0]  
  
      pivot = pivot_fn(l)  
      lows = [el for el in l if el < pivot]  
      highs = [el for el in l if el > pivot]  
      pivots = [el for el in l if el == pivot]  
  
      if k < len(lows):  
          return quickselect(lows, k, pivot_fn)  
      elif k < len(lows) + len(pivots):  
          return pivots[0]  
      else:  
          return quickselect(highs, k - len(lows) - len(pivots), pivot_fn)  
  

Chứng minh O(n) trung bình

• Nếu pivot chia danh sách gần như làm đôi, mỗi lần gọi đệ quy sẽ chỉ xử lý một nửa dữ liệu của bước trước
• Chứng minh toán học:

  C = n + n/2 + n/4 + n/8 + ... = 2n = O(n)  
  

O(n) xác định

• Bảo đảm thời gian tuyến tính ngay cả trong trường hợp xấu nhất

• Dùng thuật toán "median-of-medians" để chọn pivot

• Quy trình:

  1. Chia danh sách thành các nhóm 5 phần tử
  2. Sắp xếp từng nhóm và chọn median
  3. Chọn median của các median làm pivot

• Ví dụ mã:

  def pick_pivot(l):  
      assert len(l) > 0  
  
      if len(l) < 5:  
          return nlogn_median(l)  
  
      chunks = chunked(l, 5)  
      full_chunks = [chunk for chunk in chunks if len(chunk) == 5]  
      sorted_groups = [sorted(chunk) for chunk in full_chunks]  
      medians = [chunk[2] for chunk in sorted_groups]  
      median_of_medians = quickselect_median(medians, pick_pivot)  
      return median_of_medians  
  
  def chunked(l, chunk_size):  
      return [l[i:i + chunk_size] for i in range(0, len(l), chunk_size)]  
  

Tóm tắt

• Thuật toán quickselect có thể tìm median trong thời gian tuyến tính nếu chọn được pivot phù hợp
• Thuật toán median-of-medians là cách chọn pivot bảo đảm thời gian tuyến tính ngay cả trong trường hợp xấu nhất
• Trong thực tế, chọn pivot ngẫu nhiên thường đã đủ hiệu quả

Tổng kết của GN⁺

• Bài viết này giải thích nhiều thuật toán khác nhau để tìm median, đặc biệt tập trung vào cách tìm median trong thời gian tuyến tính
• Thuật toán quickselect nhanh về trung bình, nhưng có thể dùng median-of-medians để phòng trường hợp xấu nhất
• Trong các ứng dụng thực tế, chọn pivot ngẫu nhiên thường là đủ hiệu quả trong phần lớn trường hợp
• Một thuật toán có chức năng tương tự là introselect, hiện được dùng trong thư viện chuẩn C++

[GN⁺]

Ý kiến trên Hacker News

• Đã viết một bài dài so sánh nhiều thuật toán tìm trung vị khác nhau vào 4 năm trước
• 10-15 năm trước, đã dùng MapReduce để tìm trung vị trong các mục log có hàng tỷ giá trị
  • Nếu biết độ chính xác và phạm vi của dữ liệu thì có thể dùng bucket sort
  • Biểu diễn thời gian bằng mili giây nguyên và tạo histogram để có thể dễ dàng tìm trung vị
• Năm 2017, đã có một bài báo được công bố giúp cách tiếp cận median-of-medians trở nên cạnh tranh với các thuật toán chọn khác
  • Andrei Alexandrescu đã có một bài nói về thuật toán này vào năm 2016
• Danh sách tác giả của thuật toán median-of-medians rất nổi tiếng
  • Manuel Blum, Robert Floyd, Ron Rivest, Bob Tarjan, Vaughan Pratt, v.v.
• Thuật toán Floyd-Rivest cũng hiệu quả nhưng khó hiểu
• Dùng thuật toán streaming có thể tính gần đúng mà không cần lưu toàn bộ dữ liệu vào bộ nhớ
• Có cách sửa đổi quicksort để chọn trung vị
• Từng nhận được câu hỏi phỏng vấn về việc tìm trung vị trong một danh sách có hàng nghìn tỷ con số
  • Đã dùng cách đặt cận trên và cận dưới để tìm trung vị, nhưng đó không phải phương pháp tối ưu
  • Có một cách hiệu quả hơn là dùng priority heap
  • Sau đó đã bắt đầu đăng ký LeetCode
• Đã chia sẻ một ví dụ đơn giản được triển khai bằng Go
• Radix sort có thể dùng cho nhiều kiểu dữ liệu khác ngoài số nguyên, chẳng hạn như chuỗi