Google App Engineでランキングやページングを実現する - $koherent->diary
昨日一昨日、Google App Engine (GAE)に関する日本最大の勉強会（だと思う）appengine ja night #7 (ajn7)が行われました。 その中で『ランキング問題』が話題に上がりました。『ランキング問題』とは、何十万件もの点数のデータがあるときに、App Engine上で、「◯点は何位です」と高速に求めることは難しい、という問題です。（◯ページ目を表示、というページングもこれと同じ種類の問題になります。） ajn7では「上位でない限り正確な順位は必要ないのではないか」という話になりましたが、Skiplistを用いた検索アルゴリズムを使えば正確かつ高速に順位を求めることができるのではないかと思い、実装＆検証してみました。 ランキング（順位取得）のデモ 下記ページで順位取得のデモを動かしています。スコア（点数）を入力すると順位と取得にかかった時間が表示されます（時
ネットワークプログラムのI/O戦略 - sdyuki-devel
図解求む。 以下「プロトコル処理」と「メッセージ処理」を分けて扱っているが、この差が顕著に出るのは全文検索エンジンや非同期ジョブサーバーなど、小さなメッセージで重い処理をするタイプ。ストリーム指向のプロトコルの場合は「プロトコル処理」を「ストリーム処理」に置き換えるといいかもしれない。 シングルスレッド･イベント駆動 コネクションN：スレッド１。epoll/kqueue/select を１つ使ってイベントループを作る。 マルチコアCPUでスケールしないので、サーバーでは今時このモデルは流行らない。 クライアントで非同期なメッセージングをやりたい場合はこのモデルを使える： サーバーにメッセージを送信 イベントハンドラを登録；このときイベントハンドラのポインタを取っておく イベントハンドラ->フラグ がONになるまでイベントループを回す イベントハンドラ->結果 を返す １コネクション１スレッ
非同期プロトコルのクライアント - sdyuki-devel
非同期プロトコルとは、サーバーから返ってくる応答が、必ずしも要求した順番通りに返ってこないプロトコル（ソース無し。オレオレ定義）。 順不同で返ってくる応答と要求を対応づけるのはクライアントの仕事で、典型的には要求の中にシーケンス番号を入れておき、サーバーは要求と同じシーケンス番号を応答の中にも含める。 例：MessagePack-RPC 非同期プロトコルの特徴： イベント駆動型のサーバーの場合、サーバーの実装が簡単になる 同期プロトコルだと順番を揃えてから返さないといけない。サーバーの実装が（要求１つに対してスレッドを割り当てて処理するのではなく）ソケット１つに対してスレッドを割り当てて処理する方式だとあまり関係なくて、特に実装は簡単にならない。 処理が重い要求と軽い要求を続けて送っても、重い要求に詰まって後の応答が返ってこなくなることが無い 同期プロトコルだと、応答を送り返すにはその前の
Bayesian Setsによる関連文書検索システムStupa - mixi engineer blog
都会よりも田舎が好きなfujisawaです。Bayesian Setsというアルゴリズムを使って、関連する文書を高速・高精度に検索できるシステムを作成しましたので、そのご紹介をさせていただきます。 Bayesian Setsとは Bayesian Setsはいくつかアイテムを入力すると、それを補完するようなアイテムを返してくれるアルゴリズムです。原著論文の先頭に"Inspired by Google Sets"と書かれているように、Google Setsを参考にして作成されています。実際にどのような出力が得られるか、Google Setsに以下の表のクエリを検索して試してみますと、 クエリ 出力 apple, banana chocolate, strawberry, vanilla, cherry, ... apple, macintosh software, windows, mac,
シムシティーの仕組み
シムシティーを作り始めていちばん最初に考えたのは、街を一種の生き物のように表現できないかってことだった。 僕が街についてどう考えているかはすでに説明したけど、大事なのは街を構成する建物とか道路じゃなくって、そこでどんな活動が行なわれているかってことだと思うんだ。道路を車が走り、電車が動き、人々が動き回り、常に要素が変化し続ける“動きのある”システム。街を表現する方法っていうと誰でも地図を思い浮かべると思うけど、僕は動きがない地図じゃなくって、たとえば飛行機から眺めた街、動きのある世界をディスプレイに表現しようって考えた。それこそが僕の考える街の姿だからね。 それともう一つ考えたことは、プレイヤーに伝える情報をできるだけわかりやすく、それも“面白い”って思えるような形で表現しようってことだった。シミュレーション・ソフトっていうとたいてい数値や図表がたくさん出てくるけれど、数字が並んでいるのを
クラスタリングの定番アルゴリズム「K-means法」をビジュアライズしてみた - てっく煮ブログ
集合知プログラミング を読んでいたら、K-means 法（K平均法）の説明が出てきました。K-means 法はクラスタリングを行うための定番のアルゴリズムらしいです。存在は知っていたんだけどいまいちピンときていなかったので、動作を理解するためにサンプルを作ってみました。クリックすると１ステップずつ動かすことができます。クラスタの数や点の数を変更して、RESET を押すと好きなパラメータで試すことができます。こうやって１ステップずつ確認しながら動かしてみると、意外に単純な仕組みなのが実感できました。K-means 法とはK平均法 - Wikipedia に詳しく書いてあるけど、もうすこしザックリと書くとこんなイメージになります。各点にランダムにクラスタを割り当てるクラスタの重心を計算する。点のクラスタを、一番近い重心のクラスタに変更する変化がなければ終了。変化がある限りは 2. に戻る。これ
ベイズを学びたい人におすすめのサイト - download_takeshi’s diary
ベイジアンフィルタとかベイズ理論とかを勉強するにあたって、最初はなんだかよくわからないと思うので、 そんな人にお勧めのサイトを書き残しておきます。 @IT スパム対策の基本技術解説（前編）綱引きに蛇口当てゲーム？！楽しく学ぶベイズフィルターの仕組み http://www.atmarkit.co.jp/fsecurity/special/107bayes/bayes01.html いくつかの絵でわかりやすく解説してあります。 自分がしるかぎり、最もわかりやすく親切に解説してる記事です。数学とかさっぱりわからない人はまずここから読み始めるといいでしょう。 茨城大学情報工学科の教授のページから http://jubilo.cis.ibaraki.ac.jp/~isemba/KAKURITU/221.pdf PDFですが、これもわかりやすくまとまってます。 初心者でも理解しやすいし例題がいくつかあ
Aho Corasick 法 - naoyaのはてなダイアリー
適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」「店」という単語が含まれていた場合には、これらの単語(と出現位置)が入力に対しての出力になります。 この類の処理は、任意の開始位置から部分一致する辞書中のキーワードをすべて取り出す処理、ということで「共通接頭辞検索 (Common Prefix Search)」などと呼ばれるそうです。形態素解析、Wikipedia やはてなキーワードのキーワードリンク処理などが代表的な応用例です。 Aho Corasick 法 任意のテキストから辞書に含まれるキーワードをすべて抽出するという処理の実現方法は色々とあります。Aho Corasick 法はその方法のひと
新はてなブックマークでも使われてるComplement Naive Bayesを解説するよ - 射撃しつつ前転 改
新はてブ正式リリース記念ということで。もうリリースから何週間も経っちゃったけど。 新はてなブックマークではブックマークエントリをカテゴリへと自動で分類しているが、このカテゴリ分類に使われているアルゴリズムはComplement Naive Bayesらしい。今日はこのアルゴリズムについて紹介してみる。 Complement Naive Bayesは2003年のICMLでJ. Rennieらが提案した手法である。ICMLというのは、機械学習に関する（たぶん）最難関の学会で、採択率はここ数年は30%を切っている。2003は119/371で、32.1%の採択率だったようだ。 Complement Naive Bayesの位置づけは 実装が簡単 学習時間が短い 性能もそこそこよい という感じで、2003年段階にあっても、絶対的な性能ではSVMに負けていた。しかし、学習が早いというのは実アプリケーシ
HITS, 主成分分析, SVD - naoyaのはてなダイアリー
ウェブグラフのリンク解析によるページの評価と言えば PageRank が著名ですが、もうひとつ Jon Kleinberg による HITS (Hyperlink-induced topic search)も有名です。最初の論文 Authoritative Sources in a Hyperlinked Environment は 1999年です。IIR の 21章で、この PageRank と HITS についての解説がありました。 HITS HITS はウェブページの評価に二つの軸を用います。一つが authority スコア、もう一つが hub スコアです。 例えば「Perl の情報が欲しい」という検索要求に対しては CPAN や 開発者である Larry Wall のホームページなどが重要度の高いページかと思います。これらのページは「Perl に関して信頼できる情報源」ということ
人工無能の作り方
書いた人 INA 人工無能とは？ 人間っぽく話すプログラムのこと。会話を理解しているというよりは、なんかそれっぽいことを話すだけのものが多い。 今回は「日本語のようなものを話す人工無能」を作ってみたので、その簡単な仕組みと工夫した点について少し書いてみることにする。 動機 うちのサークルのメンバーがよく集まってるチャット。とてもマニアックな どうしようもない 会話が繰り広げられているわけだが、ちょっと物足りない。 そうだ！ 萌キャラがいないじゃないか！ 「ないなら作ればいいじゃない？」 材料 MeCab 形態素解析エンジン 難しいことは知らなくても問題ない。 「私は変な人ではない」 ↓ 私 名詞,代名詞,一般,*,*,*,私,ワタシ,ワタシ は 助詞,係助詞,*,*,*,*,は,ハ,ワ 変 名詞,形容動詞語幹,*,*,*,*,変,ヘン,ヘン な 助動詞,*,*,*,特殊・ダ,体言接続,だ,
ソーシャルブックマークに関する研究 : 研究開発
総合研究大学院大学 複合科学研究科 情報学専攻 卒 博士（情報学） 自然言語処理や機械学習、データ分析に関する研究内容とwebシステムの開発と運用について書いています。 シリコンバレーベンチャーみたいに深い技術の事業化をしたいと思っています。 ご興味ある方はご連絡ください。 ブックマークをメタデータとして使うということは当り前ですが共通です。 ・リコメンデーション ・情報検索のimprovement ・その他マイニング などが普通です。 特にリコメンデーションが人気すぎますので、 これ以外の利用法を考え出せれば..... "普通"は del.icio.us を用います。 国内だと、 ほとんど b.hatena.ne.jp を用います この研究では Folksonomy という言葉を覚えておいてください 言及されている場合が多いです。 後は、 一般的な（外部からの）タグ付けがなされているデ
第 7 回アルゴリズムイントロダクション輪講会資料: Days on the Moon
すでにニュースでも伝えられている通り、12 月 1 日に第 7 回アルゴリズムイントロダクション輪講会がありました。今回の担当は私だったので、その発表資料を公開します。 中央値と順序統計量 (その 1) 予定 順序統計量とは 選択問題とは 最小値と最大値 平均線形時間選択アルゴリズム 中央値と順序統計量 (その 2) 最悪線形時間選択アルゴリズム 3 つずつのグループに分割した場合 7 つずつのグループに分割した場合 参考文献 中央値と順序統計量 (補足) 4 つずつのグループに分割した場合 6 つずつのグループに分割した場合 Lazy-Select Randomized-Partition スタッフロール 「どうせ後から Web で公開するんだから、PDF とか見るのに手間がかかるものは使ってられないよね。やっぱ時代は XML 複合文書でしょ!」と、数式を表現するのに MathML を使
著名ソーシャルメディアが使っているアルゴリズムを大公開！ | Moz - SEOとインバウンドマーケティングの実践情報
“アルゴリズム”は、もっとも非人間的なものの代表だともいえる。ソーシャルメディアにとって、そのアルゴリズムが不可欠だというのは、実に皮肉めいている。 僕はこの間、グーグルがどうやってユーザーデータを集めているかについて書いた記事を掲載した（前編、後編）。今回は、著名なソーシャルメディアサイトが、ユーザーデータを活用する上でどのようにアルゴリズムを用いているのか、白日の下にさらそう。 ソーシャルメディアを成り立たせているのは人間の力だが、ユーザーが入力したデータを利用できる状態にする仕組みは、アルゴリズムによって作られている。現在活動している無数のソーシャルメディアサイトで実証済みのことだが、ユーザーの関与とアルゴリズムによる処理ルールの上手いバランスを見出すことは、とても難しくなりがちだ。これから紹介するアルゴリズムは、悪意のないユーザーと結びついて初めてうまくいくものだ。 人気ソーシャル
Animated Sorting Algorithms
Discussion These pages show 8 different sorting algorithms on 4 different initial conditions. These visualizations are intended to: Show how each algorithm operates. Show that there is no best sorting algorithm. Show the advantages and disadvantages of each algorithm. Show that worse-case asymptotic behavior is not the deciding factor in choosing an algorithm. Show that the initial condition (inp
TagGridのデータ配置アルゴリズムの簡単な解説 - llameradaの日記
はじめに TagGridでは16000毎のFlickrの写真を、写真のタグにしたがって格子状に配置しています。この配置アルゴリズムについて簡単に説明したいと思います。 基本的なアイデア まず、入力となるのはN個のタグ付きデータとします。また、K種類のタグがあるとします。 TagGridでは、このN個のデータとK種類のタグがそれぞれ平面上に配置されるとします。 データだけでなく、タグも2次元平面上に配置するのが大事な点です。 基本的な考え方としては、あるデータのタグが例えばseaとsunの場合、このデータの位置がseaタグと sunタグの近くになるようにデータとタグを配置します。データは複数のタグを持つので、一番良い配置方法というのは簡単には決定できません。そこで、なるだけ良さそうな配置を求めてみます。 フォーマルな問題定義 基本的なアイデアを、もう少しフォーマルに定義します。 n番目のデー
はてなブログ | 無料ブログを作成しよう
突然の出会い: プラウベルマキナについて 日本がバブル経済に突き進み始めた頃に3,500台ほど作られ、数年後にひっそり生産が閉じられた超短命製品プラウベルマキナW67とご縁があった。 その生産数の少なさからまともな個体と出会うことがなかったのだけど、使わないデジタル機材一式を売りに行った帰りにガラス…
PHPにおけるグラフ描画とアルゴリズム：CodeZine
はじめに本稿で扱うグラフ 「グラフ」という語を広辞苑（第5版）で引くと、載っている意味は次の3つです。互いに連関する二つまたは二つ以上の量の間の関係を表す図形。例えば関数fに対し、xがfの定義域を動くときの点（x， f（x))の軌跡をfのグラフという。またx、yに関する方程式をみたす点（x， y）の軌跡をその方程式のグラフという。全体に対する割合を示したり、数量の大小を比較したりするための図表。円グラフ・棒グラフなど。写真を主にした雑誌。画報。 しかし、本稿で扱うグラフは、この3つのいずれでもありません。国語辞典には載っていないことが多いようですが、計算機科学や数学において「グラフ」と言えば、図のような、点（pointあるいはvertex、node）と点を結ぶ線（lineあるいはarc、edge）の集合を指します。 グラフはプログラミングにおいてよく用いられる基本的なデータ構造の一つです
アルゴリズムからプログラムを学ぼう！
PHPのための基礎－ソフトウェア工学としてのPHPプログラミング PHPの基礎ではなく、PHP「のため」の基礎としたのには理由があります。連載「PHP開発プロジェクトの夢と現実（http://www.thinkit.co.jp/free/article/0705/5/1/）」で、PHPは習得しやすいプログラミング言語であることを書きました。また、そのことによる弊害も述べました。 今回の連載では「言語としての」PHPについてはある程度わかっているのだけれど、いまひとつプログラミングに自信が持てないという、初級または中級の方々を主な対象として、プログラミングの基礎を解説します。本連載は、「ソート」に焦点をあててその考え方を具体的に説明していきましょう。 改めてソートとは ソート（sort）とは、ものをある規則に合うように並び替えることです。ここではソートアルゴリズムを考えて、ソートを行う関数を
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
検索エンジンのランキング計算方法 : 研究開発