週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

ところで、三項メジアンの場合、比較回数はどれだけ少なくなるのでしょう。 三項メジアンはquicksortの高速化手法の一つです。 ピボットを単にひとつランダムに選ぶ代わりに、要素を三つ選んでその中間の値をピボットに採用します。たしかSedgewickのalgorithmsかどこかにありました。

比較回数は、普通のquicksortと比較して高々定数倍の違いしかないはずです。なぜなら、O(N log N)はソートの計算量の下限なので、三項メジアンを採用しても比較回数は少なくともO(N log N)になるためです。しかしどのくらいでしょう?

次のような関数を想定してみます。

def qsort_median3(elements):
  n = len(elements)
  p = random.randrange(len(elements))
  q = random.randrange(len(elements))
  r = random.randrange(len(elements))
  if elements[p] < elements[q]:
    if elements[q] < elements[r]:
       i = q
    elif elements[p] < elements[r]:
       i = r
    else:
       i = p
  elif: # cut
  # cut
  # pivot = elements[i]
  k = partition(elements, i)  # partition: needs n-3 comparison
  # k is the position of the pivot
  qsort_median3(elements[0..k])  # comparison comp(k)
  qsort_median3(elements[k+1..n])  # comparison comp(n-1-k)

この場合、比較回数関数comp(n)は次のようになるはずです。

comp(0) = 0
comp(n) = n + 1/(n*n*n) * sumk((1 + 3*(n-1) + 6*k*(n-k-1)) * (comp(k)+comp(n-k-1))

k はピボットの値です。(1 + 3*(n-1)...のところで、ピボットがkとなる場合の数を計算しています。

計算結果です。

三項メジアンつきquicksortの比較回数

少しだけしか速くない。比を取ったほうがわかりやすいかも知れません。

三項メジアンと普通のquicksortとの比較回数の比
N = 100とか短いところは無視して,N <= 10000のところを注目すると、およそ1割速くなっています。こんなもんでしょうか。それともプログラムが間違っているかもしれません。

プログラムがあっているとすると、

  • 性能向上はこの程度
  • ほかの最適化と組み合わせると有効
  • 比較回数で性能向上は測れない

このあたりが思い当たります。実測もしないとだめですね。

スポンサーサイト
コメント
この記事へのコメント
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
http://gusmachine.blog49.fc2.com/tb.php/242-674ddee6
この記事にトラックバックする(FC2ブログユーザー)
この記事へのトラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。