私は、人々がプログラミングにおいて知っておくべき最も有用なデータ構造と考えるものを見つけることに興味があります。いつも使用しているデータ構造は何ですか?
この投稿への回答は、問題に役立つデータ構造を見つけることに関心のある新しいプログラマーに役立つはずです。回答には、おそらくデータ構造、それに関する情報または関連するリンク、それが使用されている状況、およびこの問題に適している理由 (例: 理想的な計算の複雑さ、単純さと理解など) を含める必要があります。
各回答は、1 つのデータ構造のみに関するものである必要があります。
人々が共有できる知恵と経験の真珠に感謝します。
私が最もよく使用するデータ構造の 1 つは (もちろんベクター以外で)、Hashtable です。O(1) 時間で大量のデータを検索できるようにする必要がある場合は、これが唯一の選択肢です。つまり、コレクションのサイズが大きくなっても検索にかかる時間が長くなることはありません。
問題は、挿入と削除の時間が他のデータ構造よりも長く、コレクションを検索するための何らかのキーが必要なことです。すべての要素にはキーが必要です。このアルゴリズムは、各要素のキーを取得し、検索するハッシュ テーブル内のスロットを示すハッシュ コードを計算します。次に、実装に応じて、そのバケットに落ちたアイテムのリストに従ってアイテムを見つけるか、近くのバケットを検索します。hastable のサイズは、キー間のハッシュ コードの衝突の量に大きく影響されるハッシュの効率を決定します。
マップが必要で、予想されるマップの要素数が約 10 を超える場合はいつでも使用してください。効率を高めるにはテーブル内に多くの未使用スロットが必要なため、他の構造体よりもメモリを集中的に使用します。
C# にはDictionary<keytype, valuetype>、ハッシュテーブルまたはベクターをいつ使用するかを内部的に決定する HybridDictionary を備えた優れた実装があり、HybridDictionary さえあります。優れたプログラミング本で説明されていますが、ウィキペディアが役に立ちます:
http://en.wikipedia.org/wiki/Hashtable
投稿ごとに1つのデータ構造に関する要件を無視する必要があります.
配列- 最も基本的で、最速のアクセスを提供します。ベクトルは、単純な古い配列に対する即興であり、最近一般的に使用されている事実上の代替品です。 dequeueはこのテーマの別のバリエーションで、一定時間/ランダム アクセスを提供しますが、最初と最後での高速な挿入と削除のために最適化されています。
リンク リスト- 頻繁にドロップおよび挿入されるデータのリストを維持するのに非常に便利ですが、反復/検索には非常に時間がかかります。例: メモリ ページ内の空き/使用済みリスト
ツリー- より複雑な構造の基礎を形成する基本構造。この構造には多くの形式があります。ツリーがソートされている場合のログ検索時間を提供します。辞書などの大きなデータ項目に役立ちます。バイナリ/AVL および赤黒ツリーが最も一般的です。
マップとハッシュ- 正確にはデータ構造ではありませんが、巧妙なロジックと上記のデータ構造の組み合わせを使用して実装された複雑な高速検索アルゴリズムです。
これらのデータ構造とその実装は、C++ の STL ライブラリで利用できます。他の言語にもネイティブ実装があります。これらの基本的なデータ構造とそのバリエーション (キュー、スタック、プライオリティ キュー) のいくつかと、検索アルゴリズムについての知識があれば、基本は十分にカバーされていると言えます。
私は連想配列をかなり頻繁に使用しています。基本的には、文字列をインデックスとする配列です。
リンクされたリストの利点は、ノードの追加/削除が非常に安価であることです。配列とは異なり [...] 展開時にメモリを再割り当てする必要はありません。
配列があり、それを埋めるたびに割り当てサイズを 2 倍にすると、O(1) 個の追加が償却されます。また、配列のすべての要素をループすることは、キャッシュ効果により、リンクされたリストをループするよりも (壁時間で) 高速になる可能性があります (リンクを大きなチャンクに割り当てて、それらをいじりすぎない限り) ）。
また、配列は小さくなります。要素ごとのワード オーバーヘッドと、割り当てごとのオーバーヘッドを節約できます (これはおそらく少なくとも 2 つのワードです。1 つはサイズ用で、もう 1 つは空きリスト内の次のポインター用です)。
リンクリストの長所と短所は誰もが知っているはずですが、使用法がまったくないため、多くの人が忘れているようです。
リンクリストの利点は、ノードの追加/削除が非常に安価であるということです。コアで配列を使用する配列やデータ構造とは異なり、拡張時にメモリを再割り当てする必要はありません。
不利な点は、検索に対してまったくうまく機能しないことです。配列内のO（1）ルックアップは、リンクリストのO（n）です。
すべての構造と同様に、リンクリストは特定の条件下でのみ理想的です。しかし、適切なタイミングで使用すると、非常に強力です。
アイテムをループするために、「foreach」制御構造と組み合わせて配列を頻繁に使用していることに気づきました。以前は、数値インデックスと "for(i=1;i<n;i++)" を持つ配列を使用していました。明示的な数値インデックスの代わりに「foreach」を使用して配列をループすると、より一般的で読みやすいソリューションが得られることがわかりました。
二分木が好きです。特に Splay-Tree バリアント。これは自己均衡二分木に多少似ていますが、アプリケーションの使用パターンにも適応します。最悪の場合の O(n) 動作に遭遇することはほとんどありません。
良いボーナスは、他の自己均衡二分木よりも書きやすく、必要なコードが少ないことです。これは、実際に非常に優れたパフォーマンスを発揮するため、私のお気に入りのデータ構造の 1 つです。
グラフは、見過ごされがちな非常に強力なデータ構造です。
多くの問題は、問題をモデル化したグラフを作成し、そのグラフに対してよく知られたアルゴリズムを使用することで解決できます。たとえば、自然言語処理 (ノードを接続するエッジの重みは、ある単語が別の単語に続く可能性を表すことができます)、ビデオ ゲーム (グラフを使用して AI キャラクターの最短経路を決定します)、およびネットワーク トポロジです。
Steve Yegge がブログ投稿で推奨したThe Algorithm Design Manualからグラフについて学びました。
オブジェクト指向プログラミングではそれほどではありませんが、私は常にスタックの無数の用途を見つけてきました。実際、すべてのデータ構造には用途があり、複雑ではありません。あなたができるすべてを学びます。
ここに一般的な答えはないと思います。いくつかのユースケースに限定する必要があります。たとえば、プログラマー/マネージャーとしての10年以上のキャリアの中で、私は二分木を使用したことがありません。これは、バイナリツリーが役に立たないことを意味するのではないかと思いますが、カーネルと組み込みの世界では、リンクリストの方がおそらく適しています。
実際、いくつかの例外を削除することを考えるとき、私は単純なリンクリストのみを使用しました。
そして、組み込みでさえ、おそらくそれは私が低レベルのハードウェアプロトコルの世界に住んでいる唯一の構造ではなく、おそらく「丘を登る」より多くのデータ構造が使用されています...
これは、大工さんの道具箱にあるどの道具が使いこなすのに最適かを尋ねるようなものです。それぞれが特定の種類の仕事に適しているため、基本的なもの (マップ、リスト、バッグ、セットなど) を均等に学習する必要があります。
知っておくべきデータ構造は 1 つではないと思います。各データ構造には独自のプロパティがあり、特定の問題に適しています。
基本的な評価として、いくつかの抽象データ型 (セット、ディクショナリ、順序付きリスト、キュー、スタックなど) と、それぞれの相対的なトレードオフを実装するいくつかの方法を知っておく必要があります。
これにはおそらく、配列、連結リスト (一重および二重連結)、ハッシュ テーブル、二分探索木 (単純なバランス ヒューリスティックをある程度理解した上で)、およびバイナリ ヒープを理解する必要があります。これらを完全に理解することで、より複雑で興味深いデータ構造を理解するための長い道のりを歩むことができます。さらに、それらすべてを実装すると、プログラミング プロジェクト用に理解できる既製のライブラリが得られます (ただし、明らかに、Boost などのより強化されたライブラリや、生産コードにより適したものは何でもあります)。
これにより、データ構造の非常に便利な語彙が得られ、プログラムの作成方法に大きな違いが生じる可能性があります。キューの多くの部分的な実装で問題を解決してきたことに気付くかもしれません。たとえば、正規の実装に置き換えることができます。
この投稿は漠然としすぎています。配列、辞書など、無数のデータ構造があります。各データ構造を使用して、さまざまな問題を解決できます。
特定の問題について DS に依頼する方がはるかに生産的です。
クイックソート
マージソート
バブルソート
これらは、それらがどのように機能するかを学び、理解するのに非常に役立ちます。並べ替えは楽しく、多くの分野に適用できます:)