GoogleのMapReduceアルゴリズムをJavaで理解する
GoogleのMapReduceアルゴリズムをJavaで理解する：いま再注目の分散処理技術（前編）（1/2 ページ） 最近注目を浴びている分散処理技術「MapReduce」の利点をサンプルからアルゴリズムレベルで理解し、昔からあるJava関連の分散処理技術を見直す特集企画（編集部） いま注目の大規模分散処理アルゴリズム 最近、大規模分散処理が注目を浴びています。特に、「MapReduce」というアルゴリズムについて目にすることが多くなりました。Googleの膨大なサーバ処理で使われているということで、ここ数年の分散処理技術の中では特に注目を浴びているようです（参考「見えるグーグル、見えないグーグル」）。MapReduceアルゴリズムを使う利点とは、いったい何なのでしょうか。なぜ、いま注目を浴びているのでしょうか。 その詳細は「MapReduce : Simplified Data Proc
クラスタリングによる迷路作成アルゴリズム
はじめに クラスタリングアルゴリズムにより、解くと絵が浮かび上がる 迷路を作成する方法を紹介する。 クラスタリングとは ウェブのリンク情報や、mixiの友人関係など、ネットワークの性質を 知りたいことがよくある。このとき、ネットワークの性質として このネットワークにおいて任意に選んだ要素Aと要素Bはつながっているか？ このネットワークは全体がつながっているか？ つながっていないとしたらいくつのグループに分かれるか？ 要素数最大のグループはどれか？ などの情報が欲しくなる。このような解析をするときに 必要となるのがクラスタリングである。 クラスタリングとは、同値関係のリストが与えられたときにグループ分けを することである。たとえば、 友達の友達は友達である と定義すると、友人関係は同値関係を作る。 その上で、 A君とB君は友達 C君とE君は友達 B君とD
Cuckoo Hashing - Radium Software
ハッシュテーブルからエントリーを検索する処理は，一般に定数時間で済むとされている。つまり，どんなにエントリーが増えても検索の速さは変わらない，ということ。データ構造の教科書には必ず載っていることだね。 でも実際には，ハッシュの衝突が起こった場合に，速度の低下が発生する可能性がある。例えば，一般的なチェイン法（オープンハッシュ）だと，衝突したエントリーに関して線形検索を行うことになるから，衝突が多ければ多いほど，定数時間からは遠のいてしまう。 この速度低下を防ぐ方法はいろいろある。なかでも cuckoo hashing （カッコウ・ハッシング）は仕組みが面白い。こいつは，エントリーの検索を必ず定数時間で済ませてくれるという優れものなんだ。 Cuckoo hashing では，２つのハッシュ関数と，２つのテーブルを用いる。ここでは，２つのハッシュ関数をそれぞれ h1, h2 として，２つのテー
「解読不能は数学的に証明済み」、RSAを超える新暗号方式とは ― ＠IT
2008/04/11 すべての暗号はいずれ破られる。2000年前のシーザー暗号の時代から高度な暗号技術が一般化したデジタル通信の現代に至るまで、それが暗号通信の歴史が証明し続けた事実であると同時に、もっとも人口に膾炙したクリシェでもあった。例えば、鳴り物入りでリリースされたDVDのコンテンツ暗号技術「CSS」（Content Scramble System）が、リリースからわずか数年で10代のノルウェー人ハッカーに破られたことは記憶に新しい。 【追記】（2008年4月15日） この記事は取材に基づいて執筆したものですが、一部専門家らから「CAB方式暗号は解読不能」というのは誇大表現ではないかとの疑義が呈されています。アルゴリズムの公開や第三者による検証がない現在、この記事に登場するCAB方式が発案者・実装者の主張通り画期的な暗号方式で、本当に解読が不可能であるかどうか分かりません。現在、専
mixi Engineers’ Blog » コミュニティブラウザ
はじめまして。mixi開発部のskimuraです。 １月２８日にリリースした「コミュニティブラウザ」について書きたいと思います。 ■ コミュニティブラウザとは 存在するコミュニティが増加するほど、目的のコミュニティを捜し出すのは困難になると考えられます。mixiに存在するコミュニティは日々増加しており、今現在では180万以上ものコミュニティが存在します。そこで、興味があるコミュニティを探す手助けをするためのツールを作成したいと考え、本サービスを作成しました。コミュニティブラウザは各コミュニティ対して、関連性が高いコミュニティをおすすめするサービスです。それぞれのコミュニティに参加している各ユーザが参加しているコミュニティの傾向をもとに計算しています。 ■ コミュニティブラウザの使い方 コミュニティブラウザにアクセスすると自分の所属しているコミュニティの一覧が表示されます オススメコミュニテ
GC - GCアルゴリズム詳細解説 - livedoor Wiki（ウィキ）
GC¥¢¥ë¥´¥ê¥º¥à¾ÜºÙ²òÀâ ÆüËܸì¤Î»ñÎÁ¤¬¤¹¤¯¤Ê¤¤GC¥¢¥ë¥´¥ê¥º¥à¤Ë¤Ä¤¤¤Æ¾ÜºÙ¤Ë²òÀ⤷¤Þ¤¹ ¥È¥Ã¥×¥Ú¡¼¥¸¥Ú¡¼¥¸°ìÍ÷¥á¥ó¥Ð¡¼ÊÔ½¸ GC ºÇ½ª¹¹¿·¡§ author_nari 2010ǯ03·î14Æü(Æü) 20:47:11ÍúÎò Tweet ¤³¤ÎWiki¤¬Ìܻؤ¹½ê GC¤È¤Ï¡© GC¤ò³Ø¤ÖÁ°¤ËÃΤäƤª¤¯»ö ¼Â¹Ô»þ¥á¥â¥ê¹½Â¤ ´ðËÜ¥¢¥ë¥´¥ê¥º¥àÊÔ Reference Counter Mark&Sweep Copying ±þÍÑ¥¢¥ë¥´¥ê¥º¥àÊÔ IncrementalGC À¤ÂåÊÌGC ¥¹¥Ê¥Ã¥×¥·¥ç¥Ã¥È·¿GC LazySweep TwoFinger Lisp2 Pa
Darts: Double ARray Trie System
Darts: Double-ARray Trie System はじめに Darts は, Double-Array [Aoe 1989]を構築するための シンプルな C++ Template Library です. Double-Array は Trie を表現するためのデータ構造です. ハッシュ木, デジタルトライ, パトリシア木, Suffix Array による擬似 Trieといった 他の Trie の実装に比べ高速に動作します. オリジナル の Double-Arrayは, 動的に key の追加削除を行えるような 枠組ですが, Darts は ソート済の辞書を一括してDouble-Array に変換することに機能を絞っています. ハッシュのような単純な辞書として使うことも可能ですが, 形態素解析器の辞書に必須の Common Prefix Search を非常に高速に行うことが
正規表現はお好き? - steps to phantasien
積んであった Beautiful Code を読んでみる. 第一章はカーニハンによる正規表現の話. 数十行のコードで簡単な正規表現を実装してみせる. パターン文字列を内部表現に変換せずマッチに使うぜ, コードも短い, ビューティホー! ...という主張なのだが, それはほんとにビューティホーなのか. UNIX 人の感覚にはついていけない. それにしても彼らは正規表現が好きだ. いつものその話ばかりしている. artu はいうまでもなく プログラミング作法 にも正規表現が出てきた. まったくこのマンネリめ. そう斜に構えつつ読み直してみると, 案外ラディカルな話も載っているのに気付く. 9.7 "オンザフライコンパイル" より: Ken Thompson はまさにこの方法によって 1967 年に IBM7094 上に正規表現を実装した. 彼のバージョンは, 正規表現に含まれる様々な処理を小さ
ConsistentHashing - コンシステント・ハッシュ法
ConsistentHashing - コンシステント・ハッシュ法 目次 この文書について コンシステント・ハッシュ法 実例 実装 用途 コンシステント・ハッシュ法 この文書について "Tom White's Blog: Consistent Hashing" の日本語訳です. http://weblogs.java.net/blog/tomwhite/archive/2007/11/consistent_hash.html 推敲歓迎: 誤訳, タイポ, 訳語の不統一, そのほか... 原文のライセンス: http://creativecommons.org/licenses/by-nc-sa/2.0/ 私は今までに何度かコンシステント・ハッシュ法にとりくんだことがある。 このアイデアをあらわした論文 ( David Karger らによる Consistent Hashing and R
[を] 転置インデックスによる検索システムを作ってみよう！
転置インデックスによる検索システムを作ってみよう！ 2007-11-26-5 [Algorithm][Programming] 転置インデックス[2007-06-17-6]による検索システムの実装は パフォーマンスを無視すれば意外と簡単です。 それを示すために Perl で簡単な検索システムを作ってみました。 検索方式は転置インデックス(Inverted Index)、 ランキングには TF-IDF[2005-10-12-1] を用いました。 検索対象ファイルは一行一記事で以下のフォーマットとします。 [記事ID][SPC][記事内容]\n 記事IDは数字、記事内容は UTF-8 の文字で構成されるものとします。 以下のようなサンプル test.txt を用意しました。 1 これはペンです 2 最近はどうですか？ 3 ペンギン大好き 4 こんにちは。いかがおすごしですか？ 5 ここ最近疲れ
![[を] 転置インデックスによる検索システムを作ってみよう！](https://cdn-ak-scissors.b.st-hatena.com/image/square/af37977ee866988286b95e74fff98500a190545c/height=288;version=1;width=512/https%3A%2F%2Fchalow.net%2Fimages%2Ftcl-logo-25.png){kind=logo}
ゲーマーでなくても仕組みぐらいは知っておきたいアルゴリズムx40
高校生の時、数学の先生がこう言いました。 ゲームなんて、開発者が作ったルールの上で遊ばれるだけだ。 と。 その時、ゲーマーな自分はこう思いました。 ゲーマーは、開発者が作ったルールの上で遊ばれたい。 と。 というわけで、普段何気なくプレイしているゲームには、どのようなルール（アルゴリズム）があるのか。それを知るために、いろいろなゲームのアルゴリズムなどを解析しているページへのリンク集を作りました。 ほとんどのゲームのアルゴリズムは正式に発表されていないので、ユーザーの手による逆解析だったり、大学の研究による真面目な考察だったりします。（リンク先には、一部アルゴリズムと呼べないものも含まれています） 各種ゲームのプログラム解析 ドラクエ、FF、ロマサガのプログラム解析 DQ調査報告書（リンク切れ） ドラクエの物理ダメージ計算式は本質的にどれも同じだが、細かい部分で微妙に違う RPG INST
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。
はてなのCAPTCHAは簡単に破れる
CAPTCHAをご存知でしょうか。 スパム防止のために歪んだ文字とかを入力させる、アレのことなのですが、 はてなのCAPTCHAの強度が妙に低く思えたので検証してみました。 CAPTCHAというのはいわゆる逆チューリングテストという奴で、 人間には可能だが機械には処理しにくいことをさせることで、 ロボットによる操作を弾こうというものです。 たとえば、Gmailのユーザ登録には以下のような画像が表示され、 表示されている文字を入力することが求められます。 CAPTCHAの強度 例えばスパムを送るために大量のGmailアカウントを得ようとしてる人がいたとします。 手作業でGmailを登録するのは骨が折れる。 そこでプログラムによる機械化を試みることになるわけです。 その際、障壁となるのがこのCAPTCHAなのです。 この画像から正解である文字列"vittac"を得ることは機械には難しい。 プロ
Amazon Dynamo – スケーラブルなハッシュテーブルWebサービス | 秋元@サイボウズラボ・プログラマー・ブログ
via O’Reilly Radar Amazonが来週ACMで話すというDynamoというサービスが面白そうだ。 Amazonのウェブサービスは、たとえばS3は「ファイルを置いて、取り出せる」だけだし、EC2はサーバ一台分だけ見ればただのVPSホスティングサービスだ。だけど、必要に応じて支払いを増やすと、好きなだけスケールさせられるし、不要になれば減らすのも簡単なことから、ネットサービスの運営者が固定費について悩まなくて済むようになるという点で便利だし、そんなサービスを提供するにはたいへんな技術力が必要だということはわかる。 Dynamoも同じで、「キーと値のセットを保存して、取り出せる」、とこれだけ。数が少なければスクリプト内の連想配列とシリアライズでも済みそうな機能だけれど、これを複数サーバに分散させて、たいへんな数のキーを突っ込んでも問題なく動作することを保証したサービス、となるら
sparsetable - steps to phantasien t(2007-09-07)
Matz日記 で紹介されている google-sparsehash を眺めてみた. ひさびさに Google 気分. :~/src/sparsehash-0.8 omo$ wc `find src/google/ -type f` 253 1348 10336 src/google//dense_hash_map 237 1309 9884 src/google//dense_hash_set 238 1244 9616 src/google//sparse_hash_map 223 1214 9245 src/google//sparse_hash_set 919 4776 37957 src/google//sparsehash/densehashtable.h 42 189 1187 src/google//sparsehash/sparseconfig.h 884 4642 371
カイ二乗値で単語間の関連の強さを調べる
カイ二乗値で単語間の関連の強さを調べる 2007-09-19-1 [Algorithm][Programming] カイ２乗値を使って単語間の関連度を調べる方法。 つまり、関連語を探すときに、χ二乗値を関連度として使う。 perl によるサンプルコード (chiword.pl)。昔、勉強がてら作ったコード。 #!/usr/bin/perl use strict; use warnings; my %cnt; my $pair_num; while (<>) { chomp; next if /^\s*$/; my @list = sort split(/,/, $_); for (my $i = 0; $i < @list; $i++) { for (my $j = $i + 1; $j < @list; $j++) { next if $list[$i] eq $list[$j]; $c
lucille development blog » Blog Archive » Xorshift RNGs
G. Marsaglia. Xorshift RNGs. Journal of Statistical Software, 8(14) :1 6, 2003 http://www.jstatsoft.org/v08/i14/xorshift.pdf George Marsaglia 氏により 2003 年に考案された、xor とシフトを使うだけの超高速な擬似乱数生成器(Random Number Generator, RNG)です。周期は 2^k-1(k = 32, 64, 96, 128, 160, 192)。ランダム性のテストにも十分合格するとのこと。たとえば、周期が 2^128-1 の場合のルーチンは以下のようになり、乱数値の計算部分はわずか 1 行である。 unsigned long xor128(){ static unsigned long x=123456789,y
リコメンドの裏側 : LINE Corporation ディレクターブログ
『livedoor グルメ』の根岸です。今日はlivedoor グルメにも実装されている「リコメンド（＝お勧め）」機能の話です。 マクドナルドの「ご一緒にポテトもいかがですか？」という店員の接客コメントは、誰もが知っている典型的な決まり文句ですよね。でも、誰にでもポテトをオススメするのは、芸がない。「俺はイモが嫌いなんだ！」っていう人だって絶対にいます。 インターネットでOne-to-Oneマーケティングの時代になると、ユーザーの動向を分析し、各ユーザーごとに興味を持ちそうな商品を予想して、お勧めするようになりました。たとえば、『Amazon』にログインして「マイストア」を選ぶと、それまでの購買履歴をもとにお勧め商品がリストアップされます。 僕のマイストアだと、 『笑う大天使（ミカエル）』 『ウォーターボーイズ』 『リンダリンダリンダ』 などのDVDが、リストアップされています。上記はいず
HowGoogleEarthReallyWorks - Google Earth の <ほんとの> 仕組み
HowGoogleEarthReallyWorks - Google Earth の <ほんとの> 仕組み 目次 この文書について Google Earth の <ほんとの> 仕組み パート1 終幕: 3D の仮想地球を描画する 基本 より良いフィルタリングを持ち込む さあ本題に入ろう Google Earth の <ほんとの> 仕組み この文書について RealityPrime > How Google Earth [Really] Works の日本語訳です。 推敲添削歓迎: 誤訳、タイポ、不統一、そのほか ... 有名サイト HowStuffWorks.com の記事 "How Google Earth Works" を読んだら, この記事が "それがどれだけスゴいか" や "その使い方" を書くだけで "それが(ほんとは)どんな仕組みで動いているのか" を説明していないこと
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
はてなブログ | 無料ブログを作成しよう
