[B! perl][algorithm] makamaka_at_donzokoのブックマーク

makamaka_at_donzoko id:makamaka_at_donzoko

perlとalgorithmに関するmakamaka_at_donzokoのブックマーク (6)

quick sortよりも高速でmerge sortのように安定しているソートアルゴリズムtim sort [勘違い] - Islands in the byte stream
<追記>ベンチマークプログラムに誤りがありました。ソート済のシーケンスに対してソートを掛けていました。ご指摘ありがとうございます＞ak氏そんな夢のようなソートアルゴリズムがあるのかというと、あるらしいんです。それがtim sortと呼ばれるアルゴリズムです。画期的（？）なソートアルゴリズム「Sleep Sort」：濃縮還元オレンジニュース｜gihyo.jp … 技術評論社このあたりで拾ってきたネタですね。 merge sortを改良したアルゴリズムで、安定*1しており、しかも実行速度にも優れているとか。アルゴリズムの性能の評価は済んでいるらしく、CPythonやJDK7には既に導入済みのようですね。ならば当然Perlのソートも…と考えるわけですが、まず評価のためにJavaのソースをC++にそのまま移植してみました。それがこれ（いちおうテスト済）： https://github.co
makamaka_at_donzoko 2011/10/19
algorithm

perl
リンク
乱数と Perl5 にかんする蘊蓄の話 - tokuhirom's blog
Perlの乱数についてIRCで盛り上がったのでまとめておく。結論からいうと、srand()はPerl5組み込みのものでよい。乱数の生成はMath::Random::MTがよいとおもう。 Perlのrand()の実装はConfigure時に選べるようだが*1、ふつうはdrand48()がつかわれる。これは下位ビットがまったくランダムでないことで知られるrand(3)よりはましだが、しょせん線形合同法なのでセッションIDなどを作るのには安全ではない。安全な乱数を作るためにtime()やSHA1を混ぜ込んだりするほうほうもよくつかわれるが、そのくらいならはじめからM::R::MTを使ったほうがいいとおもう。なお、srand()はあれば/dev/urandomを読むので、自前でsrand(time)などとするのはよくない。また、最初にrand()を呼ぶときに自動的に呼ばれるので、ふつうは明示的
makamaka_at_donzoko 2010/08/19
math

algorithm

perl
リンク
ブロック処理を決定性有限オートマトン(DFA)化した Text-Creolize-0.003 - Tociyuki::Diary
「練習で書いてみたText-Creolize-0.001 - Tociyuki::Diary」では、とりあえずブロックの構文を LL(1) で記述し、構文解析表を使って動かしていました。コードを作るにはてっとり早くて楽ができる反面、プッシュ・ダウン・オートマトンとしてスタックへ後続記号をいちいちプッシュしつつループを回す分が余計なオーバーヘッドになっていました。ところで、この構文解析表を変形しているとき、この構文が正規文法であることに気がつきました。つまり、block、paragraph などが、有限オートマトンの状態に相当し、状態 A で記号 S を受理したとき必ず他の状態 B へ遷移し、再帰することなく最後まで遷移を繰り返していくだけで記号列を解釈することができます。変形した記号表は下のとおりです。しかも、常にすべての状態で記号に対して一意に遷移する先の状態が一つ決まっていますので、
makamaka_at_donzoko 2010/06/06
perl

algorithm
リンク
練習で書いてみたText-Creolize-0.001 - Tociyuki::Diary
Wiki フォーマットを共通化しようという試みの WikiCreole 1.0 と拡張案の一部の実装を Perl で練習で書いてみました。 ⇒ http://github.com/tociyuki/libtext-creolize-perl (2010-09-11以降のコミットはこちらで公開) ⇒ https://tociyuki.sakura.ne.jp/archive/Text-Creolize/Text-Creolize-0.012.tar.gz (目次作成機能追加版) ⇒ https://tociyuki.sakura.ne.jp/archive/Text-Creolize/Text-Creolize-0.011.tar.gz (プレースホルダとプラグインのバグ修正) ⇒ https://tociyuki.sakura.ne.jp/archive/Text-Creolize/Tex
makamaka_at_donzoko 2010/06/06
perl

algorithm
リンク
ギレンも登場！BM25なPerlモジュール書いたよ - download_takeshi’s diary
久しぶりに何か書きます。情報検索のアルゴリズムで「BM25」というものがあります。何年か前に某研究所に遊びに行ったときに「TF/IDFより精度のいいやつ」みたいな感じでかなりアバウトに教えてもらいました。その時は「名前だけでも覚えて帰ろう」と思っていたのですが、帰りに安い居酒屋で大酒をのみ、電車のなかで騒いでしまうほど酔っ払ってすっかりその名前を忘れてしまってました。（なにやってんだか・・・）で、最近Web+DB pressをパラパラ見ていたらBM25の名前を発見！ああ、これだこれだ、思い出したよ！というわけで、重い腰を上げてモジュール化してみました。 githubに上げてあります。 Lingua::JA::OkapiBM25 http://github.com/miki/Lingua-JA-OkapiBM25 そのうちCPANからも落とせるようになります。正式名称は「Okap
makamaka_at_donzoko 2009/12/08
perl

algorithm
リンク
PDL で PageRank - naoyaのはてなダイアリー
id:smly さんが PageRank や HITS を Python で実装されているのに触発されて、自分も PageRank を Perl で実装してみました。 PageRank の計算の中心になるのは Power Method (べき乗法) です。べき乗法では行列とベクトルの積を計算しますので、手軽に使える行列演算ライブラリがあると楽でしょう。色々調べてみたところ、PDL (The Perl Data Language) が良く使われているようでしたので、これを選択しました。PDL では各種行列演算が簡単に行える他、文字列評価をオーバーライドして行列の文字列出力を良い具合で定義してくれていたりと、なかなかに便利です。PDL は行列計算以外にも色々な科学技術計算やグラフ描写などの操作をサポートしているようです。さて、PDL を使った PageRank 計算のコードは以下のように
makamaka_at_donzoko 2009/03/09
perl

algorithm
リンク
1