language-agnostic - あまり知られていないが有用なデータ構造は何ですか?

Question

非常に便利なデータ構造がいくつかありますが、ほとんどのプログラマーには知られていません。彼らはどれですか？

リンクリスト、バイナリツリー、ハッシュについては誰もが知っていますが、たとえば、スキップリストやブルームフィルターについてはどうでしょうか。あまり一般的ではないが、優れたアイデアに依存し、プログラマーのツールボックスを充実させるため、知っておく価値のあるデータ構造をもっと知りたいと思います。

PS:共通のデータ構造のプロパティを巧みに利用するDancing linksのようなテクニックにも興味があります。

EDIT :データ構造をより詳細に説明しているページへのリンクを含めるようにしてください。また、なぜデータ構造が優れているのかについて、いくつかの言葉を追加してみてください( Jonas Kölkerがすでに指摘しているように)。また、回答ごとに 1 つのデータ構造を提供するようにしてください。これにより、投票だけに基づいて、より優れたデータ構造が上位に浮上することができます。

score 270 · Accepted Answer

プリフィックスツリーまたはクリティカルビットツリーとも呼ばれるトライは、 40 年以上存在していますが、まだあまり知られていません。トライの非常にクールな使用法は、トライとハッシュ関数を組み合わせた「 TRASH - 動的 LC トライとハッシュデータ構造」で説明されています。

score 231 · Accepted Answer

ブルームフィルター: mビットのビット配列で、最初はすべて 0 に設定されています。

アイテムを追加するには、k 個のハッシュ関数を実行して、配列内のk 個のインデックスを取得し、それを 1 に設定します。

アイテムがセット内にあるかどうかを確認するには、kインデックスを計算し、それらがすべて 1 に設定されているかどうかを確認します。

もちろん、これは誤検知の可能性をある程度与えます (ウィキペディアによると、約 0.61^(m/n) で、n は挿入されたアイテムの数です)。偽陰性はあり得ません。

アイテムを削除することはできませんが、int の配列とインクリメント/デクリメントで表されるカウントブルームフィルターを実装できます。

score 139 · Accepted Answer

ロープ：これは、安価な前置文字列、部分文字列、中間挿入、および追加を可能にする文字列です。私は実際に一度しか使用していませんが、他の構造では十分ではありませんでした。通常の文字列と配列の先頭に追加するのは、私たちが行う必要のあることには非常に高額であり、すべてを逆にすることは問題外でした。

score 91 · Accepted Answer

空間インデックス、特にR ツリーとKD ツリーは、空間データを効率的に格納します。これらは、地理的な地図の座標データと VLSI の場所とルートのアルゴリズムに適しており、場合によっては最近傍検索にも適しています。

ビット配列は、個々のビットをコンパクトに格納し、高速なビット操作を可能にします。

score 86 · Accepted Answer

ジッパー- 「カーソル」の自然な概念を持つように構造を変更するデータ構造の派生物 - 現在の場所。これらは、インデックスが範囲外にならないことを保証するため、非常に便利です。たとえば、 xmonad ウィンドウマネージャーで、どのウィンドウがフォーカスされたかを追跡するために使用されます。

驚くべきことに、微積分の手法を元のデータ構造の型に適用することで、それらを導き出すことができます!

score 69 · Accepted Answer

ここにいくつかあります：

