Open-sourcing F14 for faster, more memory-efficient hash tables
Open-sourcing F14 for faster, more memory-efficient hash tables Hash tables provide a fast way to maintain a set of keys or map keys to values, even if the keys are objects, like strings. They are such a ubiquitous tool in computer science that even incremental improvements can have a large impact. The potential for optimization led to a proliferation of hash table implementations inside Facebook,
なぜBTreeがIndexに使われているのか - maru source
※この内容は個人的な考察なので、間違っている箇所もあると思います。そういう部分を見つけた際はぜひ教えて下さい。 RDBMSの検索を早くするためにIndexって使いますよね。例えばこんなテーブル CREATE TABLE user ( id INT UNSIGNED NOT NULL, name VARCHAR(255) NOT NULL, UNIQUE INDEX (id) ); idカラムにIndexを張っています。これはidでの検索を高速にするためです。ここでidカラムにIndexが貼っていない場合と比べると検索時間が大幅に変わってきてしまいます（特にレコードが多くなった時) ではなぜIndexを貼ると検索が早くなるんでしょう？？ Indexとはその名の通り索引を意味します。特定のカラムの索引を作成しておくことで検索を高速化します。 (本の最後によみがな順で単語が並べられたりしています
Zipper - HaskellWiki
The Zipper is an idiom that uses the idea of “context” to the means of manipulating locations in a data structure. Zipper monad is a monad which implements the zipper for binary trees. Sometimes you want to manipulate a location inside a data structure, rather than the data itself. For example, consider a simple binary tree type:
Data Structures for Text Sequences
Next: Introduction Data Structures for Text Sequences Charles Crowley University of New Mexico Abstract: The data structure used ot maintain the sequence of characters is an important part of a text editor. This paper investigates and evaluates the range of possible data structures for text sequences. The ADT interface to the text sequence component of a text editor is examined. Six common sequenc
動的ダブル配列を使って Wikipedia のテキスト処理を高速化 - ny23の日記
Wikipediaによるテキストマイニング入門など，Wikipedia 中の単語頻度を測るのが流行っているようだ．例えば，Hadoop を使ったり（Hadoop で Wikipedia のテキスト処理を900倍高速化 - 武蔵野日記），ハッシュを使ったり（Hadoopを使わずにWikipediaのテキスト処理を400倍高速化 - tsubosakaの日記Hadoopを使わずにWikipediaのテキスト処理を400倍高速化 - tsubosakaの日記）とか．情報系の人間なら普通はハッシュで十分と思うところ，折角なので動的ダブル配列を使って測ってみた．動的ダブル配列から保存された文字列を効率的に取り出すには，ノードリンクを実装して traverse () を再帰的に呼び出せば良い．今回は MSD radix sort 用に sibling のリンクを昇順にしたバージョン（僅かに追加速度が低
t.dvi
Purely Functional Data Structures Chris Okasaki September 1996 CMU-CS-96-177 School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213 Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy. Thesis Committee: Peter Lee, Chair Robert Harper Daniel Sleator Robert Tarjan, Princeton University Copyright c 1996 Chris Okasaki This research was sponso
ブロックアルゴリズムとB-Treeアルゴリズム
ext2とext3は、「ブロックアルゴリズム」を採用している。ブロックアルゴリズムとは、例えばディスクを4Kbytesなどの単位（ブロック）に分けて管理する方法である。ext2にジャーナリング機能を追加したものがext3である。ext2、ext3以外のファイルシステムで用いられているB-Treeとそのバリエーションは、バランス木（Balanced Tree）をベースとしたアルゴリズムである。 拡張機能としては、今回紹介する「動的iノード」と「エクステント」方式が挙げられる。「エクステント」は、ブロックアドレスの代わりに「論理セット」と呼ばれる「開始アドレス」「サイズ」「オフセット」を渡すことでアドレッシングを効率化する方式である。「動的iノード」はiノードを動的に付与する方法で、これまで存在していたiノード数の制約を解決するものとして期待されている。ReiserFSやJFS、XFSはこれら
R-tree Portal - R-trees and variants (in low-dimensional space)
When most couples contemplate retirement years, they might think of a fully-paid mortgage, endless sunny days of golf and fishing, … Continue reading “How 3 Couples Are Living Out Unique Retirement Dreams” → The challenge of living in a tiny home treehouse is achieving organizational functionality. Finding a way to make every single item in your house earn its keep while maintaining elegance and s
You’re Doing It Wrong - ACM Queue
The Bike Shed June 11, 2010 Volume 8, issue 6 PDF You're Doing It Wrong Think you've mastered the art of server performance? Think again. Poul-Henning Kamp Would you believe me if I claimed that an algorithm that has been on the books as "optimal" for 46 years, which has been analyzed in excruciating detail by geniuses like Knuth and taught in all computer science courses in the world, can be opti
yebo blog: クヌース教授は間違っていた
2010/06/15 クヌース教授は間違っていた Slashdotによれば、この数十年間、クヌース教授をはじめとするコンピュータ科学者が最適としてきたアルゴリズムを10倍高速にする方法をPoul-Henning Kamp (PHK) というハッカーが見付けたという。その論文タイトルは「You're Doing It Wrong (あなた達のやっている事は間違っている)」で、ACM Queueに掲載されている。別にクヌース教授の考えが間違っているわけではなく、アルゴリズム的には正しいが、実用レベルでは、OSには仮想メモリがあり、VMと干渉しないようにすれば簡単に高性能なシステムが作れる。従来の考え方はモダンな計算機を考慮に入れていないので、現実的には不適合を起こしている。具体的にはヒープにBツリーの要素を取り込んだBヒープというデータ構造を使うことで、バイナリヒープの10倍のパフォーマンスを
連想配列の進化 - DO++
キーに対して値を結びつける連想配列は多くのアプリケーションの肝であり、コンパクトかつ高速な処理が可能な連想配列を追い求め日夜研究が進められています。 特に非常に巨大な連想配列を高速に処理するというのが重要な課題となっています。例えば、音声認識・文字認識・機械翻訳などで使われている言語モデルでは、非常に大量のN個の単語列の情報（特に頻度）を格納することが重要になります。 この場合、キーが単語列であり、値が単語列のコーパス中での頻度に対応します。 例えばGoogle N-gram Corpusからは数十億種類ものN-gramのキーとその頻度などが取得できます。これらを主記憶上に格納し、それに関する情報（頻度や特徴情報）を操作することが必要になります。 そのほかにも大規模なデータを扱う問題の多くが巨大な連想配列を必要とします。 ここではこのような連想配列の中でも、キーの情報を格納することすら難し
DO++: 左傾赤黒木
漢字で書くと仰々しいが、赤黒木 (wikipedia) red-black tree (english wikipedia)という平衡二分木で最も多くつかわれているデータ構造の、改善版が出てたそうだ。 left-leaning red-black tree (pdf) 日本語に訳すと左傾赤黒木かな。簡単な漢字を並べている感じがしてしまう 赤黒木の詳細については、wikipediaなどをよんでもらうとして、これは更新時間が定数で更新箇所が局所的（これはマルチスレッドとかでロックする箇所をかなり細かい単位で、できるという強い利点もある）のだが、実装が結構面倒くさい。例えばC++ stl のmapとかの赤黒木の実装のstl_tree.h(google code search)は大変なことになっている（特にRb_tree_rebalance_for_eraseとか） 赤黒木というのは動的データ構造
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
w.l.o.g. ギャップバッファ
04:40 04/06/04 ピーステーブル PieceTable とも言う。文字列の Piece（小片）を繋げて、 一つの巨大な文書を表現する方式。 検索すると引っかかる文書のほとんどが AbiWord 関係なので、 このワープロソフトの主要な内部データ構造ということなのかな。 他に、MS-WordやOpenOffice.org関連の文書にも登場していて、 基本的に単なるテキストエディタよりは、文字に付加情報をくっつける系の 編集ソフトに使われる場面が今のところ多いみたいです。 余談ですがAbiWordは、綱渡り的にですがBeOS版の開発が続いている貴重なワープロソフトなのです。感謝感謝。 概要 ファイルを読み込んだとしましょう。ABCDEFG、という７文字のファイル。 とりあえず、７文字分のOrigという名前のバッファを用意して、そこに格納します。 それと別に、Addという名前の空のバ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Piece Chains | Catch22
Gap Buffers, or, Don't Get Tied Up With Ropes? : Good Math, Bad Math
Ropes: Twining Together Strings for Editors : Good Math, Bad Math
Treap - Wikipedia
Coalesced hashing - Wikipedia
Scalable Concurrent Hash Tables via Relativistic Programming / Linux Plumbers Conf: Developing the Kernel, Libraries and Utilities / September 23-25, 09 / Portland, OR