ヒープソートのアルゴリズムCodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。
統計的に正しいランキングを行う方法をJavaで書く - バイオインフォマティクスって何ですか？
Java | 統計的に正しいランキングを行う方法を見たのでちょっとJavaで書いてみる。はじめになにがしたいかというと、「レイティング」というのをご存じでしょうか。Amazonとかで商品を購入者が星つけて評価したりしてるやつ。ああいうので「良かったランキング」というのを作りたい。みんなが「購入して良かった」という評価をつけてる商品は、他の人にとっても「良かった商品」になる可能性が高い。いい商品だということがわかるわけです。問題点じゃあどういうふうにランキングをつければいいの？ということを考えると、次の問題にぶちあたる。評価してる人の数の違い。例えば、Aという商品は100人が評価していて、平均の星の数は 4.8 だとする。一方、Bの商品は1人が星5つで評価していたとする。このとき、Aの商品とBの商品ではどちらをランキング上位にすればいいだろうか？あなたならどちらを買いたい？Aはたくさんの人が
Blunderについて - やねうらおブログ(移転しました)
今年の第19回世界コンピュータ将棋選手権に出場したBlunderは、C#で書かれたコンピュータ将棋である。 コンピュータ将棋ではC#で書くとC++などで書かれた場合の1/4〜1/2ぐらいの速度しか出ないのだが*1、一次予選を3位で通過した。二次予選は惜しくも7位で終わったが、初出場とC#というハンデのわりには、十分な奮闘を見せたと思う。 そのBlunderのソースがこの度、公開された。 http://hp.vector.co.jp/authors/VA039571/blunder/ いまのところソースが公開されている将棋プログラムを強さ順に並べると、 GPS将棋 Bonanza Blunder うさぴょん …(以下略) こんな感じか。 GPS将棋とBonanzaが圧倒的なのは言うまでもないが、Blunderも、C++で書き直したりすれば、あとR200〜300ぐらいは上がる見込みがあるので、
Canonical Huffman Codes - naoyaのはてなダイアリー
1999年出版と少し古い書籍ですが Managing Gigabytes を読んでいます。理解のために 2.3 で出て来る Canonical Huffman Codes の習作を作りました。 ハフマン符号は情報圧縮で利用される古典的なアルゴリズムで、圧縮対象データに出現するシンボルの出現確率が分かっているときに、その各シンボルに最適な符号長の接頭語符号を求めるものです。 通常のハフマン符号はポインタで結ばれたハフマン木を構築して、ツリーを辿りながら各シンボルに対する接頭語符号を計算します。このハフマン木には曖昧な箇所が残されています。ハフマン木は木の辺を右に辿るか左に辿るかで符号のビットが決まりますが、右が 0 で左が 1 などというのはどちらでも良いという点です。(曖昧だから駄目、という話ではありません。) 従って、ハフマン木から生成される符号は一意には決まりません。 ここで各シンボル
DO++: AND検索の最尤推定
検索技術においてAND検索、つまり二つの単語を指定して、それが両方出現している文書数の推定を高速に行うのは難しい問題です。 問題を正しく書くと単語w_xが出ている文書番号(x1,x2,x3,..,xn)とw_yが出ている文書番号(y1,y2,y3,...,ym)が与えられたら | {(i,j)|x_i = y_j} | の数を求める問題です。 これは前もって全通り求めて保存しておくにも単語種類数の二乗のオーダー分必要なのでできません。 これは機械学習でも特徴関数が0/1の値しかとらないとき、二つの要素の特徴ベクトルの内積を求める問題と同じで、またデータベースでもJOINの順番を決めるときにでてくる問題です。 普通は全体の文書からサンプルをとって、その中で数えてみて、それを元のサイズにスケールさせることをします。例えば全体文書1億件の中から文書1000件だけとってきて、その中でw_xとw_y
1時間でわからせたコンシステントハッシュで仮想ノードが必要な理由 - 西尾泰和のはてなダイアリー
ConsistentHashing - コンシステント・ハッシュ法 とあるチャットで聞かれて図まで書いて解説したのでもったいないからエントリー化。ちなみにチャットが1時間弱だったのでこういうタイトルにした。 で、Bが消えるとBの責任範囲が全部Dに押し付けられてDがかわいそうでしょ。 Dの仕事が増えるでしょ。Cとか暇そうじゃん！サーバを複数用意しているメリットが薄れてる。みんなが同じくらい働くのが望ましい。 で、Bが1個の点で表現されているから「Bの手前」もDの1個だけで、そのせいで全部Dが引き受けるはめになった。つまり、仕事が細かく分割されてなくて1個の塊だから引き継ぐ人も1人だけで引き継いだ人涙目。あらかじめ仕事を100分割しとけばみんなで分担して肩代わりできて幸せだよね。 だからサーバが5個だけど点は5個じゃなくて500個打とう。それが仮想ノード。 実装はどうするの？という質問に対して
algorithm - 最近点検索をkd-treeで : 404 Blog Not Found
2009年04月30日01:00 カテゴリMathLightweight Languages algorithm - 最近点検索をkd-treeで というわけで、kd-treeによる検索も実装してみました。 はてなブックマーク - ototoiのブックマーク データ数が少ない場合、この全検索が高速。ただデータが多くなってくるとkd-treeがいいと思う。点ならば配列をソートするだけで実現できる。 以下のデモでは、単にkd-treeによる検索だけではなく、kd-tree構築の速度と、総当たりの場合の速度の比較もできるようにしてあります。10,000点ぐらいだと、その差を顕著に感じることが出来るでしょう。100,000点ぐらいあると、感動的なほど差が出ます。それだけあってもkd-treeの方はほぼ1ms以内に検索が終わるのですから(ただしこの場合、デモの実行に合計10秒以上かかるので注意!)。
分布推定アルゴリズム - yukobaのブログ
分布推定アルゴリズム。遺伝的アルゴリズムを改良した物です。個体の集合を交叉・突然変異させるのではなく、個体の生成確率を進化させます。最適化問題のアルゴリズムです。以下、自分へのメモです。わかったことが増えたら追記するかも。 ビットストリング 計算量に関しては、ビット数をn、反復数をTとしています。 Population-Based Incremental Learning (PBIL) http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.61.8554 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.5424 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.1108 Population-ba
『C言語による最新アルゴリズム事典』
奥村晴彦『C言語による最新アルゴリズム事典』技術評論社，1991年，ISBN4-87408-414-1，2400円 大きな画像（1.1M） 1987年10月にPascalを使った『コンピュータ・アルゴリズム事典』を，1991年2月にその改訂版としてANSI C言語を使った『C言語による最新アルゴリズム事典』を出版しました（いずれも技術評論社）。そのサポートページをつくろうと思いながら多忙のためなかなかできませんでした。とにかく始めなければ……というわけで，サポートページまがいのものを作ってみました。 石田晴久ほか『コンピュータの名著・古典100冊』（インプレス，2003年）に選んでいただきました。100冊といっても日本人の書いたものは20％しかなく，たいへん恐縮しています。 Frequently Asked Questions どの銘柄のC言語ですか？ ほぼ当時のANSI Cドラフトに基づ
おとうさんにもわかるYコンビネータ！(絵解き解説編) - よくわかりません
先日YコンビネータのきしださんのYコンビネータのエントリが話題になっていました。 ずいぶん日にちが経ってしまいましたが、自分も、自分なりにYコンビネータのあたりを絵解きで整理してみたいと思います。きしださんのエントリタイトル*1に引っ掛けて、目標として、自分の父親(非プログラマ。その辺のおっさん)でも解る内容を目指します。 なぜ不動点演算子というのか、不動点だったらなぜ再帰なのか、この辺りも含めて、実感を持って納得できればいいなと思います。 きしださんのエントリのおさらい 本題の前に、きしださんのエントリをおさらいしておきます。 Yコンビネータはただのオモチャじゃないんだよ 関数だけで色んな事が出来る 条件分岐をする関数ってのもある。 再帰(ループ)を作れる関数もある。←これがYコンビネータ。 数値も関数で表現できる。 つまり、関数だけで、条件分岐も、再帰(ループ)も、数値も作れちゃう！！
inforno :: Python: 勉強がてらDHT(Kademliaっぽいもの)を実装しました
前々から一度じっくり勉強しないとなぁと思っていたDHTまわりの勉強がてらKademliaっぽいものをPythonで実装してみました。 Kademliaはいろいろ実装があるので、ソースを読んじゃうと答えみちゃった感じになるかなーと思って、元論文と 首藤様の資料 くらいしか見ずに実装してみました。ので、いろいろ間違ってるかも知れませんが･･･。 本家Kademliaとの主な違いは UDPではなくTCPを使っている ローカル環境しかもっていないので、UDPパケットがロスしやすい場合(WAN)を想定して実装するのがめんどくさい。 よってRPC-IDをつけていない。 パケットの分割や再送もTCPにおまかせ。 original publisherから一定時間publishを受けなくてもインデックス情報をexpireしていない 実装するのは簡単です。 ノードがネットワークに参加したとき、Index情報を
なぜ関数プログラミングは重要か
John Hughes, Institutionen för Datavetenskap, Chalmers Tekniska Högskola, 41296 Göteborg, SWEDEN. rjmh@cs.chalmers.se この日本語訳は原著者の承諾を得て山下がここに公開するものです。 この訳文についての、御指摘などは山下伸夫(nobsun .at. sampou.org)までおねがい いたします。 翻訳最終更新日 : 2011-09-17 原文 "Why Functional Programming Matters" 日本語訳PostScript この論文は1984年以来何年ものあいだChalmers大学のメモとして回覧された。 1989年と1990年に幾分か改訂をしたのが[Hug89]と [Hug90]である。この版はもとのChalmer大学のメモ のnroff原稿をもとに
さあ、Yコンビネータ(不動点演算子)を使おう！ - よくわかりません
前回、おとうさんにもわかるYコンビネータ！(絵解き解説編) - よくわかりませんというエントリで、Yコンビネータ(不動点演算子)と再帰の絵解き解説をしました。 Yコンビネータ自身は、結局のところ再帰を産み出してくれるだけです。関数(正確にはλという単純な文字列変換ルール)だけで出来て、プログラミングに関するいろんな原理の研究を可能にするのが凄い訳です。その辺のさわりを、きしださんが解説されています。しかし、単なる再帰なら、実際のプログラミングではYコンビネータなんて使わなくても出来ます。 じゃあ、Yコンビネータとか不動点とかは、偉い学者さんとかが研究に使えばいいもので、普通のプログラマには何の意味もないモノなのでしょうか？ というわけで、今回はポジティブに、Yコンビネータや不動点で出てくる考え方を、理論だけじゃなく、実際のプログラミングに応用する例を見てみましょう。 今回、プログラムの例を
B木の Copy-Modify 方式での実験的コード - Tociyuki::Diary
id:naoya さんの Python 版B木に触発されて、Ruby 版の insert・delete だけを実装した B 木を書いてみました。 実装にあたり、標準的な教科書に良く掲載されている Overwrite 方式ではなく、現代的な Copy-Modify 方式、すなわち B 木の葉から根に向かって更新のおこなわれるノードを複製してから修正をおこなっていき、最後に根をすげ替える方式に挑戦してみました。こうすることにより、更新の途中でなんらかの例外が発生したとしても、直前の B 木を壊さずにすみ、安全にロール・バックすることができるようになります。また、更新の途中の元の B 木はいっさいがっさい元のままですから、根を変更バージョンごとに持つようにすれば、現代的なデータ・ベース・マネジメント・システムに採用されている Multi-Version Concurrency Control(M
はてなブックマークFirefox拡張, JavaScript で IS 法 による Suffix Array 構築 - naoyaのはてなダイアリー
昨日、はてなブックマークFirefox拡張をリリースしました。おかげさまでベータ版からダウンロード数は累積で1万ダウンロードを突破し、アクティブユーザー数も伸びています。 はてなブックマークFirefox拡張で新しいインターネットを体験しよう http://b.hatena.ne.jp/guide/firefox_addon 開発者の id:secondlife が g:subtech:id:secondlife:20090415:1239804170 で技術的な側面からのちょっとした TIPS なども紹介していますので、興味のある方はご一読ください。 検索では思いのほか SQLite の like 検索が高速なのに驚いた。はてブ検索では、検索ワードから URL, Title, コメント にマッチしたものを表示していて、それ専用の search_data だかかんらかの検索用カラムがある。
ラムダ計算とチューリングマシンの違い 2009-04-13 - きしだのはてな
ぼくもYコンビネータがわかるようになるまではそうだったのだけど、Yコンビネータを使うとどのような処理ができるのかがよくわからなくて悩んでいる人が多いように思う。他の人のブログを見ても、名前をつけずに再帰ができるのがすばらしいとか書いてあったりするのだけど、それによってどういう処理ができるのかわからずにいた。 結論をいえばYコンビネータには、なにかの処理を便利にする能力はない。関数であらゆる計算ができるということが示せれば、あとは用なしだ。理論の礎としてうまってしまえばいい。 結局、Yコンビネータによってどのような処理ができるかというのは、ラムダ計算の要素のメリットをチューリングマシンの中に見出そうとしてるといえる。 ラムダ計算とチューリングマシンは、どちらも計算モデルという点では一致しているけど、全く違う。 無限であるか有限かの違いといってもいい。 チューリングマシンでは、データの量と処理
コサイン距離ベースのLSHをRubyで - <s>gnarl,</s>技術メモ”’<marquee><textarea>￥
参考文献:Web+DB press vol.49 レコメンド特集のPart3など。 アルゴリズムの概要 詳細(特に数学的な)はぐぐれ。 モチベーションとしては、高次元における近傍点探索を高速で行いたい。まじめにやるとどう工夫しても計算量がすごいことになるので、近似で。 どうするかというと、「距離が近いと同じような値になるハッシュ関数」を使う。あるベクトルの近傍を求めたい場合、そのベクトルのハッシュと同じ(もしくは近い)値のハッシュを持つベクトルをテーブルから引いてきて返す。計算量がどうなるかはややこしいけど、とりあえず全部探すよりは速い。 で、どういう関数をハッシュとするのか。これは距離の定義によって異なる。ハミング距離、コサイン距離、ユークリッド距離などにはそういった関数の存在が知られている。 コサイン距離の場合、ランダムなベクトルをいくつか用意して、入力されたベクトルがそれらと似ている
Não Aqui! » 10行強で書けるロジスティック回帰モデル学習
ロジスティック回帰（logistic regression）の学習が，確率的勾配降下法（SGD: stochastic gradient descent）を使って，非常に簡単に書けることを示すPythonコード．コメントや空行を除けば十数行です． リストの内包表記，条件演算子（Cで言う三項演算子），自動的に初期化してくれる辞書型（collections.defaultdict）は，Python以外ではあまり見ないかも知れません． リストの内包表記は，Haskell, OCaml, C#にもあるようなので，結構メジャーかも知れません． [W[x] for x in X] と書くと，「Xに含まれるすべてのxに対し，それぞれW[x]を計算した結果をリストにしたもの」という意味になります．sum関数はリストの値の和を返すので，変数aにはXとWの内積が計算されます． Pythonでは，三項演算子を条
PDL で PageRank - naoyaのはてなダイアリー
id:smly さんが PageRank や HITS を Python で実装 されているのに触発されて、自分も PageRank を Perl で実装してみました。 PageRank の計算の中心になるのは Power Method (べき乗法) です。べき乗法では行列とベクトルの積を計算しますので、手軽に使える行列演算ライブラリがあると楽でしょう。 色々調べてみたところ、PDL (The Perl Data Language) が良く使われているようでしたので、これを選択しました。PDL では各種行列演算が簡単に行える他、文字列評価をオーバーライドして行列の文字列出力を良い具合で定義してくれていたりと、なかなかに便利です。PDL は行列計算以外にも色々な科学技術計算やグラフ描写などの操作をサポートしているようです。 さて、PDL を使った PageRank 計算のコードは以下のように
最長共通部分列問題 (Longest Common Subsequence) - naoyaのはてなダイアリー
部分列 (Subsequence) は系列のいくつかの要素を取り出してできた系列のことです。二つの系列の共通の部分列を共通部分列 (Common Subsecuence)と言います。共通部分列のうち、もっとも長いものを最長共通部分列 (Longest Common Subsequence, LCS) と言います。 X = <A, B, C, B, D, A, B> Y = <B, D, C, A, B, A> という二つの系列から得られる LCS は <B, C, B, A> で、その長さは 4 です。長さ 2 の<B, D> の長さ 3 の <A, B, A> なども共通部分列ですが、最長ではないのでこれらは LCS ではありません。また、LCS は最長であれば位置はどこでも良いので、この場合 <B, D, A, B> も LCS です。 LCS は動的計画法 (Dynamic Prog
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