サフィックス試行。ほぼすべての種類の文字列検索に役立ちます (http://en.wikipedia.org/wiki/Suffix_trie#Functionality )。接尾辞配列も参照してください。サフィックスツリーほど高速ではありませんが、はるかに小さいです。
スプレーツリー (前述のとおり)。彼らがクールな理由は 3 つあります。
- それらは小さい: 二分木で行うように左右のポインターのみが必要です (ノードの色やサイズの情報を保存する必要はありません)。
- それらは（比較的）実装が非常に簡単です
- それらは、多数の「測定基準」全体に対して最適な償却複雑さを提供します (ログ n ルックアップ時間は、誰もが知っているものです)。見る http://en.wikipedia.org/wiki/Splay_tree#Performance_theorems
ヒープ順の検索ツリー: キーに関しては検索ツリーであり、優先順位に関してはヒープ順になるように、一連の (key, prio) ペアをツリーに格納します。そのようなツリーが独特の形をしていることを示すことができます (常に完全に左側に詰め込まれているわけではありません)。ランダムな優先度を使用すると、予想される O(log n) 検索時間、IIRC が得られます。
ニッチな 1 つは、O(1) 近隣クエリを使用した無向平面グラフの隣接リストです。これはデータ構造ではなく、既存のデータ構造を編成する特定の方法です。方法は次のとおりです。すべての平面グラフには、次数が最大 6 のノードがあります。そのようなノードを選択し、その隣接ノードを隣接リストに入れ、グラフから削除し、グラフが空になるまで再帰します。ペア (u, v) が与えられたら、v の隣接リストで u を探し、u の隣接リストで v を探します。どちらもサイズが最大 6 であるため、これは O(1) です。

上記のアルゴリズムでは、u と v が隣接している場合、v のリストに u と u のリストに v の両方が含まれることはありません。これが必要な場合は、各ノードの不足しているネイバーをそのノードのネイバーリストに追加するだけですが、高速ルックアップのために調べる必要があるネイバーリストの量を保存します。

score 65 · Accepted Answer

標準のデータ構造に代わるロックフリーの代替手段、つまりロックフリーのキュー、スタック、リストは見過ごされがちです。
同時実行の優先度が高くなり、Mutex やロックを使用して同時読み取り/書き込みを処理するよりもはるかに優れた目標となるにつれて、それらはますます関連性が高くなります。

ここにいくつかのリンクがあり
ます http://www.cl.cam.ac.uk/research/srg/netos/lock-free/
http://www.research.ibm.com/people/m/michael/podc-1996.pdf [PDFへのリンク]
http://www.boyet.com/Articles/LockfreeStack.html

Mike Acton の(しばしば挑発的な) ブログには、ロックフリーの設計とアプローチに関する優れた記事がいくつかあります。

score 55 · Accepted Answer

Disjoint Setは、一連のアイテムを個別のセットに分割してメンバーシップをクエリする必要がある場合に非常に便利だと思います。Union 操作と Find 操作を適切に実装すると、実質的に一定の償却コストが得られます (データ構造クラスを正しく思い出せば、Ackermnan の関数の逆です)。

score 52 · Accepted Answer

フィボナッチヒープ

これらは、Shortest Path 問題など、多くのグラフ関連の問題に対して (漸近的に) 最も高速な既知のアルゴリズムの一部で使用されています。ダイクストラのアルゴリズムは、標準のバイナリヒープを使用して O(E log V) 時間で実行されます。フィボナッチヒープを使用すると、それが O(E + V log V) に改善されます。これは、高密度グラフの大幅な高速化です。しかし、残念なことに、それらは定数係数が高く、実際には実用的ではないことがよくあります。

score 44 · Accepted Answer

3D レンダリングの経験がある人なら誰でもBSP ツリーに精通しているはずです。一般的には、3D シーンを、カメラの座標と方位を知った上でレンダリングできるように構造化する方法です。

Binary space partitioning (BSP) は、超平面によって空間を凸集合に再帰的に再分割する方法です。この分割により、BSP ツリーと呼ばれるツリーデータ構造によってシーンが表現されます。

つまり、複雑な形状の多角形を凸集合、または完全に非反射角 (180° 未満の角度) で構成されるより小さい多角形に分割する方法です。スペースのパーティション化のより一般的な説明については、スペースのパーティション化を参照してください。

もともと、このアプローチはレンダリング効率を高めるために 3D コンピュータグラフィックスで提案されました。その他のアプリケーションには、CAD での形状 (構成的ソリッドジオメトリ) による幾何学的操作の実行、ロボット工学や 3D コンピューターゲームでの衝突検出、および複雑な空間シーンの処理を伴うその他のコンピューターアプリケーションが含まれます。

score 43 · Accepted Answer

43

ハフマンの木-圧縮に使用されます。

于 2009-02-22T04:47:47.383 に答える

score 38 · Accepted Answer

特に、前述の純粋に機能的なデータ構造のファンであれば、Finger Treesをご覧ください。それらは、償却された定数時間での端へのアクセスをサポートする永続的なシーケンスの関数表現であり、小さい部分のサイズの時間対数での連結と分割です。

元の記事によると：

関数の 2 ～ 3 本のフィンガーツリーは、Okasaki (1998) によって導入された、暗黙の再帰的スローダウンと呼ばれる一般的な設計手法の例です。これらのツリーは、効率的な連結と分割に必要な柔軟性を提供するためにペアを 2 ～ 3 個のノードに置き換えて、彼の暗黙の deque 構造を拡張したものであることは既に述べました。

Finger Tree はmonoidでパラメーター化できます。異なるモノイドを使用すると、ツリーの動作が異なります。これにより、Finger Tree は他のデータ構造をシミュレートできます。

score 34 · Accepted Answer

34

循環またはリングバッファー- ストリーミングなどに使用されます。

于 2009-03-17T18:30:42.547 に答える

score 33 · Accepted Answer

マークルツリー (つまり、ハッシュツリー)について誰も言及していないことに驚いています。

ファイルの一部しか利用できない場合に、ファイル全体のハッシュを検証する必要がある多くの場合 (P2P プログラム、デジタル署名) で使用されます。

score 32 · Accepted Answer

<zvrba>VanEmde-Boasの木

なぜかっこいいのかを知っておくと便利だと思います。一般的に、「なぜ」という質問が最も重要です;）

私の答えは、使用されているキーの数に関係なく、{1..n}キーを持つO（log log n）辞書を提供するということです。半分を繰り返すとO（log n）が得られるのと同じように、sqrtingを繰り返すとO（log log n）が得られます。これは、vEBツリーで発生することです。

score 31 · Accepted Answer

スプレーツリーはどうですか？

また、Chris Okasaki の純粋に機能的なデータ構造が思い浮かびます。

score 29 · Accepted Answer

ハッシュテーブルの興味深い変形はCuckoo Hashingと呼ばれます。ハッシュの衝突に対処するために、1 つだけではなく複数のハッシュ関数を使用します。衝突は、プライマリハッシュによって指定された場所から古いオブジェクトを削除し、代替ハッシュ関数によって指定された場所に移動することによって解決されます。Cuckoo Hashing を使用すると、3 つのハッシュ関数だけで負荷率を最大 91% まで高めることができ、アクセス時間も良好であるため、メモリ空間をより効率的に使用できます。

score 27 · Accepted Answer

最小最大ヒープは、両端の優先度キューを実装するヒープのバリエーションです。これは、ヒーププロパティの単純な変更によって実現されます。偶数 (奇数) レベルのすべての要素がすべての子および孫よりも小さい (大きい) 場合、ツリーは最小-最大順序付けられていると言われます。レベルは 1 から始まる番号が付けられています。

http://internet512.chonbuk.ac.kr/datastructure/heap/img/heap8.jpg

score 26 · Accepted Answer

私はCache Oblivious datastructuresが好きです。基本的な考え方は、ツリーを再帰的に小さなブロックにレイアウトして、さまざまなサイズのキャッシュがそれらに都合よく収まるブロックを利用できるようにすることです。これにより、RAM の L1 キャッシュからディスクから読み取られる大きなデータチャンクに至るまで、すべてのキャッシングレイヤーのサイズの詳細を知る必要なく、キャッシングを効率的に使用できます。

score 23 · Accepted Answer

左寄りの赤黒木。2008 年に公開された Robert Sedgewick による赤黒ツリーの大幅に単純化された実装 (実装するコードの行数は ~ 半分)。Red-Black ツリーの実装に頭を悩ませたことがある場合は、このバリアントについて読んでください。

Andersson Trees と非常によく似ています (同一ではないにしても)。

score 22 · Accepted Answer

ワークスチールキュー

複数のスレッド間でワークを均等に分割するためのロックフリーデータ構造 C/C++ でのワークスティーリングキューの実装?

score 19 · Accepted Answer

Gerth Stølting Brodal と Chris Okasaki によるブートストラップされた歪んだ二項ヒープ:

長い名前にもかかわらず、関数設定であっても漸近的に最適なヒープ操作を提供します。

O(1)サイズ、ユニオン、インサート、最小
O(log n)deleteMin

左翼のヒープO(1)など、データ構造の教科書で一般的O(log n)に取り上げられているよく知られているヒープとは異なり、結合には時間がかかることに注意してください。そして、フィボナッチヒープとは異なり、これらの漸近線は、たとえ永続的に使用されたとしても、償却されるのではなく、最悪の場合です!

Haskell には複数の実装があります。

Brodal が同じ漸近線を持つ命令型ヒープを思いついた後、これらは Brodal と岡崎によって共同で導出されました。

score 18 · Accepted Answer

リアルタイムレイトレーシングで（とりわけ）使用される空間データ構造であるKd-Treeには、異なるスペースと交差する三角形をクリップする必要があるという欠点があります。一般的に、BVHはより軽量であるため、より高速です。
MX-CIF Quadtreesは、通常のQuadtreeとQuadのエッジのバイナリツリーを組み合わせることにより、任意のポイントセットの代わりにバウンディングボックスを格納します。
HAMT、関連する定数のために一般にO（1）ハッシュマップを超えるアクセス時間の階層ハッシュマップ。
転置インデックスは、さまざまな検索用語に関連付けられたドキュメントをすばやく検索するために使用されるため、検索エンジンの分野で非常によく知られています。

すべてではないにしても、これらのほとんどは、NISTのアルゴリズムとデータ構造の辞書に記載されています。

score 18 · Accepted Answer

ボールツリー。彼らが人々をくすくす笑わせるという理由だけで。

ボールツリーは、距離空間内のポイントにインデックスを付けるデータ構造です。これがそれらの構築に関する記事です。これらは、ある点に最も近い近傍を見つけたり、k-meansを加速したりするためによく使用されます。

score 17 · Accepted Answer

実際にはデータ構造ではありません。動的に割り当てられた配列を最適化するためのより多くの方法ですが、Emacs で使用されるギャップバッファーは一種のクールです。

score 16 · Accepted Answer

フェンウィックツリー。これは、指定された 2 つのサブインデックス i と j の間で、ベクトル内のすべての要素の合計数を保持するデータ構造です。最初から合計を事前計算する簡単な解決策では、アイテムを更新できません (追いつくには O(n) の作業を行う必要があります)。

フェンウィックツリーを使用すると、O(log n) で更新およびクエリを実行できます。その仕組みは非常にクールでシンプルです。フェンウィックの元の論文で非常によく説明されており、ここから自由に入手できます。

http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol24/issue3/spe884.pdf

その父である RQM ツリーも非常に優れています。ベクトルの 2 つのインデックス間の最小要素に関する情報を保持でき、O(log n) の更新とクエリでも機能します。最初に RQM を教え、次にフェンウィックツリーを教えるのが好きです。

score 14 · Accepted Answer

ヴァンエムデボアスの木。最大 2^20 の整数に対して、C++の実装さえあります。

score 13 · Accepted Answer

ネストされたセットは、リレーショナルデータベースでツリーを表現し、それらに対してクエリを実行するのに適しています。たとえば、ActiveRecord（Ruby on RailsのデフォルトのORM）には、非常に単純なネストされたセットプラグインが付属しているため、ツリーの操作は簡単です。

score 12 · Accepted Answer

Scapegoat trees. A classic problem with plain binary trees is that they become unbalanced (e.g. when keys are inserted in ascending order.)

Balanced binary trees (AKA AVL trees) waste a lot of time balancing after each insertion.

Red-Black trees stay balanced, but require a extra bit of storage for each node.

Scapegoat trees stay balanced like red-black trees, but don't require ANY additional storage. They do this by analyzing the tree after each insertion, and making minor adjustments. See http://en.wikipedia.org/wiki/Scapegoat_tree.

score 12 · Accepted Answer

展開された連結リストは、各ノードに複数の要素を格納する連結リストのバリエーションです。参照などのリストメタデータの保存に関連するメモリオーバーヘッドを削減しながら、キャッシュパフォーマンスを大幅に向上させることができます。これは B ツリーに関連しています。

record node {
    node next       // reference to next node in list
    int numElements // number of elements in this node, up to maxElements
    array elements  // an array of numElements elements, with space allocated for maxElements elements
}

score 12 · Accepted Answer

それはかなりドメイン固有ですが、ハーフエッジのデータ構造はかなりきれいです。ポリゴンメッシュ (面とエッジ)を反復する方法を提供します。これは、コンピューターグラフィックスと計算幾何学で非常に役立ちます。

score 11 · Accepted Answer

Hinze と Patersonによる2-3 Finger Treesは、幅広い操作に対応する優れた漸近線を備えた優れた関数型データ構造のスイスアーミーナイフです。複雑ではありますが、先行する Kaplan と Tarjan による再帰的なスローダウンによる連鎖を伴う永続リストによる命令構造よりもはるかに単純です。

これらは、末尾、追加のO(1)いずれかにアクセスできるカテナブルな両端キューとして機能し、シーケンスの任意の部分のモノイド接頭辞の合計に直接アクセスできるインデックスを提供します。O(log min(n,m))O(log min(n,length - n))

実装はHaskell、Coq、F#、Scala、Java、C、Clojure、C#およびその他の言語に存在します。

それらを使用して、優先検索キュー、間隔マップ、ヘッドアクセスが高速なロープ、マップ、セット、カテナブルシーケンス、または迅速にカテナブル/インデックス可能なシーケンスでモノイド結果を収集すると表現できるほとんどすべての構造を実装できます。

それらの派生と使用法を説明するスライドもいくつかあります。

score 10 · Accepted Answer

Interval Treesが本当に大好きです。それらを使用すると、一連の間隔 (つまり、開始/終了時間など) を取得し、どの間隔に特定の時間が含まれるか、または特定の期間中にどの間隔が「アクティブ」であったかを照会できます。クエリは O(log n) で実行でき、前処理は O(n log n) です。

score 10 · Accepted Answer

XOR リンクリストは、2 つの XOR されたポインターを使用して、二重リンクリストのストレージ要件を軽減します。ちょっと曖昧だけどスッキリ！

score 10 · Accepted Answer

あまり知られていないが、かなり気の利いたデータ構造の 1 つは、フェンウィックツリー(バイナリインデックスツリーまたは BITとも呼ばれます) です。累積合計を格納し、O(log(n)) 演算をサポートします。累積合計はあまりエキサイティングに聞こえないかもしれませんが、ソート/ログ (n) データ構造を必要とする多くの問題を解決するために適応させることができます。

IMO、その主なセールスポイントは実装の容易さです。そうでなければ、赤黒/avlツリーのコーディングを伴うアルゴリズムの問題を解決するのに非常に役立ちます。

score 10 · Accepted Answer

ペアリングヒープは、ヒープデータ構造の一種であり、比較的単純な実装と優れた実用的な償却パフォーマンスを備えています。

score 9 · Accepted Answer

スプラッシュテーブルは素晴らしいです。通常のハッシュテーブルに似ていますが、一定時間のルックアップが保証され、パフォーマンスを損なうことなく 90% の使用率を処理できます。これらはCuckoo Hashの一般化です(優れたデータ構造でもあります)。それらは特許を取得しているように見えますが、ほとんどの純粋なソフトウェア特許と同様に、あまり心配する必要はありません。

score 8 · Accepted Answer

地域の四分木

（ウィキペディアより引用）

領域四分木は、領域を 4 つの等しい象限、サブ象限などに分解することにより、空間の分割を 2 次元で表します。各リーフノードには、特定のサブ領域に対応するデータが含まれます。ツリー内の各ノードには、正確に 4 つの子があるか、子がない (リーフノード) かのいずれかです。

このような四分木は、緯度や経度、その他のタイプの座標などの空間データを格納するのに適しています。

これは、大学時代の私のお気に入りのデータ構造でした。この男をコーディングして、それが機能するのを見るのはとてもクールでした。少し考えが必要で、人里離れた場所にあるプロジェクトを探しているなら、強くお勧めします。とにかく、データ構造クラスで通常割り当てられる標準の BST 派生物よりもはるかに楽しいです!

実際、おまけとして、クラスプロジェクトに至るまでの講義のメモ (バージニア工科大学から) をここ (pdf 警告) で見つけました。

score 8 · Accepted Answer

二分決定図は私のお気に入りのデータ構造の 1 つであり、実際には縮小順序付き二分決定図 (ROBDD) です。

これらの種類の構造は、たとえば次の目的で使用できます。

アイテムのセットを表し、それらのセットに対して非常に高速な論理演算を実行します。
式のすべての解を見つけることを意図したブール式

多くの問題はブール式で表すことができることに注意してください。たとえば、suduku の解はブール式として表現できます。そして、そのブール式の BDD を構築すると、すぐにソリューションが得られます。

score 8 · Accepted Answer

強化されたハッシュアルゴリズムは非常に興味深いものです。線形ハッシュは、テーブル全体を再ハッシュするのではなく、一度にハッシュテーブル内の 1 つの「バケット」を分割できるため、優れています。これは、分散キャッシュの場合に特に役立ちます。ただし、ほとんどの単純な分割ポリシーでは、すべてのバケットを立て続けに分割することになり、テーブルの負荷率がかなり大きく変動します。

スパイラルハッシングも本当にいいと思います。線形ハッシュと同様に、一度に 1 つのバケットが分割され、バケット内のレコードの半分弱が同じ新しいバケットに入れられます。とてもきれいで速いです。ただし、各「バケット」が同様の仕様のマシンでホストされている場合、効率が悪い可能性があります。ハードウェアを最大限に活用するには、強力でないマシンと強力なマシンを組み合わせて使用する必要があります。

score 7 · Accepted Answer

私は treaps が好きです - ヒープ構造をランダムな優先順位で二分探索木の上に重ね合わせてバランスをとるというシンプルでありながら効果的なアイデアです。

score 6 · Accepted Answer

範囲を格納するために反転リストを使用することがありますが、正規表現で文字クラスを格納するためによく使用されます。たとえば、http://www.ibm.com/developerworks/linux/library/l-cpinv.htmlを参照してください。

もう 1 つの優れた使用例は、加重ランダム決定です。シンボルと関連する確率のリストがあり、これらの確率に従ってそれらをランダムに選びたいとします。

   a => 0.1
   b => 0.5
   c => 0.4

次に、すべての確率の累計を計算します。

  (0.1、0.6、1.0)

これが反転リストです。0 から 1 の間の乱数を生成し、リスト内の次に高いエントリのインデックスを見つけます。ソートされているため、バイナリ検索でそれを行うことができます。インデックスを取得したら、元のリストでシンボルを検索できます。

シンボルがある場合n、重みの分布とは関係なく、ランダムに選択されたシンボルごとに O(n) の準備時間と O(log(n)) のアクセス時間がかかります。

反転リストのバリエーションでは、負の数を使用して範囲の終点を示します。これにより、特定のポイントで重複する範囲の数を簡単に数えることができます。例については、 http://www.perlmonks.org/index.pl?node_id=841368を参照してください。

score 6 · Accepted Answer

Arne Andersson ツリーは、右リンクのみを赤くできる赤黒ツリーに代わる単純な方法です。これにより、赤黒ツリーと同等のパフォーマンスを維持しながら、メンテナンスが大幅に簡素化されます。元の論文では、挿入と削除の優れた短い実装が提供されています。

score 6 · Accepted Answer

Fast Compact は次のことを試みます。

Judy arrays : ビット、整数、および文字列用の、非常に高速でメモリ効率のよい順序付けされたスパース動的配列。Judy 配列は、どの二分探索木よりも高速でメモリ効率が高いです。
HAT-trie: 文字列用のキャッシュを意識した Trie ベースのデータ構造
ディスクベースの文字列管理の B トライ

score 6 · Accepted Answer

DAWGは、同様の子ツリーが単一の親に圧縮される特別な種類のトライです。私は修正した DAWG を拡張し、ASSDAWG (Anagram Search Sorted DAWG) と呼ばれる気の利いたデータ構造を考え出しました。これが機能する方法は、文字列が DAWG に挿入されるたびに、最初にバケットでソートされてから挿入され、ルートからそのリーフノードに到達した場合に有効な順列を示す追加の番号をリーフノードが保持することです。これには 2 つの優れた利点があります。

挿入前に文字列をソートし、DAWG は同様のサブツリーを自然に折りたたむため、高レベルの圧縮が得られます (たとえば、「食べる」、「食べた」、「お茶」はすべて 1 つのパス aet になり、葉ノードに数字のリストが表示されます)。 aet のどの順列が有効か)。
与えられた文字列のアナグラムの検索は、ルートからリーフへのパスが置換番号を使用してリーフノードでそのパスのすべての有効なアナグラムを保持するため、超高速で簡単です。

