MapReduce - naoyaのはてなダイアリー
"MapReduce" は Google のバックエンドで利用されている並列計算システムです。検索エンジンのインデックス作成をはじめとする、大規模な入力データに対するバッチ処理を想定して作られたシステムです。 MapReduce の面白いところは、map() と reduce() という二つの関数の組み合わせを定義するだけで、大規模データに対する様々な計算問題を解決することができる点です。 MapReduce の計算モデル map() にはその計算問題のデータとしての key-value ペアが次々に渡ってきます。map() では key-value 値のペアを異なる複数の key-value ペアに変換します。reduce() には、map() で作った key-value ペアを同一の key で束ねたものが順番に渡ってきます。その key-values ペアを任意の形式に変換すること
アルゴリズムを知るとプログラムが豊かに書ける | こえむの編集後記
アルゴリズムを学ぶと、プログラムの幅が広がるよ！それも言語に囚われずに。というお話。 最近作った『シムエントリ』。 自然言語処理(テキストマイニング)の知識を学んだことで、初めて開発できたサービスです。 しかし、ほんの1ヶ月前まではこれらの知識なぞさっぱりありませんでした。たまたま、現在スポットで勤めている某研究所でプログラムの助手をしていたのがきっかけで、学ぶ機会に恵まれました。 さて、日々プログラムに触れられている皆様、アルゴリズムに純粋に触れる機会はどの程度でしょうか？ 現在よく使われている高級言語(Java, Perl, Python, etc…)には様々なライブラリが揃えられていて、そのライブラリが動くアルゴリズムを知らなくても、存在を覚えさえすればプログラムが書けてしまいます。例としては、配列のソートや、ハッシュテーブルなどでしょうか。 そして、巷でよく見かけるプログラム技術は
404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10
2007年11月26日18:15 カテゴリMathLightweight Languages プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10 ぎくっ あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな なぜぎくってしているかというと、実はすでにアルゴリズム本の発注を受けているからなのだ。いつまでも伏せておくのもなんなので、ここにえいやっとdiscloseしてしまうことにする。 アルゴリズム大募集! C&R研究所 - トップページ その下書きもかねて、そこでも紹介しないわけに行かないメジャーなアルゴリズムをとりあえず10個紹介しておくことにする。 ユークリッドの互除法(Euclidean algorithm) その昔(数百年ほど前)は「アルゴリズム」といえば、「手順一般」を指すのではなく、この「互除法
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。
Mostly-Concurrent Mark & Sweep GC のアルゴリズム
目次 1. 前置き 2. HotSpot VM 1.4.x の GC の種類 3. Mostly-concurrent Mark & Sweep 4. 応用 4.1 世代別 GC との組み合わせ 4.2 カードマーキング (Card Marking) 4.3 並列化 (Parallel GC) 4.4 ビットワイズ・スイープ (Bitwise Sweep) 4.5 インクリメンタル・コンパクション (Incremental Compaction) 5. 参考文献 脚注 コメント 1. 背景 ガーベージコレクション(GC) には色々なアルゴリズムが存在するが、大雑把に言って Stop-the-World (STW) 型 GC と On-the-fly 型 GC に大別される。 STW 型の GC はプログラムの実行中にはガーベージの回収を行わず、メモリが枯渇した時になって始めてガーベージの回
suffix array
更新履歴 2004/01/07 O(N) 構築アルゴリズム三種追加（Ko &Alulu, Kim & al., Karkkainen & Sanders) Suffix Arrayは、最近注目を集めているデータ構造です。その理由として、 (1)大規模なデータに対して、高速に検索、情報抽出を行うことができる (2)BWTとしてデータ圧縮に用いることができる。 ことが挙げられます。(1)に関しては自然言語処理において、膨大な量のコーパスから情報（例えば、単語の出現回数など）を調べるときににSuffix Arrayを用いると非常に高速に求めることができます。 膨大な量のコーパスに基づいた自然言語処理が盛んになってきている今、Suffix Arrayが注目を集めています。 また、ゲノム情報を調べるバイオインフォマティクスにおいても、ここの配列と似ている部分（例えばCCAG）を調べるといった場合
きまぐれ日記: 動的配列への追加コストはなぜ 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
スペル修正プログラムはどう書くか
Peter Norvig / 青木靖 訳 先週、2人の友人(ディーンとビル)がそれぞれ別個にGoogleが極めて早く正確にスペル修正できるのには驚くばかりだと私に言った。たとえば speling のような語でGoogleを検索すると、0.1秒くらいで答えが返ってきて、もしかして: spelling じゃないかと言ってくる(YahooやMicrosoftのものにも同様の機能がある)。ディーンとビルが高い実績を持ったエンジニアであり数学者であることを思えば、スペル修正のような統計的言語処理についてもっと知っていて良さそうなものなのにと私は驚いた。しかし彼らは知らなかった。よく考えてみれば、 別に彼らが知っているべき理由はないのだった。 間違っていたのは彼らの知識ではなく、私の仮定の方だ。 このことについてちゃんとした説明を書いておけば、彼らばかりでなく多くの人に有益かもしれない。Googleの
hnwの日記 - PHPの奇妙なround関数
(2012/11/01追記) 4年ほど前の記事「PHP5.3.0alpha3のround関数の実装がPHP5.2.6と変わった - hnwの日記」でお伝えした通り、PHP 5.3.0から別の実装が採用されており、本ページで指摘しているような挙動のPHPは既に絶滅危惧種です。念のため。 さて、プログラミングの話題もたまには書いてみます。今回はPHPのround関数の挙動が変だ！という話題です。 round()は浮動小数点数を四捨五入する関数で、大抵の言語に同じ名前で実装されているかと思います。ではPHPのround関数の何が問題なのか、ちょっと試してみましょう。 $ uname -sro Linux 2.6.9-42.0.10.plus.c4smp GNU/Linux $ php --version PHP 5.1.6 (cli) (built: Feb 23 2007 06:56:38)
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://yimado.s-lines.net/algo_and_ds/