Hatena::ブログ(Diary)

菊やんの雑記帳

2010-02-28 ヒープソートによる素数判定?

[] なぜか素数判定をやるのにヒープソートがでてきたでござるの巻 09:27  なぜか素数判定をやるのにヒープソートがでてきたでござるの巻を含むブックマーク

今週末はSPOJのPRIC(http://www.spoj.pl/problems/PRIC/)をやってるのだが、なぜか素数判定にヒープソートを使うというわけの分からない実装ができてしまった。

まず、等差数列を素数で割ったあまりを考えると

anmod 3mod 5mod7mod 11mod 13
111111
3520029
6904634
103135412
13722457
17101362
205102710
23924185
27303090
307126108

こんな感じに規則的に並ぶじゃん。当たり前だけど、ほとんどの素数pの列はp行ごとに0がでてくる。

だから試し割したい素数の数に対して、その素数周期のタイマーを走らせておけばタイマーが発火したらそこは合成数じゃん。

大量のタイマーを管理する簡単な方法は、発火時間の近い順にソートしたリストをもっておいて、一つ前のタイマーとの時間差を持っておく方法で、こうしておくと、1tickごとに変数を一個デクリメントして0かどうか判定するだけで、全てのタイマーのカウントダウンを行える。

大昔のLinuxカーネルのタイマーとかこんなだった。

というわけで、PRICでこれを使うと変数を一個デクリメントして0かどうかを見る。0だったら合成数。違ったら素数。エクスパイアしたタイマーは再開してタイマーリストの適切な場所に挿入する。これだけでいいじゃん。

でも、よく考えてみたら再開したタイマーをリストに挿入するのが遅そう→そうだヒープソートを使おう!

というわけで、ヒープソートを使ってタイマーリストを作ると何がうれしいかというと

  • 結局、一番最初に発火するタイマーだけわかってれば、あとは線型に並んでる必要がないことを利用できる。完全にソートする必要はなくてヒープを組み立てるだけでよい。
  • エクスパイアしたタイマーをすぐに正しい位置に戻せる

と思って実装してみたんだけど、というか、この方法は一番最初に思いついたけど面倒だから無視してたんだけど、

微妙に速くない。それなりに10位台にはなりそうなスピードではあるけれども…

ヒープソートの部分に実行時間の8割をもってかれて、でも、ヒープソートって高速化できる工夫が入る余地が全くない…