score 5 · Accepted Answer

Zobrist Hashingは、ゲームボードの位置を表すために一般的に使用されるハッシュ関数です（チェスのように）が、確かに他の用途もあります。それの良いところの1つは、ボードが更新されるたびに段階的に更新できることです。

score 5 · Accepted Answer

BK-Trees、または Burkhard-Keller Treesは、文字列に近い一致をすばやく見つけるために使用できるツリーベースのデータ構造です。

score 5 · Accepted Answer

Donald Knuth が提示した横方向のヒープを見てみましょう。

http://stanford-online.stanford.edu/seminars/knuth/071203-knuth-300.asx

score 5 · Accepted Answer

フェンウィックツリー(またはバイナリインデックス付きツリー) は、ones ツールキットに追加する価値があります。カウンターの配列があり、(PPM 圧縮のように) 累積カウントを照会しながらそれらを常に更新する必要がある場合、Fenwick ツリーは O(log n) 時間ですべての操作を実行し、余分なスペースを必要としません。適切な紹介については、このトップコーダーチュートリアルも参照してください。

score 5 · Accepted Answer

文字列処理用のサフィックスツリーと配列、バランスリスト用のスキップリスト、自動バランスツリー用のスプレーツリーが好きです。

score 4 · Accepted Answer

4

