Perlのstable quicksort - てきとうなメモ
stableなquicksortないかなと思っていろいろ探していたらPerlのquicksortがstableな実装だった． perl5.10.0のpp_sort.cより引用． Perlのquicksortについては以下のようなデータ構造を利用している． indir list1 +----+ +----+ | | --------------> | | ------> first element to be sorted +----+ +----+ | | --------------> | | ------> second element to be sorted +----+ +----+ | | --------------> | | ------> third element to be sorted +----+ +----+ ... +----+ +----+ | | ----
Wavelet Tree - naoyaのはてなダイアリー
圧縮全文索引の実装などでしばしば利用される Rank/Select 辞書と呼ばれるデータ構造があります。詳しくは参考文献を参照していただくとして、今回は一般の文字列に対して効率的に Rank/Select を可能とするデータ構造である Wavelet Tree (ウェーブレット木) のライブラリを作りました。 http://github.com/naoya/perl-algorithm-wavelettree/tree/master my $wt = Algorithm::WaveletTree->new("abccbbabca"); is $wt->rank(6, 'a'), 2; is $wt->rank(6, 'b'), 3; is $wt->rank(9, 'b'), 4; is $wt->select(0, 'a'), 0; is $wt->select(1, 'a'), 6;
Schwartzian transform - Wikipedia
This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (February 2024) (Learn how and when to remove this message) In computer programming, the Schwartzian transform is a technique used to improve the efficiency of sorting a list of items. This idiom[1] is appropriate for
404 Blog Not Found:javascript - Array#sortがオレquicksortより遅い!?
2006年11月23日14:45 カテゴリLightweight Languages javascript - Array#sortがオレquicksortより遅い!? な、なんだってー!? ごっつええブログ - JavaScriptによるソートアルゴリズムの比較実験 『JavaScriptを使って一定以上の数量をもった数値配列をソートする場合は、組み込みメソッドよりもクイックソートを使用したほうが高速である』 自分でも検証してみた。 どうやらMozilla系列のJavaScript実装に関しては嘘ではないらしい。以下で確認してほしい。 Firefox 2に関してはほぼ同等だが、Mac IE 5, Safari 2.0.4, Opera 9.02ではbuiltinの方が速かった。しかしその差は最も大きかったSafariでも3倍程度で、builtinとしてはやはり遅いように見える。 # of
Rubyの浮動小数点数リテラルの扱いは正しいのか - hnwの日記
題名の通りなんですが、前回の記事「PHP以外全員不正解」に対して「ダウト！」を頂戴したのでまとめてみます。 Cのこの動作が、唯一無二絶対のものであるとする根拠はどこにあるのでしょうか? strtod によれば、 If the subject sequence has the decimal form and at most DECIMAL_DIG (defined in ) significant digits, the result should be correctly rounded. If the subject sequence D has the decimal form and more than DECIMAL_DIG significant digits, consider the two bounding, adjacent decimal strings L and
スパムはあっちいけ！「ベイジアン・フィルターによるスパム判定」
さてじゃあ今度は「ベイジアン・フィルター」を使ったスパム判定だ。何か「名前のついた技法」っていうと、結構ヘヴィなように感じるが、これはそれほどには大した技法ではない。原理は簡単だ。 「通常投稿の例」と「スパムの例」を収集して、その単語ベースの特徴を整理して保存しておく。それで入力テキストで使われる単語の特徴が、どちらに近いか？を判定する。で、「スパム」と入力が判定されたら、「スパムの例」にそれを追加し、「通常投稿」と判定されたら「通常投稿の例」に追加する。 まあ、そんな「学習」タイプのものなので、実はこの「ベイジアン・フィルター」は最近のメーラのスパム対策の主流になっている技術だ。とはいえ、これをそのまま持ってくる...となると、少し考慮が必要ではある。 掲示板スパムで今問題なのは、「（ほとんど）同じ内容の投稿」を大量に繰り返し投稿することだ。実はこのベイジアン・フィルターのアルゴリズムで
[を] Dynamic Programming による類似文字列マッチの実装例
Dynamic Programming による類似文字列マッチの実装例 2007-01-22-4 [Programming][Algorithm] 「Modern Information Retrieval」(8.6.1 p.216) での Dynamic Programming (DP) の解説のところのアルゴリズムを 素直に Perl で実装したみた。 さらにマッチ箇所取り出しロジックも実装してみた。 DP はいわゆる「類似文字列検索（あいまい検索）」に使うと 便利なアルゴリズム。 実は、大学院でも前の会社でも、PerlやらC++やらで実装して使ってた。 単純ながら使い勝手もよく、まさに現場向きかと。 grep 式に頭から見ていくので計算量的にはイマイチなのだが、 転置インデックス検索などで範囲を絞ってから適用すれば実用上問題ない。 ■定義みたいなの Q1. 二
Rabin Karp アルゴリズムでコード重複の検出 blog.bulknews.net
Rabin Karp アルゴリズムでコード重複の検出 YAPC::NA で会った Fotango の Norman Nunley がつくってる Algorithm::RabinKarp モジュールが面白げです。 Rabin Karp 文字列探索アルゴリズム (wikipedia) を使って文字列のハッシュ（ダイジェスト）をチェックし、同一の値を示す部分を重複しているとみなしてレポートしてくれます。つまり、プロジェクト内のコードのコピーペーストを検出するツールとして使えるというわけ。 ためしに Plagger で試してみた結果は rabin.txt のようになりました。プラグインの register_hook や CustomFeed での Feed オブジェクトの生成など、イディオム的に使う部分が大半になってしまっていますが、いくつか実際コピペで再利用しているコードが検出できています。 c
多次元配列であれこれ 続き - hibomaの日記
２次元の配列でビットマップをまねて、左右対称に反転／上下対称に反転 を再現する操作 の続きをやります。 今度は2次元の配列（行列？平面？）を「９０度回転」する操作をしてみようと思います。画像を90度回転する ってよくやるよね。写真の縦横の向きを変えたりとか。その操作の再現。 っとその前に前日のコードのリファクタリングからやります。 my @A = qw(a1 a2 a3 a4); my @B = qw(b1 b2 b3 b4); my @C = qw(c1 c2 c3 c4); my @D = qw(d1 d2 d3 d4); my $XY = [ \(@A , @B , @C , @D) ]; 配列は全部無名配列にしてリファレンスとしてぶっ込みました。入れ子になったこの配列をこれからごにょごにょします。 配列に対する操作は sub y_reverse { my $ref = shift;
多次元配列 ->「ビットマップ」？ - hibomaの日記
唐突ですが my $A = ['a1' , 'a2' , 'a3' , 'a4']; my $B = ['b1' , 'b2' , 'b3' , 'b4']; my $C = ['c1' , 'c2' , 'c3' , 'c4']; my $D = ['d1' , 'd2' , 'd3' , 'd4']; my @XY = ($A , $B , $C , $D ); #もしくはこっちの方が書き方キレイかな？ # #my @A = qw(a1 a2 a3 a4); #my @B = qw(b1 b2 b3 b4); #my @C = qw(c1 c2 c3 c4); #my @D = qw(d1 d2 d3 d4); # #my @XY = \(@A , @B , @C , @D); 入れ子になったこんな配列があります。この配列はイメージとして # 1 2 3 4 # #A a1 a2 a3
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
