sparsetable - steps to phantasien t(2007-09-07)
Matz日記 で紹介されている google-sparsehash を眺めてみた. ひさびさに Google 気分. :~/src/sparsehash-0.8 omo$ wc `find src/google/ -type f` 253 1348 10336 src/google//dense_hash_map 237 1309 9884 src/google//dense_hash_set 238 1244 9616 src/google//sparse_hash_map 223 1214 9245 src/google//sparse_hash_set 919 4776 37957 src/google//sparsehash/densehashtable.h 42 189 1187 src/google//sparsehash/sparseconfig.h 884 4642 371
Double Arrayの非常に効率的な圧縮 - 射撃しつつ前転 改
「ダブル配列におけるキャッシュの効率化」という論文を見付けた。FIT2006というフォーラムで発表されたものらしい。これはすごい。目から鱗が落ちた。なんかリンク張って良いものか迷うので、とりあえずはリンクしない。 この論文に書いてあることは2つあって、ひとつは配列サイズの削減で、もうひとつはできるだけキャッシュミスを減らすための方法である。配列サイズを削減するための方法がすごい。これまで誰も考え付かなかったのか、それとも考え付いたけどやらなかったのか？ まず、checkの要素サイズは1byteで十分である。なぜなら、遷移元のインデックスがわからなくても、遷移に使ったキーの値がわかれば十分なので。これでDoubleArray全体のサイズを5/8に減らせる。また、普通、1GBのDouble Arrayを作成したりすることは無い（せいぜい100MB程度だろう）ので、Baseにも4byteも割り当
横着プログラミング 第9回: sary: Suffix Array のライブラリとツール
最終更新日: 2002-12-18 (公開日: 2002-12-18) Unix Magazine 誌に 2002年1月号から 2003年2月号にかけて連載し ていた記事の元の原稿です。 私にフローチャートだけを見せて、テーブルは見せないとしたら、 私はずっと煙に巻かれたままになるだろう。逆にテーブルが見せて もらえるなら、フローチャートはたいてい必要なくなる。 -- Frederick P. Brooks Jr. *1 プログラミングにおいてはデータ構造が重要であり、正しいデータ 構造を選択すればアルゴリズムは自明なものとなる、という主張が ある。Rob Pike*2 の "Notes on Programming in C" *3 によると、現実的なプログラムに必要なデータ構造は次の 4つであ るという。 配列 (array) 連結リスト (linked list) ハッシュテーブル
An Implementation of Double-Array Trie
Contents What is Trie? What Does It Take to Implement a Trie? Tripple-Array Trie Double-Array Trie Suffix Compression Key Insertion Key Deletion Double-Array Pool Allocation An Implementation Download Other Implementations References What is Trie? Trie is a kind of digital search tree. (See [Knuth1972] for the detail of digital search tree.) [Fredkin1960] introduced the trie terminology, which is
Fast String Searching With Suffix Trees | Mark Nelson
Published in Dr. Dobb’s Journal August, 1996 I think that I shall never see A poem lovely as a tree. Poems are made by fools like me, But only God can make a tree. Joyce Kilmer A tree’s a tree. How many more do you need to look at? -Ronald Reagan The problem Matching string sequences is a problem that computer programmers face on a regular basis. Some programming tasks, such as data compression or
無題ドキュメント
次に、各Suffixにおける大小関係を定義します。この大小関係は辞書式順序です。辞書式順序とは、辞書に並んでいる通りの順番であり、簡単に言えば、 (1)両Suffixを頭（左）から順番に一文字ずつ比較していき、初めて違うところで、文字の大小関係で比較を行う (2)もし、二つを比較していき、片方のSuffixが終わりに達してしまったら、そちらの方が小さいと定義する。 例えば、(1)は上の例でいえば、 S5 と S7を比較するとすると S5 adabra S7 abra 一文字目は両方ともaで、同じなので二文字目（赤い部分）を比較すると、dとbであり、文字の大小関係で d > b なので S7 < S5 という大小関係がつきます。 (2)については、S0 と S7を比較すると S0 abracadabra S7 abra で、頭から4文字は同じであり、S7はデータの最後に達しました。この
線形時間で Suffix Array 作成
線形時間で Suffix Array 作成 2005-01-23-1 [Algorithm] 週末自己啓発！アルゴリズムの勉強。趣味の世界。 taku-ku 氏に教えてもらった論文。線形時間で Suffix Array を作る話。 Suffix Tree 方式だと O(n) でできるのだがこれは違うやり方。 Juha K¨arkk¨ainen and Peter Sanders: "Simple Linear Work Suffix Array Construction", ICALP 2003, LNCS 2719, pp. 943-955, 2003. <http://www.cs.helsinki.fi/u/tpkarkka/publications/icalp03.pdf> Abstract. [...] 1. recursively sort suffixes beginning
Matzにっき(2007-08-17)
<< 2007/08/ 1 1. [言語] 連載：C# 2.0入門 第3回 新しい繰り返しのスタイル − yield return文とForEachメソッド − ＠IT 2. [Ruby] Shoes, a Tiny Toolkit for Making Browser-like Things 2 1. [OSS] Download Hadoop at OSCON (Yahoo! Developer Network blog) 2. ウェブキャリアでWebエンジニアとしてのキャリアを磨こう 株式会社ウェブキャリア 3. 先達の業界に学ぶプロジェクトマネジメント 第1回 20年は遅れているITプロマネ：ITpro 4. 横浜 3 1. [OSS] 特別講演：「オープンソース・ソフトウェア開発思想とリアルな地域ネットワークの連 2. [Ruby] トークセッション-5：「世界に広がるオブジェク
A Hash Function for Hash Table Lookup
I offer you a new hash function for hash table lookup that is faster and more thorough than the one you are using now. I also give you a way to verify that it is more thorough. All the text in this color wasn't in the 1997 Dr Dobbs article. The code given here are all public domain. Over the past two years I've built a general hash function for hash table lookup. Most of the two dozen old hashes I
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://www.neurosci.aist.go.jp/~akaho/thesis/thesis-www/node16.html