永続データ構造

于 2010-07-17T17:17:21.180 に答える

score 4 · Accepted Answer

ブルームフィルターの言及によると、削除可能なブルームフィルター (DlBF) は、いくつかの点で基本的なカウントバリアントよりも優れています。http://arxiv.org/abs/1005.0352を参照

score 4 · Accepted Answer

スプレイツリーはクールです。それらは、最も頻繁に照会される要素をルートに近づけるように、自分自身を並べ替えます。

score 4 · Accepted Answer

これらすべてのグラフ構造から離れて、単純なRing-Bufferが大好きです。

適切に実装すると、パフォーマンスを維持し、場合によっては改善しながら、メモリフットプリントを大幅に削減できます。

score 4 · Accepted Answer

B* ツリー

より高価な挿入を犠牲にして効率的に検索できるのは、さまざまな B ツリーです。

score 4 · Accepted Answer

min-heap を使用して一定時間内に最小要素を見つけるか、max-heap を使用して最大要素を見つけることができます。しかし、両方の操作を実行したい場合はどうでしょうか? Min-Maxを使用して、一定時間内に両方の操作を実行できます。これは、最小最大順序付けを使用して機能します。つまり、連続するツリーレベル間で最小ヒープ比較と最大ヒープ比較を交互に行います。

