開発メモ: IndexDB: 転置インデックスのためのDB
大震災の時分に何だが、Kyoto Cabinetベースで検索エンジンの核となる転置インデックスを作るのに適したDBを実装したという話。 転置インデックスとappend操作 多くの検索エンジンの核となる転置インデックスとは、検索語に一致する表現がどこに出てきたかという位置情報のリストを保持するものであり、検索語をキーとして位置情報リストを値とする連想配列である（転置インデックスを使わない検索エンジンもあるが）。この位置情報リストをposting listとか呼んだりするらしい。転置インデックスにもいくつか流儀があり、検索語をどのように切り分けるかで単語（分かち書き）方式とか文字N-gram方式とか呼ばれるものがあったりするが、いずれにせよ、小さいキーと、非常にでかい値を保持する連想配列を作ることには変わりない。 で、素朴に転置インデックスを作ろうとすると、検索対象の文書を解析しながら、得られ
インテル・AMDのCPUアーキテクトが明かす： GNU grep が速い理由 - karasuyamatenguの日記
GNU grepの元祖作者がFreeBSDハッカーをschoolしている。 http://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html FreeBSD対GNU grepのパフォーマンスを議論していると思われるとことに「俺はgrepの初代作者だ」と名乗って現われた男がいる。 履歴書(http://duckytech.com/resume.pdf)を見ると、GNU coreutilsに貢献した後、インテルやAMDでCPUアーキテクトを勤めている男だ。これは話を聞いた方がよさそうだ。 FreeBSDユーザでもある彼はリストを観閲していたらたまたまGNU対BSDのgrep論争に当ってしまったようだ。BSDのリストにGNU grepの秘密を解く。 技1： 全ての入力バイトを見ないから速い 技2： 見るバイトに関
ridiculous_fish » Blog Archive » The Treacherous Optimization
Old age and treachery will beat youth and skill every time. "I’m going to beat grep by thirty percent!" I confidently crow to anyone who would listen, those foolish enough to enter my office. And my girlfriend too, who’s contractually obligated to pay attention to everything I say. See, I was working on Hex Fiend, and searching was dog slow. But Hex Fiend is supposed to be fast, and I want blazing
ノートPCのTPMを/dev/randomの乱数生成器として使う - このブログはURLが変更になりました
前回のGnukでGPG鍵を生成する際に、/dev/randomからエントロピーを取り出すのが遅い問題の対策を調べていたところ、TPM(Trusted Platform Module)を乱数生成器として使えることが分かったので試してみた。 TPMとは WikipediaのTrusted Platform Moduleより一部抜粋 概要 RSA暗号演算やSHA-1ハッシュ演算といった機能を有しており、チップ内で暗号化・復号、デジタル署名の生成・検証、プラットフォームの完全性検証を行うことができる。また、TPMの内部でRSAの鍵ペア(公開鍵と秘密鍵)を生成することができる。 TPMの仕様はTCG (= Trusted Computing Group)という国際的な業界団体で策定されており、最新のバージョンは1.2である。 ノートPCだけではなく、デスクトップPCにもTPMは搭載されている。Win
Arora's Task Stealing Deque
作成日：2005.11.27 目次 前置き データ構造 操作 擬似コード 動作 問題点 参考文献 脚注 1. 前置き マルチプロセッサ上で行う並列処理を行うプログラムが、 仕事を均等に N 分割できるものは稀だ。 プログラムの処理コストの最大値や平均値を見積もることができても、 実際の処理時間や消費メモリはプログラムの実行内容によって大きく変わっていく。 そのため各プロセッサに割り当てる負荷(ロード)が均一になるように 負荷分散を行うことが重要になる。 負荷分散を行うためには、 プログラムをある程度の粒度に分割し、 プロセッサ間で担当をやり取りできるようにする。 とりあえずプログラムを分割したものをタスクと呼ぶことにしよう。 タスクをやり取りする方法は、 大雑把に言って三つある。 マネージャーがいて、どのプロセッサがどのタスクを行うか制御する。 暇なプロセッサが、タスクを多く抱えたプロセッ
A few key problems in Redis persistence
Today I read this article about Redis with interest. It's a legitimate point of view on databases, you may agree or not, but the author has a solid idea about what he is looking for and about the database scene. I don't agree with everything, but there is something I especially like about this article: it actually identifies very well what I think are actually the strength and deficiencies of Redi
Designing algorithms for Map Reduce
Since the emerging of Hadoop implementation, I have been trying to morph existing algorithms from various areas into the map/reduce model. The result is pretty encouraging and I've found Map/Reduce is applicable in a wide spectrum of application scenarios. So I want to write down my findings but then found the scope is too broad and also I haven't spent enough time to explore different problem dom
本当に1.5倍のほうがメモリ効率がよいのか - inamori’s diary
C++のstd::vectorにpush_backしていくと、ある領域を確保して、それを超えそうになったらまたある程度ゆとりのある領域を確保するという機構になっています。 ２倍だけじゃない - d.y.d. にまとめてありますが、std::vectorや類似するコンテナは2倍ずつ領域を大きくしていくのかと思いきや、1.5倍というのも多いんですね。実際にVC10 beta2で動かしてみると、 #include <iostream> #include <vector> int main() { std::vector<int> v; for(int i = 0; i < 100; i++) { const std::vector<int>::size_type old_cap = v.capacity(); v.push_back(i); const std::vector<int>::siz
d.y.d. 2倍だけじゃない
10:01 10/07/20 それでも２倍だ 先日のvectorの伸長度合いの記事に関して 本当に1.5倍のほうがメモリ効率がよいのか という反応をいただきました。とても興味深い。みんな読みましょう。 自分の理解メモ： 「再利用ができるから嬉しい」等の議論をするなら、 今までに確保したメモリ (1 + r^1 + ... + r^k) のうち、 有効に使えてるメモリ r^{k-1} (バッファ拡大直後) や r^k (次のバッファ拡大直前) の割合で評価してみようじゃないかという。 まず簡単のために再利用をしない場合を考えると、この割合はそれぞれ (r-1)/r^2、 (r-1)/r になります（途中計算略）。 この利用率が最悪になる瞬間 (r-1)/r^2 を最善にしよう、 という一つの指標で考えてみると、式を微分なりなんなりしてみると r = 2 で最大(25%)となることがわかります
TLE '10 - d.y.d.
09:37 10/02/28 PrezzProcezz TLEのPREP は、私のコードは縮める前がこんな感じで、 // println(X) #define p(X) X _Pragma("") // H = 百の位が… (a: 3で割って0余る場合、 b: 1余る、 c: ２余る) #define a(H) d(H 0) e(H 1) f(H 2) d(H 3) e(H 4) f(H 5) d(H 6) e(H 7) f(H 8) d(H 9) #define b(H) e(H 0) f(H 1) d(H 2) e(H 3) f(H 4) d(H 5) e(H 6) f(H 7) d(H 8) e(H 9) #define c(H) f(H 0) d(H 1) e(H 2) f(H 3) d(H 4) e(H 5) f(H 6) d(H 7) e(H 8) f(H 9) // HJ =
L'eclat des jours(2009-11-10)
_ でっかなバッファを避ける? Aleviating Memory Fragmentation in Mono コンパクティングしなければ、いやでもフラグメントがどかどかできる。 するとでっかなバッファを取ろうとすると新しいページの割り当てが必要となりプロセスが肥大する。 だからでっかなバッファを要求すんな。細切れ継ぎ合わせメモリーストリームを使え。 と読んだ。 細切れ継ぎ合わせ方式だと実際のバッファへのポインタ分だけ余分なメモリを食うわけだし、次の細切れへの移動にオーバーヘッドがかかるわけだが、それを補ってあまりある恩恵が得られればOK。 （ここで、「さっそく試してみる」といかないところがだめなところだ）
■ - kurimura’s diary
stack_ni_yasasii_free_tree treeを回転させて回転しきれなくなったら削除だと割と簡単にかける気がする。 void stack_ni_yasasii_free_tree(tree* t) { while(t){ tree*tmp; while(t->r){ tmp = t->r; t->r = tmp->l; tmp->l = t; t = tmp; } tmp = t; t = t->l; wrap_free(tmp); } }
個人用電卓のプログラミング
今年の3月頃にこのブログに投稿した, 電卓HHCのプログラミングの話題の続きである. この電卓のシミュレータには, スタックが2個あり, その間でデータが受け渡せる. このスタックを, 両方へ延びるテープ, 命令UとNをヘッドの右, 左への移動と思うと, 2スタックモデルはTuring Machineに非常によく似てくる. そこで今回は, Turing Machineをシミュレートしてみた. Turingの1936年の有名な論文の始めの方に, テープに0010110111011110...を書く例がある. つまり, 0の列の間に1を0個, 1個, 2個, 3個, ...と挟むのである. この論文のテープは, 計算結果を書くますと, 作業用の記号を書くますが, 交互に並んでいる. 従って, 上の出力も,テープ全体で見ると, bを空白のますとして, 0b0b1b0b1b1b0b1b1b1b0b
転置インデックスを実装しよう - mixi engineer blog
相対性理論のボーカルが頭から離れないmikioです。熱いわっふるの声に応えて今回はTokyo Cabinetのテーブルデータベースにおける検索機能の実装について語ってみたいと思います。とても長いのですが、最後まで読んだあかつきには、自分でも全文検索エンジンを作れると思っていただければ嬉しいです。 デモ モチベーションをあげていただくために、100行のソースコードで検索UIのデモを作ってみました。Java 6の日本語文書を対象としているので、「stringbuffer」とか「コンパイル」とか「倍精度浮動小数」とかそれっぽい用語で検索してみてください。 インデックスがちゃんとできていれば、たった100行で某検索エンジン風味の検索機能をあなたのデータを対象にして動かすことができます。ソースコードはこちら（テンプレートはこちら）です。 でも、今回はUIの話ではないのです。ものすごく地味に、全文検索
コンピューターに絵画を描かせる | fladdict
コンピューターによる写真の絵画変換ってのは、photoshopにもついてるんだけど、あれってダサい。 なんかヌタッとしてて、全体がのっぺりしている・・・というか、主題と背景とかそういうのが考慮されずに一律に変換されているのがキモイ。 で、最近ごぞんじのように、写真のフラクタル分割をずっと趣味で研究してたんだけど、ようやく自分が納得できる精度でフラクタル分割する方法を思いついた。↓の画像がその処理結果なんだけど、だいぶいい感じに分割できてると思う。 アルゴリズムはQuasimondoのFITCの発表を聞いてる最中に思いついたもの。 まず画面のピクセルを走査し輝度の標準偏差を取る。標準偏差が閾値以上の場合、その領域は十分に複雑であると判断され、分割される。あとはそれを繰り返して二分木あるいは四分木で分割していけばいい。輝度を基準にするってのはJPEGの圧縮からアイデアを頂きました。 ちなみにQ
スペル修正プログラムはどう書くか
Peter Norvig / 青木靖 訳 先週、2人の友人(ディーンとビル)がそれぞれ別個にGoogleが極めて早く正確にスペル修正できるのには驚くばかりだと私に言った。たとえば speling のような語でGoogleを検索すると、0.1秒くらいで答えが返ってきて、もしかして: spelling じゃないかと言ってくる(YahooやMicrosoftのものにも同様の機能がある)。ディーンとビルが高い実績を持ったエンジニアであり数学者であることを思えば、スペル修正のような統計的言語処理についてもっと知っていて良さそうなものなのにと私は驚いた。しかし彼らは知らなかった。よく考えてみれば、 別に彼らが知っているべき理由はないのだった。 間違っていたのは彼らの知識ではなく、私の仮定の方だ。 このことについてちゃんとした説明を書いておけば、彼らばかりでなく多くの人に有益かもしれない。Googleの
Jeffrey Dean
I joined Google in mid-1999, and I'm currently Google's Chief Scientist, focusing on AI advances for Google DeepMind and Google Research. My areas of focus include machine learning and AI and applications of AI to problems that help billions of people in societally beneficial ways. I have a broad variety of interests, including machine learning, large-scale distributed systems, computer systems pe
Google WSDM'09講演翻訳：大規模な情報検索システム構築における課題（１） - llameradaの日記
GoogleのFellowであるJeffrey Dean氏のWSDM'09における講演"Challenges in Building Large-Scale Information Retrieval Systems"のスライドを翻訳してみました。Googleの検索システムの10年間の進化の軌跡が紹介されており、興味深い話が満載です。個人的にはディスクの外周部と内周部を使い分けている話がツボでした。なお、イタリック体で一部解説・感想をいれています。翻訳は素人なので詳しくは元の資料を参照してください。 スライドの入手元：Jeffrey Dean – Google AI 検索システムに取り組む理由 チャレンジングなサイエンスとエンジリアニングのブレンド 多くの魅力的な未解決な問題が存在する。 CS（コンピュータサイエンス）の多数の領域にまたがる。 アーキテクチャ、分散システム、アルゴリズム、圧
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
コードを愛でる - コードを愛でる
Hack the Cell 2009 結果発表