第6回 上手なアルゴリズムの見つけ方
図1に示すHTML形式のテキスト・データ（以下，HTMLデータ）があります。このHTMLデータをブラウザに表示させたときに「表示される文字列」と「その文字列に対して有効なタグ名」を対応付けるアルゴリズムを考えてください。結果は配列に格納して，画面に表示させるものとします（図2）。 見わたせば，世の中はアルゴリズムだらけです。私のようなプログラマは，日常生活でも「締め切り順に仕事をソートしてごらん」「仕事のスタックがたまっているからてんてこまい」など，いま置かれている状態をアルゴリズムやデータ構造になぞらえて会話することがよくあります。前回紹介した再帰処理と言えば，落語の演目の一つ，「頭山」です。自分の頭に生えた桜の木を引っこ抜いて，その跡にできた池に自分自身が身を投げる，という不思議な話ですが，これこそ再帰処理をよく言い表していると思います。 このように世の中には，ハッシュだってスタックだ
やねうらお―よっちゃんイカは買ってもレニエのお菓子は買わない男 - アタック25必勝陣形について
3月25日放送分のアタック25で以下のような陣形になった。 □□■□□ □□■□□ ■■■■■ □□■□□ □□■□□ （■は緑、□は空き） 以下、イノセンスさんによる解説文。 まだ角を取る戦いが始まってないので勝負はここからのように思えるが、4人の解答者全員が自分にとって最も有益な行動を取った場合、なんとこの時点で緑の勝ちが確定する。この特殊な陣形を、私は「グランドクロス」と名づけた。 まず、アタック25の公式ルールによると、自分が引っくり返せるパネルがないときに正解したら、次に引っくり返せるパネルができるような位置を取らなければならない。 よって、グランドクロスの状況で緑以外の誰かが正解しても角にいきなり飛び込むことはできず、緑のパネルに隣接したどこかを取ることになる。ここでそのような取り方をしてしまうと、取った人以外の3人は次から角を取ることができるようになるにもかかわらず、取った本
文字列ソーティング #3 - odz buffer
今度は単語単位のソートにしてベンチマーク。元データは同じく新聞記事約 30MBytes (単語数 5,727,663)。 ついでに MSD Radix Sort も加えてみた。 で、きむらさんのところを見て、そういや、プロファイルとってないなと思ったので、g++ -O2 -pg でコンパイルして gprof で結果を見てみた。suffix_compare が strcmp の代わりの functor なんだけど普通にやるとインライン展開されちゃうから無理矢理別ファイルに分けてリンクしてある。 algorithm time[sec] quicksort 32.56 multikey quicksort 9.45 merge sort 20.46 MSD radix sort 15.74 std::sort 29.61 std::stable_sort 21.17 ==> mergesort
Quicksort が遅い理由 - odz buffer
クイックソートは、その性質上、再帰の最後の方になってくるとほとんど同じ要素同士を比較することになってしまうので、文字列配列の場合、最後の方の比較のコストがかなり大きくなってしまうので、それが影響しているのではないかと。 む。そうかも。 まぁ、なんにしても Multikey Quicksort が結構速いっすね。いや MSD Radix Sort も同じぐらいの性能が出るけど。 つうか、一口に文字列ソートといっても、どんなデータをソートするかによるわけだけど。DNA の塩基配列なんかだと MSD Radix Sort のが強いかも。
接尾辞配列 - odz buffer
ref:接尾辞配列 - Wikipedia ref:Suffix array - Wikipedia, the free encyclopedia ぬお。日本語版 Wikipedia に Suffix Array の項目が。接尾辞配列なんていっている人いるのか、とか思ったけど検索したらそこそこ使われているし。 で、どうも英語版の翻訳らしんだけど、日本語訳がすごいことになっているね。 The easiest way to construct a suffix array is to use an efficient comparison sort algorithm. This requires O(nlogn) suffix comparisons, but a suffix comparison requires O(n) time, so the overall runtime of
文字列ソーティング #2 - odz buffer
文字列ソーティングの速度比較にいくつかのアルゴリズムで Suffix Array を構築してみた。 対象データは 30 MBytes ほどの英文新聞記事データで、gcc 4.0 で -O2 でコンパイル。結果はこんな感じ。 algorithm time[sec] quicksort 97.33 multikey quicksort 63.66 merge sort 73.62 std::sort 90.30 std::stable_sort 76.61 む。クイックソートよりマージソートの方が速いし。マージのコストはたいしたことないのかな。 ちなみに、Suffix Array の構築に特化したアルゴリズムだとこんな感じ。 algoritm time[sec] two-stage sort 33.50 improved two-stage sort 17.30 skew algorithm
文字列ソーティング - odz buffer
ref:lethevert is a programmer - 文字列ソート ref:ときどきの雑記帖 リターンズ 2007年3月 文字列をソートするのに、クイックソート系のアルゴリズムをつかうのと、マージソート系のアルゴリズムを使うのでは、効率が大分変わる。 と思うのだけれど、マージソート系で文字列ソートを速くする方法ってあるのかな？ んーアルゴリズム的にはどちらも O(n log n)だったと思うし、 「効率がだいぶ変わる」というのは一体? 文字列の比較コストはコンスタントじゃないですからね。マージソートならマージの時に辞書的に近い位置の文字列ばかりを比較することになるから、比較コストが大きくなるってことなんじゃないでしょうか。 まぁ、データによるんでしょうけど、Suffix Array の構築とかになると結構違ってくるかもしれません。 ちなみに、文字列ソーティングに強いクイックソート
2 分法とニュートン法
計算機では整数の四則計算の組み合わせで, より複雑な計算をしているとおもってほぼまちがいない. たとえば の近似計算を考えてみよう. この数を近似計算するにはいろいろな方法があるが, 一つの方法は, は と の交点をもとめることである. 一般に を連続微分可能関数とし,
ユビキタスの街角 データ圧縮手法の応用
PPM (Prediction by Partial Matching)というデータ圧縮アルゴリズムがある。 一般に、あるデータ列が与えられているとき、次に来るデータを予測することができればデータ圧縮を行なうことができる。 データ列から判断して次に来るデータが「a」だと確実に判断できるときは「a」を記述する必要が無いからである。 PPM法では、既存のデータ列中の文字列出現頻度を計算することによってこのような予測を行なう。 たとえば「abracadab」というデータの次にどの文字が来るか予測する場合、 「a」は4回、「b」は2回出現している 「b」の後に「r」が続いたことがある 「ab」の後に「r」が続いたことがある ... といった情報を累積して確率を推定する。 この場合、 (3)から考えて次の文字は「r」である確率が高いが、 (1)も考慮すると「a」の確率もある、という風に計算を行なう。
末尾再帰のクイックソートつづき - maoeのブログ
先日のエントリに対してid:nozomさんからトラックバックをいただいた．どうやら先に挙げたページにあるquicksort/cpsのcpsは継続渡しスタイル(CPS)のことだったようだ．調べてみると確かにこのCPSは末尾再帰に変換するときによく使われるらしく，Wikipediaにも Besides space and execution efficiency, the tail recursion is important to allowing a common idiom in functional programming, continuation passing style (CPS), without quickly running out of stack space. とあり，リンク先には用例も載っている． ということで，昨日のqsortをCPSに変換する． その前にfilt
再帰クイックソートの可視化: Days on the Moon
「いやなブログ - JavaScript でソートアルゴリズムを可視化」より。何も考えずに再帰処理のクイックソートの様子を逐次描画しようとするとこうなります。 function quickSort(data, begin, end, log) { if (begin >= end) return data; var pivotPos = begin; var pivot = data[pivotPos]; for (var i = begin + 1; i < end; i++) { if (data[i] < pivot) { var temp = data[i]; data[i] = data[pivotPos + 1]; data[pivotPos + 1] = data[pivotPos]; data[pivotPos] = temp; pivotPos++; } } log(da
きまぐれ日記: 動的配列への追加コストはなぜ O(1)?
動的配列への追加コストは O(1) ってのは覚えていればそれだけの話ですが，どうしてかと言われると意外と難しいものです． というのも, このO(1)ってのは動的配列の実装方法に強く依存しているからです．実装を知っていないと答えられません． 一般論として，1つ要素を追加するとき，配列に空きがなかったら新しく配列を作り直して全要素をコピーする必要があります．コピーのコストは O(n) だから，追加コストも O(n) になるという議論が混乱の元になっています． こういうときは，要素追加を n 回繰り返したときの計算量を n で割った平均をとるという解析方法が使われるそうです．一般に, ある operation C の計算量を C を n 回行ったときの計算量 O(n) を n で割った値 O(n)/n で評価する手法をならし解析 (amortized analysis)と言うそうです． さて，s
メール転送のおはなし - どさにっき
2007年2月11日(日) 建国記念の日 ■ 無題 _ 障害連絡を受ける携帯に深夜にメールが飛んできて、すわ何事と起きてみたら、それが spam だったときのやるせなさといったら。 _ で、起こされた。さっき。 _ あした受信拒否設定しとこ。とりあえず、寝る。 2007年2月13日(火) ■ IE6 KeepAlive _ ちょと話題の これとか これとか これとか。 _ えーと、サーバが Connection: close を返しておきながらサーバの方からは TCP を切断しない場合、クライアントの IE はタイムアウトするまで仕事をサボるから遅い（≠重い）、ということでいいのかな。へー、こんな問題あるんだねぇ。知らなかった。今まで聞いたことなかったけど、よほどレアなケースなんだろう。 _ でも、うーん、これって IE のバグなのかなぁ？ _ HTTP ってアプリケーション層のプロトコル
k-nearest neighbors algorithm - Wikipedia
In statistics, the k-nearest neighbors algorithm (k-NN) is a non-parametric supervised learning method. It was first developed by Evelyn Fix and Joseph Hodges in 1951,[1] and later expanded by Thomas Cover.[2] Most often, it is used for classification, as a k-NN classifier, the output of which is a class membership. An object is classified by a plurality vote of its neighbors, with the object bein
Better Bayesian Filtering - ベイジアンフィルタの改善
ベイジアンフィルタの改善 --- Better Bayesian Filtering Paul Graham, January 2003 これは、Paul Graham： Better Bayesian Filtering を、原著者の許可を得て翻訳・公開するものです。 <版権表示> 本和訳テキストの複製、変更、再配布は、この版権表示を残す限り、自由に行って結構です。 (「この版権表示」には上の文も含まれます。すなわち、再配布を禁止してはいけません)。 Copyright 2002 by Paul Graham 原文: http://www.paulgraham.com/better.html 日本語訳：Shiro Kawai (shiro ＠ acm.org) <版権表示終り> Paul Graham氏のエッセイをまとめた『ハッカーと画家』の 邦訳版が出版されました。 出
パワー法による固有値と固有ベクトルの求め方
パワー法による固有値と固有ベクトルの求め方 Last modified: May 16, 2002 固有値・固有ベクトルを求める簡単な方法としてはパワー法がある（パワー法は，あくまでも簡便法である。より一般的で精度も十分で計算速度も速いアルゴリズムは数多くある）。 例題： 「行列 $\mathbf{A}$ の，固有値と固有ベクトルを求めなさい。」 \[ \mathbf{A} = \left ( \begin{array}{rrr} 1.0 & 0.5 & 0.3 \\ 0.5 & 1.0 & 0.6 \\ 0.3 & 0.6 & 1.0 \end{array} \right ) \] 固有値・固有ベクトルを求めたい行列を $\mathbf{A}$ とする。 > ( A <- matrix(c(1, 0.5, 0.3, 0.5, 1.0, 0.6, 0.3, 0.6, 1.0), b
ベイジアンフィルタについて
最近話題のベイズ理論を用いたフィルタについて整理してみました．まず，ベ イズ理論が注目され始めたというニュースを最初にみたのが，ＭＳも注目する “ベイズ”って何だ(oricom.co.jp)でした． このときは対して気にもとめていませんでしたが，再度興味をそそられ出した のが，グーグル、インテル、MSが注目するベイズ理論(CNET)のニュース． MSだけならまだしも，Googleが，というのが自分的には大きかったです．しか し，このニュースだけでは，この技術が具体的にどのように採用されるのか， 特に検索エンジンのような大規模なものに適用可能かどうかは大きな疑問でし た． そもそも，このベイズ理論がどこに聞いてくるのかということを考えるとその 疑問は自然だと思います．ベイズ理論（ベイズ推定）は，過去に起きた事象の 確率を利用して未来を予測する手法です．そのため，直感的にはユーザごとの 最適化
きまぐれ日記: ソートの平均要素移動距離
配列をソートする際に各要素の平均移動距離はどれくらいになるか問題が同僚の間で話題になった. 結論から言ってしまえば，サイズ n の配列の場合平均移動距離は n/3 になるらしい． サイズ n の場合, 最右の要素は [0 .. n-1] に等確率で移動するので，直感的に考えると n/2 のような気がする．しかし，真ん中の要素は両側に移動するので，その距離は小さくなる．平均移動距離は n/2 より小さい値になるはずだ. 頭で考えるより手を動かしたほうが楽なので，モンテカルロサンプリングしてみた. 配列をランダムにシャッフルし，ソート済みの配列と比較して各要素の平均移動距離を求める．これを 1000 回繰り返し平均値を計算する. #include <iostream> #include <vector> #include <cmath> #include <algorithm> static
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
アルゴリズムとデータ構造
ニュートン法