score 3 · Accepted Answer

2つのスタックを使用して実装されたキューは、スペース効率がかなり高くなります（少なくとも1つの追加のポインター/参照オーバーヘッドを持つリンクリストを使用するのとは対照的です）。

2つのスタックを使用してキューを実装するにはどうすればよいですか？

キューが巨大な場合、これは私にとってうまく機能しました。ポインタに8バイトを節約すると、100万エントリのキューが約8MBのRAMを節約することを意味します。

score 3 · Accepted Answer

プライオリティデキューは、順序が異なる 2 つの個別のプライオリティキューを維持するよりも安価です。 http://www.alexandria.ucsb.edu/middleware/javadoc/edu/ucsb/adl/middleware/PriorityDeque.html http://cphstl.dk/Report/Priority-deque/cphstl-report-2001-14.pdf

score 3 · Accepted Answer

Paolo Ferragina と Giovanni Manzini によるFM-indexは本当にクールだと思います。特にバイオインフォマティクスでは。これは基本的に、接尾辞配列と参照テキストのバロウズ・ホイーラー変換の組み合わせを利用する圧縮された全文索引です。索引全体を解凍せずに索引を検索できます。

score 2 · Accepted Answer

2

PQ-ツリー

于 2010-05-23T02:23:35.670 に答える

