ref:http://www.algo.ics.tut.ac.jp/~yusuke_abe/html/2008-03-01.html#2008-03-01-1 「常識的」が「普通」に書き換わったのはなぜだろう． それはちょうどこのへんを読んだので、その通りかも、と思って修正した結果です。 さて、それはともかくとして、エ…

ref:http://www.algo.ics.tut.ac.jp/~yusuke_abe/html/2008-02-19.html#2008-02-19-1 Project Euler をやっている人は素数関係の部分をライブラリ化するに違いないと思う今日この頃ですが、エラトステネスの篩だろ、常識的普通に考えて。 % time java Prime …

ref:404 Blog Not Found:アルゴリズム百選 - 二分探索(binary search) あとまぁ、どうでもいいといえばどうでもいいのだけど。 範囲指定する場合、終端は終端要素のインデックス + 1 で与えるのが通例じゃないのかなぁ。というか、終端要素のインデックスを…

ref:404 Blog Not Found:アルゴリズム百選 - 二分探索(binary search) 面白い応用としては、Suffix Arrayというものがあります。これは無秩序に並んだデータ、例えば一般的なテキストファイルに対応する秩序だったデータ構造を用意し、それに対して二分探索…

ref:Quick Sort - mono-hateの日記 なんか以前も Haskell での quick sort について書いたような記憶があるけども、Python でもできたりするな。 def quicksort(xs): if len(xs) == 0: return [] x = xs[0] return quicksort([y for y in xs[1:] if y < x]) …

ファイルの中にある文字列が何回出現するか数えたいとする。 sub count_occurrences { my ($search, $text) = @_; my @m = ($text =~ /\Q$search\E/g); return scalar @m; } さて、このサブルーチンはうまく動くだろうか。うまく動かないとすれば、何がまず…

ref:みずぴー日記 - 文字列の距離 via:Blog/2007-8-20 - Rocco の日記 普通、こういうのは edit distance (編集距離) と言うんじゃないかな、と思うんだけども文字列間距離だけでも通じるもの？Hamming distance とか無視ですか、そうですか。 アルゴリズム…

なんか Java で Suffix Array なコードというリクエストがあったので簡単に。 とりあえず Suffix Array の構築だけ。効率とか一切無視で。 import java.io.IOException; import java.util.Arrays; import java.util.Comparator; import java.util.regex.Matc…

多分、Suffix Treeを作って、一番深い分岐を調べるという方針になるのかと思います。 Suffix Treeだと大きな文書だとSuffix Arrayを作って順次隣接する要素を比較していけばよいのかと。 どちらの方が速いのかというと、どうなんでしょう？ より正確には Gen…

ref:lethevert is a programmer - 問題 : 文字列処理 うん、まぁ、Suffix Array を使って「任意部分文字列の頻度計数」なんてことをやっていた自分にとっては、手元のコードを組み合わせて30行ほどのコードを書け足せば、それなりの速度で動くものが出来上が…

データ系列の任意区間から最小値(もしくはその位置)を取得する操作を Range Minimum Query というのだが、これは n 個のデータに対して O(n) の前処理をしておけば O(1) で計算できることが知られている。 で、その実装が九州大学の坂内さんのページで公開さ…

今度は単語単位のソートにしてベンチマーク。元データは同じく新聞記事約 30MBytes (単語数 5,727,663)。 ついでに MSD Radix Sort も加えてみた。 で、きむらさんのところを見て、そういや、プロファイルとってないなと思ったので、g++ -O2 -pg でコンパイ…

クイックソートは、その性質上、再帰の最後の方になってくるとほとんど同じ要素同士を比較することになってしまうので、文字列配列の場合、最後の方の比較のコストがかなり大きくなってしまうので、それが影響しているのではないかと。 む。そうかも。 まぁ…

文字列ソーティングの速度比較にいくつかのアルゴリズムで Suffix Array を構築してみた。 対象データは 30 MBytes ほどの英文新聞記事データで、gcc 4.0 で -O2 でコンパイル。結果はこんな感じ。 algorithm time[sec] quicksort 97.33 multikey quicksort …

ref:lethevert is a programmer - 文字列ソート ref:ときどきの雑記帖 リターンズ 2007年3月 文字列をソートするのに、クイックソート系のアルゴリズムをつかうのと、マージソート系のアルゴリズムを使うのでは、効率が大分変わる。 と思うのだけれど、マー…

ref:西尾泰和のブログ: ICTスクール日記 あー、2つのファイルを連結して圧縮して、圧縮率を Similarity Measure に使って Clustering するって話でいいのかな。以前、梅村先生が Conference でそんなのを聞いてきたって嬉しそうに紹介してたような記憶がある…

ref:404 Blog Not Found:Algorithm - O(n log(n))より速いsort まぁ、データの特性が利用できるならO(n log n)より速いアルゴリズムが存在するのは、その道の人には常識だったりもするが。 sub bucket_sort(\@&){ my ($aref, $cref) = @_; my @bucket = (); …

ref:落ちてないけど堕ちている - 「安定」なクイックソート stable な quick sort もあるよ、という話なのだが。 quicksort :: Ord a => [a] -> [a] quicksort [] = [] quicksort (x:xs) = quicksort [ y | y <- xs, y < x ] ++ [x] ++ quicksort [ y | y <-…