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

なんかちゃんと実装して速度を測って、あと論文だけ見ればいいような気がしてきました。しかしACMの会員はもう切れていて、古い論文はなかなか手に入りません。ようやく Sedgewick, R., "Implementing Quicksort Programs," Comm. ACM, 21, 10 (1978) 847--857.は見つかりました。

ここまで、比較回数の平均や分散を表す漸化式は自分で計算してきました。同時に これらを検算するために、次のような、比較回数をランダムに計算するコードを作っていました。

def comp(n):
  if n == 0:
     return 0
  k = random.randrange(n)
  return n - 1 + comp(k) + comp(n - 1 - k)

これを利用する際にさまざまなイベントが。

  • 乱数のためにメルセンヌツイスタを導入。検索したら、SIMD-oriented Fast Mersenne Twisterなるより速いMTが存在することを発見。
  • 標本分散は標本数NじゃなくてN-1で割るのが正しいはず、と思って統計の本を探しまくる。Χ二乗分布をまったく忘れていました。
スポンサーサイト
コメント
この記事へのコメント
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
http://gusmachine.blog49.fc2.com/tb.php/244-756b4149
この記事にトラックバックする(FC2ブログユーザー)
この記事へのトラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。