score 2 · Accepted Answer

tokenmapこのデータ構造に名前があるかどうかはわかりませんが、 Boost に含めるために提案されたデータ構造は興味深いものです。これは、ルックアップが O(1) であるだけでなく、単純な配列アクセスである、動的にサイズ変更可能なマップです。私は、このデータ構造がどのように機能するかの基本原則を説明する、このデータ構造に関する背景資料のほとんどを書きました。

トークンマップのようなものは、ファイルまたはリソースハンドルをファイルまたはリソースを表すデータ構造にマップするために、オペレーティングシステムによって使用されます。

score 2 · Accepted Answer

Disjoint Set Forestは高速なメンバーシップクエリとユニオン操作を可能にし、Kruskal のアルゴリズムで最小スパニングツリーに使用されることで最もよく知られています。

本当にクールなことは、両方の操作がアッカーマン関数の逆数に比例して実行時間を償却し、これを「最速の」非定数時間データ構造にすることです。

score 2 · Accepted Answer

デルタリスト/デルタキューは、cron やイベントシミュレータなどのプログラムで使用され、次のイベントがいつ発生するかを判断します。 http://everything2.com/title/delta+list http://www.cs.iastate.edu/~cs554/lec_notes/delta_clock.pdf

score 2 · Accepted Answer

