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,
Text Editor: Data Structures – averylaird.com
The first step in building my text editor is to implement the core API. If you’re wondering why I want to do this, the original article is here. I researched several data types, and I tried to be language agnostic. I wanted my decision to not be influenced by any particular language, and first see if there was a “best way” out there, solely based on operations. Of course, a “best way” rarely exist
なぜ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とはその名の通り索引を意味します。特定のカラムの索引を作成しておくことで検索を高速化します。 (本の最後によみがな順で単語が並べられたりしています
テキストエディタ用バッファの各種データ構造とその評価 (2)
vector類をvector類で管理する組み合わせについて、考察とパフォーマンス測定を行う。 測定項目は以下の項目とする。 バッファ構築時間 シーケンシャルアクセス＋1文字削除時間・使用メモリ量 シーケンシャルアクセス＋1文字挿入時間・使用メモリ量 vector<shared_ptr<array<char>>> 最も基本的な組み合わせ。 STL には array が無いので、reserve であらかじめ領域を確保しサイズを固定にした vector<char> を代わりに用いる。 array のサイズは 32KB としてみる。array サイズを変えた場合の計測は余裕があれば行う。 文字データが array サイズ以上になった場合、可能なら前後の array に送る。そうでない場合は新たに array を作成する。 編集コストおよびブロック分割時コストは、ブロックサイズを B とすれば O(
テキストエディタ用バッファの各種データ構造とその評価
概要 テキストエディタのためのバッファの各種データ構造について述べ、 それらを筆者がC++で STLに準じたインタフェースを持つテンプレートクラスとして実装したものについて、 パフォーマンス（処理速度、使用メモリ量）計測を行った結果を報告する。 筆者が実際にテキストエディタを実装する場合にどのデータ構造がよいか、という視点で評価を行う。 目次： はじめに バッファに要求される機能・性能 バッファクラスのインタフェース パフォーマンス計測 各種データ構造 gap_vector<wchar_t> VS. list<wstring> gap_vector<wstring> 終わりに 参考文献 はじめに テキストエディタは、簡単に言うと、シーケンシャルなテキスト情報を保持し、ユーザの指示により内容を表示、修正するプログラムである。 上図のような構造はオブジェクト指向な設計と親和性が高い。 テキスト
Zipper - HaskellWiki
where @ marks a hole: the spot that the subtree appears in. This is the way we shall implement a tree with a focus. One way of expressing this context is as a path from the root of the tree to the hole (to which the required subtree will be attached). To reach our subtree, we needed to go down the left branch, and then down the right one. Note that the context is essentially a way of representing
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
Leftist Heap - 言語ゲーム
Chris Okasaki の Purely Functional Data Structures という本を買ってみました。これは、副作用を使わないでいろいろなデータ構造のアルゴリズムを実装するという大変面白い本で、これを読むと、副作用無しで○○が出来るわけがない！という時の○○がだいぶ減ると思います。 サンプルは Standard ML で書かれているのですが、良くわからないのでHaskell で書き直しながら読んでみます(巻末に Haskell での実装例が載ってるけど見ないふり)。 17 ページに Heap というコレクションが紹介されています。これは次の性質をもったコレクションです。 要素は大小関係を持つオブジェクト。 最小の要素だけを取り出す事が出来る。 ようするにあるリストをソートして最小の奴を取り出したいという場合、取り出す物が最小の物だけならばソートするより効率の良い方法
Leftist Heap - 道ばたに仰ぐ
Leftist Heapはヒープに加えて以下の制約が加わったLeftist Treeという構造を持つ。 rank(left child) >= rank(right child) rankとはright spineの長さ（右にだけ降りていったときの最後の接点までの長さ）のことである。 Leftist Treeは要素数nならば rank <= lg(節点数 + 1) という性質を持つ。各計算に置けるオーダーは insert: O(log n) delete_min: O(log n) find_min: O(1) merge: O(log n) (O(log(n1) + log(n2)): n1とn2の要素数をマージ) となる。
動的ダブル配列を使って 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はこれら
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://arxiv.org/pdf/1804.10112.pdf
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
IBM Research | QVM - The Quality Virtual Machine - Chameleon
Paul Christiano, Erik D. Demaine, and Shaunak Kishore: Lossless Fault-Tolerant Data Structures with Additive Overhead
Dynamic Double-Array Library
Treap - Wikipedia