幅優先探索 - Wikipedia
ドイツの都市間の接続を示した例 フランクフルトから幅優先検索を行った場合にできる木構造 幅優先探索（はばゆうせんたんさく、英: breadth first search）はグラフ理論(Graph theory)において木構造(tree structure)やグラフ(graph)の探索に用いられるアルゴリズム。アルゴリズムは根ノードで始まり隣接した全てのノードを探索する。それからこれらの最も近いノードのそれぞれに対して同様のことを繰り返して探索対象ノードをみつける。「横型探索」とも言われる。 幅優先探索は解を探すために、グラフの全てのノードを網羅的に展開・検査する。最良優先探索とは異なり、ノード探索にヒューリスティクスを使わずに、グラフ全体を目的のノードがみつかるまで、目的のノードに接近しているかどうかなどは考慮せず探索する。
ハッシュテーブル - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "ハッシュテーブル" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2016年9月) ハッシュテーブルの例（名前をキーとして電話番号を検索） ハッシュテーブル (英: hash table) は、キーと値の組（エントリと呼ぶ）を複数個格納し、キーに対応する値をすばやく参照するためのデータ構造。ハッシュ表ともいう。ハッシュテーブルは連想配列や集合の効率的な実装のうち1つである。 ハッシュテーブルはキーをもとに生成されたハッシュ値を添え字とした配列である。通常、配列の添え字には非負整数しか扱えない。そこで、キーを要約する値であるハッシュ値を
P2Pと分散ハッシュテーブル〜その１
さて、P2Pでは最近「分散ハッシュテーブル」というキーワードをよく聞きます。分散ハッシュテーブルついては後で紹介しますが、これを用いるとルーティング、検索が高速に、しかもP2Pネットワーク全体に対して適用することができます。例えば既にeMuleと呼ばれるファイル共有システムでは分散ハッシュテーブルの一種であるkademliaが使われています。ではそもそも分散ハッシュテーブルとはどういうものなのでしょうか？それを説明するにはまず検索で使われるハッシュ法を説明する必要があります。 [お知らせ]分散ハッシュテーブル（ＤＨＴ）についてわかりやすく解説したページを作りました。 ＤＨＴに興味のある方はまずこちらをご覧下さい。 分散ハッシュテーブル（ＤＨＴ）入門〜その１ ハッシュ法 今、あるデータベースを考えてください。ここには人の名前と身長が書いてあるテーブルとしましょう。例えば table_1={
Implementation notes: sparse_hash, dense_hash, sparsetable
Implementation of sparse_hash_map, dense_hash_map, and sparsetable This document contains a few notes on how the data structures in this package are implemented. This discussion refers at several points to the classic text in this area: Knuth, The Art of Computer Programming, Vol 3, Hashing. sparsetable For specificity, consider the declaration sparsetable<Foo> t(100); // a sparse array with 100
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
Extendible hashing - Wikipedia
Extendible hashing is a type of hash system which treats a hash as a bit string and uses a trie for bucket lookup.[1] Because of the hierarchical nature of the system, re-hashing is an incremental operation (done one bucket at a time, as needed). This means that time-sensitive applications are less affected by table growth than by standard full-table rehashes. Extendible hashing was described by R
mixi Engineers’ Blog » Inside Tokyo Cabinet その弐
予定を立てた途端にやりたくなくなる症候群に堪えて連載を続けるmikioです（こんな私でもエアーマンくらいは倒せます）。前回はDBMの基本について説明しましたが、それを忠実に実装しても実際には使いものにはならないことにも触れました。今回は、実用的なDBMに進化すべく、Tokyo Cabinet（およびその前身のQDBM）で考えた工夫についてお話します。 ハッシュ関数についてもう少し 前回の記事に関して、「ハッシュ関数はビットシフト使って実装した方が早いよ」という旨のお便りをいただきました（ありがとうございます）。まさにその通りで、乗算命令（ここではimull）より左シフト命令（ここではsall）の方が速いみたいです（Intelの資料によると、mulが15から18で、salが4とのこと）。しかし、DBMの場合はファイルI/Oにかかる時間が支配的になるというのが重要な点です。したがって、ハッシュ
Inside Tokyo Cabinet その壱 - mixi engineer blog
約半年間の沈黙を破ってOSSの世界に戻ってきつつあるmikioです。先日、Tokyo Cabinet（以下「TC」と呼びます）というデータベースライブラリをリリースしました。今回から数回に分けて、TCの設計と苦労話について連載してみます。 DBMとは TCは、いわゆるDBMの系譜のデータベースライブラリで、単純なハッシュテーブルをファイル上で永続化するだけの機能を提供します。DBMはAT&Tの古代UNIXの時代から受け継がれる伝統芸能なのですが、私はそういう枯れた技術が大好きなのです。 プログラマの皆さんは、PerlやRubyではハッシュ（連想配列）と呼ばれ、JavaやC++ではmapと呼ばれるような、何らかのキーに関連づけてなんらかの値を記録するデータ構造って実によく使いますよね。例えばmixiでは、ユーザアカウントに関連する情報（名前とかニックネームとか）は、ユーザIDをキーにしたハッ
libketama - a consistent hashing algo for memcache clients - Amarok Blog
We wrote ketama to replace how our memcached clients mapped keys to servers. Previously, clients mapped keys->servers like this: server = serverlist[hash(key)%serverlist.length]; This meant that whenever we added or removed servers from the pool, everything hashed to different servers, which effectively wiped the entire cache. We add (and sometimes remove) servers from the memcached pool often
[空を飛ぶ鳥の群れの動きを再現するアルゴリズムの論文] Craig Reynolds: Flocks, Herds, and Schools: A Distributed Behavioral Model
Published in Computer Graphics, 21(4), July 1987, pp. 25-34. (ACM SIGGRAPH '87 Conference Proceedings, Anaheim, California, July 1987.) Flocks, Herds, and Schools: A Distributed Behavioral Model 1 Craig W. Reynolds Symbolics Graphics Division [obsolete addresses removed 2] Abstract The aggregate motion of a flock of birds, a herd of land animals, or a school of fish is a beautiful and familiar par
線形時間で 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
[を] Suffix Array の解説文書のリンク集
Suffix Array の解説文書のリンク集 2006-04-10-3 [Algorithm] Suffix Array について解説している日本語による文書のうち、 Webで閲覧できるもののリンク集。随時更新予定。 - 用語解説: Suffix Array (PDF) via http://ta2o.net/tools/sufary/ - Suffix Array の解説 in D論 (PDF) via http://ta2o.net/tools/sufary/ - 横着プログラミング 第9回: sary: Suffix Array のライブラリとツール http://0xcc.net/unimag/9/ - Suffix Arrayの簡単な説明 http://sary.sourceforge.net/docs/suffix-array.html - Suffix Trees and
最小完全ハッシュ関数の作り方
■順列型の最小完全ハッシュ関数 ０から４までの５個の数字が下のように並んでいる場合を例にして説明します。 ５個の数字の並べ方は５！通りありますので５！(=120)通りの並べ方の総てに対して0から119までの数値を一意に割り付けることが目的となります。 ３４１０２ ここでは左側から順に数字を見ていくことにします。最初の数字は３で残りの数字の個数は４個ですね。 この残れさた数字の個数分の総順列数は４！ですが、この数量を基数と言います。 つまり左端の数字が何であるかを完全に識別する為に最低限必要な基本となる重みのことです。 従って先ず最初の数字３に基数である４！を掛け算してはじき出します。 [３]４１０２ → ３＊４！ 次に左から２番目の数字ですが、ここから先はとても注意が必要です。 ２番目の数字は４で残りの数字の個数は３個です。残りの数字の個数が３個なので基数は３！になります。つまり基数が変化
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://swig.stanford.edu/pub/summaries/database/linhash.html
http://www.inf.unibz.it/dis/teaching/DMS/lecturenotes/dms03.pdf
サービス終了のお知らせ
https://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/PATRICIA/
http://www.codeproject.com/csharp/patriciatrie.asp
サービス終了のお知らせ
Data Structures – Unraveling the Complexity of Data Organization