角縫いのデータ構造。要約から：

コーナースティッチングは、長方形の 2 次元オブジェクトを表現するための手法です。VLSI レイアウトの対話型編集システムに特に適しているようです。データ構造には 2 つの重要な機能があります。1 つ目は、空のスペースが明示的に表現されていることです。次に、パッチワークキルトのように、長方形の領域を角で縫い合わせます。この構成により、検索、作成、削除、ストレッチ、および圧縮のための高速アルゴリズム (線形時間またはそれ以上) が得られます。アルゴリズムは、VLSI 回路の単純化されたモデルの下で提示され、構造のストレージ要件が議論されます。測定によると、コーナーステッチには、可能な限り単純な表現の約 3 倍のメモリスペースが必要です。

score 2 · Accepted Answer

個人的には、疎行列データ構造が非常に興味深いと思います。 http://www.netlib.org/linalg/html_templates/node90.html

有名な BLAS ライブラリはこれらを使用します。また、数十万の行と列を含む線形システムを扱う場合、これらを使用することが重要になります。これらのいくつかは、コンピューターグラフィックスで一般的なコンパクトグリッド (基本的にはバケットソートグリッドのようなもの) にも似ています。 http://www.cs.kuleuven.be/~ares/publications/LD08CFRGRT/LD08CFRGRT.pdf

また、コンピューターグラフィックスに関する限り、MAC グリッドはやや興味深いものですが、それは単に賢いからです。 http://www.seas.upenn.edu/~cis665/projects/Liquation_665_Report.pdf

score 2 · Accepted Answer

Bucket Brigade

They are used extensively in Apache. Basically they are a linked list that loops around on itself in a ring. I am not sure if they are used outside of Apache and Apache modules but they fit the bill as a cool yet lesser known data structure. A bucket is a container for some arbitrary data and a bucket brigade is a collection of buckets. The idea is that you want to be able to modify and insert data at any point in the structure.

Lets say that you have a bucket brigade that contains an html document with one character per bucket. You want to convert all the < and > symbols into < and > entities. The bucket brigade allows you to insert some extra buckets in the brigade when you come across a < or > symbol in order to fit the extra characters required for the entity. Because the bucket brigade is in a ring you can insert backwards or forwards. This is much easier to do (in C) than using a simple buffer.

Some reference on bucket brigades below:

Apache Bucket Brigade Reference

Introduction to Buckets and Brigades

score 2 · Accepted Answer

Burrows–Wheeler 変換(ブロックソート圧縮)

圧縮に不可欠なアルゴリズム。テキストファイルの行を圧縮したいとしましょう。行を並べ替えると、情報が失われると言えます。しかし、BWT はこのように動作します。入力をソートし、元の順序を復元するために整数インデックスを保持することで、エントロピーを大幅に削減します。

score 2 · Accepted Answer

適切な文字列データ構造。ほとんどすべてのプログラマーは、言語が構造に対して持っているネイティブサポートに落ち着きますが、それは通常非効率的です (特に文字列を構築する場合は、別のクラスまたは何かが必要です)。

最悪なのは、文字列を C の文字配列として扱い、安全のために NULL バイトに依存することです。

score 2 · Accepted Answer

PATRICIA - 英数字でコード化された情報を取得するための実用的なアルゴリズム、DRMorrison (1968)。

PATRICIA ツリーは、Trie に関連しています。トライの問題は、キーのセットがまばらな場合、つまり、実際のキーが潜在的なキーのセットの小さなサブセットを形成している場合、非常によくあることですが、トライの内部ノードの多く (ほとんど) は、一人の子孫。これにより、トライのスペースの複雑さが高くなります。

http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/PATRICIA/

score 1 · Accepted Answer

CycleSortはかなりきちんとしたソートアルゴリズムだと思います。

これは、書き込みの総数を最小限に抑えるために使用される並べ替えアルゴリズムです。これは、フラッシュメモリの寿命が書き込み量に比例するフラッシュメモリを扱う場合に特に便利です。これがウィキペディアの記事ですが、最初のリンクに行くことをお勧めします。（素敵なビジュアル！）

score 1 · Accepted Answer

配列を使用して要素のデータを保存する巧妙なデータ構造がありますが、配列はリンクされたリスト/配列でリンクされています。

これには、要素の反復が非常に高速であり (純粋なリンクリストアプローチよりも高速)、メモリ内で要素を含む配列を移動したり、(解放) 割り当てを行ったりするためのコストが最小になるという利点があります。(このため、このデータ構造はシミュレーションに役立ちます)。

私はここからそれについて知っています：

http://software.intel.com/en-us/blogs/2010/03/26/linked-list-verses-array/

