Google App Engineでランキングやページングを実現する - $koherent->diary
昨日一昨日、Google App Engine (GAE)に関する日本最大の勉強会（だと思う）appengine ja night #7 (ajn7)が行われました。 その中で『ランキング問題』が話題に上がりました。『ランキング問題』とは、何十万件もの点数のデータがあるときに、App Engine上で、「◯点は何位です」と高速に求めることは難しい、という問題です。（◯ページ目を表示、というページングもこれと同じ種類の問題になります。） ajn7では「上位でない限り正確な順位は必要ないのではないか」という話になりましたが、Skiplistを用いた検索アルゴリズムを使えば正確かつ高速に順位を求めることができるのではないかと思い、実装＆検証してみました。 ランキング（順位取得）のデモ 下記ページで順位取得のデモを動かしています。スコア（点数）を入力すると順位と取得にかかった時間が表示されます（時
Geohashのアルゴリズム
Photo by Ludovico Cera 前回、最後にGeohashのエンコード・デコード方法を解説、とか書いたのですが、私が書く前にyuroyoroさんがブログで解説していました。しっかり解説されているので、ぜひ、そちらをご覧ください。 Geohashのミソは、座標を2進数にして、それを交互に並べる所にあります。そしてそれをBASE32でエンコードすることで、座標を文字列にして表現しています。 BASE32は、5ビットで1文字なので、Geohashの長さが奇数の場合は、経度の方がビットが短くなります。 (例: 5文字の場合 全25ビット 緯度が13ビット、経度が12ビット) そのため、グリッドの大きさが、Geohashが奇数の場合は縦長、偶数の場合は横長になります。 ビット列から文字列へのエンコード方法に、BASE32を使っているのは大文字小文字を区別しないためだと思いますが、これを
PythonでLDAを実装してみる
Latent Dirichlet Allocationはテキストのような不連続データのための生成的確率モデル。入力はドキュメント。出力はドキュメントを特徴づける何か（tf-idfみたいなもん）。 基本的なアイディアは、あるドキュメントは潜在的ないくつかのトピックが混合していて、それぞれのトピックは語の分布で特徴づけられている、ということ。 論文[1]ではαとβというパラメータを用いてドキュメントが以下のように生成されると仮定している。 ドキュメントのトピックの分布θがディリクレ分布Dir(α)に基づいて選ばれる。 ドキュメントの語数N個になるまで以下を繰り返す。 トピックznが多項分布Mult(θ)に基づいて選ばれる。 単語wnが確率p(wn|zn,β)で選ばれる。 ただし、トピックzの数をk個、単語wの種類をV個とすると、パラメータαはk次元のベクトル、βはk x V次元の行列でβij=
PMVS2
PMVS is a multi-view stereo software that takes a set of images and camera parameters, then reconstructs 3D structure of an object or a scene visible in the images. Only rigid structure is reconstructed, in other words, the software automatically ignores non-rigid objects such as pedestrians in front of a building. The software outputs a set of oriented points instead of a polygonal (or a mesh) mo
Bundler - Structure from Motion for Unordered Image Collections
Bundler: Structure from Motion (SfM) for Unordered Image Collections Software written by Noah Snavely Download Bundler from the bundler_sfm repository on GitHub | What is Bundler? | Downloading Bundler | Documentation | References | Links | What is Bundler? Bundler is a structure-from-motion (SfM) system for unordered image collections (for instance, images from the Internet) written in C and C++.
コンピュータ囲碁プログラムが9段のプロ棋士と対戦、ハンデ付きで辛くも勝利 | スラド デベロッパー
8月10日、コンピュータ囲碁プログラムZenがプロ囲碁棋士の王メイエン九段と対戦し、19路盤で七子、9路盤でのコミ2.5/3.5目という大きなハンデが与えられていたものの、9路盤で見事に一勝をあげた。棋譜はネット囲碁対局サーバKGSで公開されている。 Zen は今年5月に行われたコンピュータオリンピアードで優勝した囲碁プログラムで、プログラマのyamato氏によって開発された。KGSにおいて2dのレーティング（碁会所で3～4段レベル）を得たこともある。 囲碁は手が広いことからチェスや将棋のような力ずくの探索ができず、つい最近まで最も強いプログラムでもアマチュア初段レベルだった。しかし棋力は確実に上がってきており、将棋と同じようにトップクラスの人間以外は勝つことができない時代に入りつつあるようだ。 マイコミジャーナルに王九段のコメント付きのレポートが掲載されているが、対戦は19路盤1回、9路
Rubyのハッシュテーブルの仕組みを徹底的に理解する - ザリガニが見ていた...。
ハッシュとは 一般的に理解すると抽象的で分かり難くなってしまうが、ハッシュとは、あるデータから、一定の計算をして求めた、目的に沿った数値、と思っている。それでは、どのような目的に利用されるのか？自分の知識で考えてみた。 暗号化 webアプリケーション等で、パスワードをDBに保存する時、生のパスワードをハッシュに変換して保存する。 Digest::SHA1.hexdigest等で求めたハッシュから、元のデータを復元するのが非常に困難という特性を利用する。 保存しているパスワードハッシュが、たとえ漏洩したとしても、不正利用を防止できる。 パスワードを照合するときも、ハッシュに変換して、保存しているパスワードハッシュと一致するかどうかで判断する。 同等の確認 長い文字列データを比較する時、全ての文字が等しいかチェックするのは非常に時間がかかる。 しかし、長い文字列データをハッシュに変換しておき、
GT Nitro: カーレーシング・ドラッグレーシングゲーム - Google Play のアプリ
GT Nitro: Car Game Drag Raceは、典型的なカーゲームではありません。これはスピード、パワー、スキル全開のカーレースゲームです。ブレーキは忘れて、これはドラッグレース、ベイビー！古典的なクラシックから未来的なビーストまで、最もクールで速い車とカーレースできます。スティックシフトをマスターし、ニトロを賢く使って競争を打ち破る必要があります。このカーレースゲームはそのリアルな物理学と素晴らしいグラフィックスであなたの心を爆発させます。これまでプレイしたことのないようなものです。 GT Nitroは、リフレックスとタイミングを試すカーレースゲームです。正しい瞬間にギアをシフトし、ガスを思い切り踏む必要があります。また、大物たちと競いつつ、車のチューニングとアップグレードも行わなければなりません。世界中で最高のドライバーと車とカーレースに挑むことになり、ドラッグレースの王冠
アルゴリズムと計算量
金庫破りと計算量膨張 n 桁の番号をもつ暗証ロックがあるとします。 2 桁であれば 00 〜 99 の 100 個の正解があるわけで、 0 番から順に入力していく解き方では、 最悪の場合は 100 手目に開きます。 99 が正解とは限らないので、平均的にはこれより早く解き終わります。 0 であるときの確率は 1/100 で、このときの手数は 1 手です。 1 であるときの確率は 1/100 で、このときの手数は 2 手です。 2 であるときの確率は 1/100 で、このときの手数は 3 手です。 3 であるときの確率は 1/100 で、このときの手数は 4 手です。 : 99 であるときの確率は 1/100 で、このときの手数は 100 手です。 つまり、平均手数は により、100 手目の約半分です。 ここでいう解き方をアルゴリズムといい、 問題を解くための手数 (てかず) のことを計
Algo 23 MSTP
The document discusses algorithms for finding minimum spanning trees in graphs. It describes Prim's and Kruskal's algorithms, which both run in O(ElogV) time where E is the number of edges and V is the number of vertices. It also mentions that Fibonacci heaps can be used to implement Prim's algorithm in O(E+VlogV) time.
Google File System(GFS)技術メモ — ありえるえりあ
* 参照した論文 + http://labs.google.com/papers/gfs-sosp2003.pdf * 特徴 + 安いPC(OSはGNU/Linux)で分散ファイルシステムを構築しています(*注1)。 + PCは壊れるという前提で設計しています(*注2)。このため、分散システムを構成するノードが壊れた時、データが失われないことと、自動で復旧できることに主眼を置いています。 + ファイルシステムを利用する側(アプリ)に、ある程度の想定を求めています。任意の利用ケースに対してそこそこのパフォーマンスを出す(=平均的に良い性能)のではなく、特定の利用ケースで性能を発揮できるように設計しています。 + 性能を発揮できる利用ケースは次のようなケースです。 ++ 主にサイズの大きいファイルを扱う(*注3)。 ++ ファイルへの書き込みは追記(append)が多い(ファイルの一部分を何度
MapReduce - naoyaのはてなダイアリー
"MapReduce" は Google のバックエンドで利用されている並列計算システムです。検索エンジンのインデックス作成をはじめとする、大規模な入力データに対するバッチ処理を想定して作られたシステムです。 MapReduce の面白いところは、map() と reduce() という二つの関数の組み合わせを定義するだけで、大規模データに対する様々な計算問題を解決することができる点です。 MapReduce の計算モデル map() にはその計算問題のデータとしての key-value ペアが次々に渡ってきます。map() では key-value 値のペアを異なる複数の key-value ペアに変換します。reduce() には、map() で作った key-value ペアを同一の key で束ねたものが順番に渡ってきます。その key-values ペアを任意の形式に変換すること
GoogleのMapReduceアルゴリズムをJavaで理解する
GoogleのMapReduceアルゴリズムをJavaで理解する：いま再注目の分散処理技術（前編）（1/2 ページ） 最近注目を浴びている分散処理技術「MapReduce」の利点をサンプルからアルゴリズムレベルで理解し、昔からあるJava関連の分散処理技術を見直す特集企画（編集部） いま注目の大規模分散処理アルゴリズム 最近、大規模分散処理が注目を浴びています。特に、「MapReduce」というアルゴリズムについて目にすることが多くなりました。Googleの膨大なサーバ処理で使われているということで、ここ数年の分散処理技術の中では特に注目を浴びているようです（参考「見えるグーグル、見えないグーグル」）。MapReduceアルゴリズムを使う利点とは、いったい何なのでしょうか。なぜ、いま注目を浴びているのでしょうか。 その詳細は「MapReduce : Simplified Data Proc
MySQLに対するDrizzleの答え #1 スレッド管理編 - mixi engineer blog
先日、Drizzleのスレッド管理を担うコアの一部分がモジュール化され、勉強がてらMySQLのスレッド管理の設計を調べてみました。その時のメモ（だから文が少し固いかも）と、Drizzleでの戦略を今回のエントリーで公開します。 最後のDrizzleでは？セクションまではプログラミングの教科書に載っている様な典型的なセオリを述べているだけなので、MySQLのインターナルに詳しい方は最後まで飛ばした方が良いかもしれません。 ちなみにソースはMySQL 5.1とMySQL 6.0のドキュメントです http://dev.mysql.com/doc/refman/6.0/en/connection-threads.html http://dev.mysql.com/doc/refman/5.1/en/connection-threads.html 現在の仕組みと制限 現在のMySQLでは新たなクラ
著名ソーシャルメディアが使っているアルゴリズムを大公開！ | Moz - SEOとインバウンドマーケティングの実践情報
“アルゴリズム”は、もっとも非人間的なものの代表だともいえる。ソーシャルメディアにとって、そのアルゴリズムが不可欠だというのは、実に皮肉めいている。 僕はこの間、グーグルがどうやってユーザーデータを集めているかについて書いた記事を掲載した（前編、後編）。今回は、著名なソーシャルメディアサイトが、ユーザーデータを活用する上でどのようにアルゴリズムを用いているのか、白日の下にさらそう。 ソーシャルメディアを成り立たせているのは人間の力だが、ユーザーが入力したデータを利用できる状態にする仕組みは、アルゴリズムによって作られている。現在活動している無数のソーシャルメディアサイトで実証済みのことだが、ユーザーの関与とアルゴリズムによる処理ルールの上手いバランスを見出すことは、とても難しくなりがちだ。これから紹介するアルゴリズムは、悪意のないユーザーと結びついて初めてうまくいくものだ。 人気ソーシャル
集合知と多量情報の可視化アルゴリズム本 Programming Collective Intelligence | fladdict
先日購入したBen FryのVisualizing Dataとあわせて買ってみた、Programming Collective Intelligence: Building Smart Web 2.0 Applications という本もかなりよさげ。 端的にいうとWEB2.0コンテンツ用に特化した、統計解析の理論とアルゴリズムの解説本。 いわゆる「これを買った人はこれを買ってます」を筆頭に、市場予測やスパム抽出、特徴データのグルーピングなど、集合知を抽出するアルゴリズムが大集合してる感じです。各アルゴリズムの原理の説明から、シンプルな自力実装までが書いてある感じっぽい。こういう系は数式だけあって理解不能か、動作がライブラリに隠蔽されてて理解不能で手が出せなかったけど、この本あれば大分理解できそう。以下、乗ってる内容メモ。 ・Amazon的なリコメンドのしくみ ・データのグループ化(クラス
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 Partial Mark and Sweep -Cycle Collection- Mostly Parallel GC train gc MostlyCopyingGC(Bartlett 1989) TreadmillGC(Barker 1992)
404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10
2007年11月26日18:15 カテゴリMathLightweight Languages プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10 ぎくっ あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな なぜぎくってしているかというと、実はすでにアルゴリズム本の発注を受けているからなのだ。いつまでも伏せておくのもなんなので、ここにえいやっとdiscloseしてしまうことにする。 アルゴリズム大募集! C&R研究所 - トップページ その下書きもかねて、そこでも紹介しないわけに行かないメジャーなアルゴリズムをとりあえず10個紹介しておくことにする。 ユークリッドの互除法(Euclidean algorithm) その昔(数百年ほど前)は「アルゴリズム」といえば、「手順一般」を指すのではなく、この「互除法
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Sketch2Photo: Internet Image Montage
IBM Developer
