priority queue (というか heap) 関係の論文で、任意の要素を削除する操作が出てくるのだが、これの用途は何だろう?
任意の要素の優先順位を変更するのは、グラフ関係で使うらしい。実際、Dijkstra の最短経路アルゴリズムでは確かに使う。
だが、削除はどうなのだろう?
スケジューラでキャンセルするときとかかな。
Python には heapq.nlargest(n, iter) という、イテレータ iter 中の大きいもの n個を取り出す関数がある。(小さいものを取り出す heapq.nsmallest もある)
さて、iter の長さ (繰り返す回数) を m として、m は n よりも十分に大きいとしよう。これの計算量はどうなるか。iter からすべてのデータを読み出すのに O(m) かかるのはしょうがないので、O(m) が最善である。
もちろんやりかたによるわけであるが、素朴に考えられるのはソートを使うことである。iter を全部読み込んで、ソートして、大きいもの n個を取り出す。読み込みに O(m), ソートに O(m log m), 取り出すのに O(n) かかる。というわけで O(m log m) となる。
さて、heapq.nlargest がそうやっているかというと、もちろん違う。heapq というモジュール名が示すように、ヒープを使う。
ヒープの使い方にもいろいろあるが、まず、ソートと同様にぜんぶ読み込む場合を考えよう。iter を全部読み込んで、サイズ m のバイナリヒープを構成し、大きいもの n個を取り出す。読み込みに O(m), ヒープの構成に O(m), 取り出すのに O(n log m) かかる。というわけで、O(m) となる。最善ですばらしい。
しかし、iter の長さに比例してメモリを消費するというのは、よろしくない。もっと少ないメモリ消費で済むものを考えてみよう。
サイズ n のヒープを使ってみよう。
サイズ n のヒープにどんどん値を入れていき、サイズが n を越えたら小さい方から捨てていく。そうすると、iter からひとつ読み込む度に、サイズ n のヒープにひとつ値を挿入し、ひとつ削除することになる。挿入も削除も O(log n) で、m回繰り返すので O(m log n) となる。
まぁ、ヒープ内の最小よりも小さなものは入れても捨てるだけなので入れるまでもなく捨ててよいが、そうやっても最悪計算量は変わらない。
では、n よりもちょっと大きなサイズのヒープを使ってみよう。
1 < a としてサイズ an とする。そうやって、an個読み込む毎にヒープを作って大きいもの n個を取り出し、残りを捨てる。
全体の長さが m なので、m/(an) 回それを繰り返す。一回毎に、残っている n個と新しく読み込んだ an 個でヒープを構成するのでそれが O((1+a)n), その中から n個取り出すのが O(n log((1+a)n)) なので、トータルでは m/(an) を乗じてそれぞれ O((1+a)m/a), O((m/a)log(1+a) + (m/a)log(n)) となる。前者は O(m) なのでぜんぶ読み込んだときと同じである。後者は、a を log(n) に等しくなるように選べば、やっぱり O(m) とできる。
というわけで、a = log(n) としてヒープのサイズを n log n にとれば、時間計算量をぜんぶ読み込んだ場合と同じ、つまり最善なものにできる。
「第七回Wikiばな 〜 Wikiの起源へ〜」にいってきた。
Wikiばなで (メモが間違ってなければ) 紹介されていた On the Nature of The Nature of Order を検索したら 和訳 があった。
来週の水曜は FSIJの月例会で、今年やった Google Summer of Code の話である。
興味がある人はどうぞ。
ちょっと inotify を使ってみる。
% /usr/bin/ruby -rinotify -e '
i = Inotify.new
i.add_watch("/tmp", Inotify::CREATE | Inotify::DELETE | Inotify::MOVE)
i.each_event {|ev| printf "%s %#x\n", ev.name.inspect, ev.mask }
'
これで、/tmp のファイルの増減を見張れる。
那須
[latest]