私の好きなアルゴリズム: 線形時間での中央値探索 (2018)

O(n log n)で中央値を見つける

• リストをソートしてから中央値を選ぶ、最も単純な方法
• 比較ベースのソートの計算量は O(n log n)
• コード例:

  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])  
  

平均 O(n)で中央値を見つける

• quickselect アルゴリズムを使うと、平均的には線形時間で中央値を見つけられる

• Tony Hoare が開発した再帰的アルゴリズム

• 手順:

  1. リストから任意のインデックスを選んで ピボット に設定
  2. ピボットを基準にリストを2つのグループに分ける:
     • ピボット以下の要素
     • ピボットより大きい要素
  3. 中央値を含むグループを再帰的に探索

• コード例:

  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)  
  

平均 O(n) の証明

• ピボットがリストをおおよそ半分に分ける場合、各再帰呼び出しは前の段階のデータの半分に対して動作する
• 数学的証明:

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

決定的 O(n)

• 最悪の場合でも線形時間を保証

• median-of-medians アルゴリズムを使ってピボットを選択

• 手順:

  1. リストを5個ずつのグループに分ける
  2. 各グループをソートして中央値を選ぶ
  3. 中央値たちの中央値をピボットとして選ぶ

• コード例:

  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)]  
  

まとめ

• quickselect アルゴリズムは、適切なピボットを選べば線形時間で中央値を見つけられる
• median-of-medians アルゴリズムは、最悪の場合でも線形時間を保証するピボット選択法
• 実際には、任意のピボット選択でも十分に効果的

GN⁺の要約

• この記事は中央値を見つけるさまざまなアルゴリズムを説明し、とくに線形時間で中央値を見つける方法を扱っている
• quickselect アルゴリズムは平均的には高速だが、最悪の場合に備えて median-of-medians アルゴリズムを使うこともできる
• 実際の応用では、任意のピボット選択でたいてい十分に効果的
• 類似の機能を持つアルゴリズムとして introselect があり、これは C++ 標準ライブラリで使われている

[GN⁺]

Hacker Newsの意見

• 4年前に、さまざまな中央値アルゴリズムを比較した長い記事を書いた
• 10〜15年前、数十億個の値を持つログ項目から中央値を見つけるためにMapReduceを使った
  • データの精度と範囲が分かっていれば、バケットソートを使えた
  • タイミングを整数ミリ秒で表し、ヒストグラムを作成することで中央値を簡単に見つけられた
• 2017年に、中央値の中央値アプローチを他の選択アルゴリズムに対して競争力のあるものにした論文が発表された
  • Andrei Alexandrescuがこのアルゴリズムについて2016年に講演した
• 中央値の中央値アルゴリズムの著者一覧は非常に有名
  • Manuel Blum, Robert Floyd, Ron Rivest, Bob Tarjan, Vaughan Pratt など
• Floyd-Rivestアルゴリズムも効率的だが、理解しにくい
• ストリーミングアルゴリズムを使えば、全データをメモリに保存しなくても近似値を計算できる
• クイックソートを修正して中央値を選択する方法がある
• 面接問題として、数兆個の数字があるリストから中央値を見つける問題を出された
  • 上限と下限を設定して中央値を見つける方法を使ったが、最適な方法ではなかった
  • 優先度ヒープを使うより効率的な方法があった
  • その後、LeetCodeのサブスクリプションを始めた
• Goで実装されたシンプルな例を共有した
• Radixソートは整数以外にも、文字列などさまざまなデータ型に使える