「...そして、追加の配列が割り当てられ、粒子の配列のセルリストにリンクされます。これは、TBBが並行コンテナーを実装した方法といくつかの点で似ています。」(リンクされたリストと配列のパフォーマンスについてです。 )

score 1 · Accepted Answer

Binomial heapには多くの興味深い特性があり、その中で最も役立つのはマージです。

score 1 · Accepted Answer

ポリゴンメッシュのハーフエッジデータ構造とウィングドエッジ。

計算幾何学アルゴリズムに役立ちます。

score 1 · Accepted Answer

以前はWPL Treesで運が良かったです。枝の加重パス長を最小化するツリーバリアント。重みはノードアクセスによって決定されるため、頻繁にアクセスされるノードはルートの近くに移動します。私はそれらを使用したことがないので、それらがスプレイツリーとどのように比較されるかはわかりません.

score 1 · Accepted Answer

再帰構造を追跡する環境。

コンパイラは、再帰的ではあるがツリーとは異なる構造を使用します。内側のスコープには外側のスコープへのポインターがあるため、入れ子は裏返しになります。変数がスコープ内にあるかどうかを確認することは、内側のスコープから外側のスコープへの再帰呼び出しです。

public class Env
{    
    HashMap<String, Object> map;
    Env                     outer;

    Env()
    {
        outer = null;
        map = new HashMap();
    }

    Env(Env o)
    {
        outer = o;
        map = new HashMap();
    }

    void put(String key, Object value)
    {
        map.put(key, value);
    }

    Object get(String key)
    {
        if (map.containsKey(key))
        {
            return map.get(key);
        }
        if (outer != null)
        {
            return outer.get(key);
        }
        return null;
    }

    Env push()
    {
        return new Env(this);
    }

    Env pop()
    {
        return outer;
    }
}

この構造に名前があるかどうかはわかりません。私はこれを裏返しリストと呼んでいます。

score 1 · Accepted Answer

他の誰かが既に Burkhard-Keller-Trees を提案しましたが、私自身の実装をプラグインするために、それらについてもう一度言及するかもしれないと思いました. :)

http://well-adjusted.de/mspace.py/index.html

より高速な実装があります (ActiveState の Python レシピまたは他の言語での実装を参照してください) が、私のコードがこれらのデータ構造を理解するのに役立つと思います/願っています。

ところで、BK ツリーと VP ツリーはどちらも、類似した文字列を検索する以外にも使用できます。いくつかの条件 (正、対称性、三角形の不等式) を満たす距離関数がある限り、任意のオブジェクトに対して類似性検索を実行できます。

score 0 · Accepted Answer

直角三角形ネットワーク（RTIN）

メッシュを適応的に細分割するための美しくシンプルな方法。分割操作とマージ操作は、それぞれ数行のコードです。

score 0 · Accepted Answer

RMQ と LCA に関連するいくつかのアルゴリズムについて読んだときに、別のデータ構造のデカルトツリーに出くわしました。デカルトツリーでは、2 つのノード間の最も低い共通の祖先が、それらの間の最小ノードです。RMQ 問題を LCA に変換すると便利です。

score 0 · Accepted Answer

二分決定図 (私のお気に入りのデータ構造で、ブール方程式を表し、それらを解くのに適しています。非常に多くのことに効果的です)
ヒープ (ノードの親が常にノードの子と何らかの関係を維持するツリー。たとえば、ノードの親は常にその子のそれぞれよりも大きい (max-heap) )
Priority Queues (実際には min-heaps と max-heaps だけで、多くの要素の順序を維持するのに適しています。たとえば、最も高い値を持つアイテムが最初に削除されることになっています)
ハッシュテーブル (あらゆる種類のルックアップ戦略とバケットオーバーフロー処理を含む)
バランスのとれた二分探索木 (それぞれに独自の利点があります)
- RB-trees (順序付けられた方法で挿入、検索、削除、および反復する場合、全体的に良好)
- Avl-trees (ルックアップは RB より高速ですが、それ以外は RB と非常によく似ています)
- Splay-trees (最近使用されたノードが再利用される可能性が高い場合、ルックアップが高速になります)
- フュージョンツリー (ルックアップ時間をさらに短縮するための高速乗算の活用)
- B+Trees (データベースおよびファイルシステムでのインデックス作成に使用され、インデックスからの読み取り/インデックスへの書き込みの待機時間が重要な場合に非常に効率的です)。
空間インデックス (点/円/長方形/線/立方体が互いに近接しているか、含まれているかを照会するのに最適)
- BSP ツリー
- 四分木
- オクトリー
- レンジツリー
- 似ているが少し違う木がたくさんあり、次元が違う
インターバルツリー (オーバーラップするインターバルを適切に見つける、線形)
グラフ
- 隣接リスト (基本的にはエッジのリスト)
- 隣接行列 (エッジごとに 1 ビットのグラフの有向エッジを表すテーブル。グラフトラバーサルが非常に高速)

これらは私が考えることができるものです。ウィキペディアには、データ構造に関するさらに多くの情報があります

language-agnostic - あまり知られていないが有用なデータ構造は何ですか?

83 に答える 83

Related

Reference