パート1.線形構造

配列

1つのオブジェクトが必要な場合、1つのオブジェクトを作成します。 複数のオブジェクトが必要な場合は、いくつかのオプションから選択できます。 コードの新人が次のように書いているのを見ました：

//   int score1 = 0; int score2 = 0; int score3 = 0; int score4 = 0; int score5 = 0;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これにより、5つのレコードの値が得られます。 このメソッドは、50個または100個のオブジェクトが必要になるまでうまく機能します。 個々のオブジェクトを作成する代わりに、配列を使用できます。

 //   const int NUM_HIGH_SCORES = 5; int highScore[NUM_HIGH_SCORES] = {0};
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次のように、5つの要素のバッファーが作成されます。











配列のインデックスはゼロから始まることに注意してください。 配列に5つの要素がある場合、それらの要素のインデックスは0〜4になります。

単純な配列の欠点

一定数のオブジェクトが必要な場合、配列は非常に適しています。 しかし、別の要素を配列に追加する必要があるとします。 単純な配列では、これを行うことはできません。 配列から要素を削除する必要があるとしましょう。 単純な配列では、これも不可能です。 1つの数量の要素に関連付けられます。 サイズを変更できる配列が必要です。 したがって、選択する方が良い...

動的配列

動的配列は、サイズを変更できる配列です。 標準ライブラリの主要なプログラミング言語は、動的配列をサポートしています。 C ++では、これはvectorです。 Javaでは、これはArrayListです 。 C＃では、これはListです。 それらはすべて動的配列です。 コアでは、動的配列は単純な配列ですが、2つの追加データブロックがあります。 単純な配列の実際のサイズと、単純な配列に実際に格納できるデータの量を格納します。 動的配列は次のようになります。

 //      sometype *internalArray; unsigned int currentLength; unsigned int maxCapacity;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

internalArray要素は、動的に割り当てられたバッファを指します。 有効なバッファ配列はmaxCapacityに保存されます 。 使用される要素の数はcurrentLengthで指定されます 。

動的配列に追加する

オブジェクトを動的配列に追加すると、いくつかのアクションが発生します。 配列クラスは、十分なスペースがあるかどうかを確認します。 currentLength <maxCapacityの場合、配列に追加する余地があります。 十分なスペースがない場合、より大きな内部配列が配置され、すべてが新しい内部配列にコピーされます。 maxCapacity値は、新しい拡張値に増加します。 十分なスペースがある場合、新しい要素が追加されます。 挿入ポイントの後の各要素は、内部配列の隣接する場所にコピーする必要があります。コピーが完了すると、ボイドは新しいオブジェクトで埋められ、 currentLengthの値が1つ増えます。











挿入ポイントの後に各オブジェクトを移動する必要があるため、最後に要素を追加することをお勧めします。 この場合、ゼロ要素を移動する必要があります（ただし、内部配列は引き続き拡張する必要があります）。 動的配列は、要素を中央ではなく最後に追加するときに最適に機能します。

オブジェクトを動的配列に追加すると、各オブジェクトはメモリ内を移動できます。 CやC ++などの言語では、動的配列に追加すると、配列オブジェクトへのすべてのポインターが無効になります。

動的配列から削除する

オブジェクトを削除する場合、追加するよりも作業が少なくて済みます。 まず、オブジェクト自体が破棄されます。 第二に、このポイントの後の各オブジェクトは1つの要素だけシフトされます。 最後に、currentLengthは1つ減少します。











配列の末尾に追加する場合と同様に、配列の末尾から削除するのが最適です。これは、オブジェクトをゼロ移動する必要があるためです。 また、内部配列のサイズを小さくしてサイズを小さくする必要がないことも注目に値します。 後でオブジェクトを追加する場合、割り当てられたスペースは同じままである場合があります。

動的配列からオブジェクトを削除すると、削除された要素の後のすべてのメモリがオフセットされます。 CやC ++などの言語では、動的配列から削除すると、削除された配列の後のすべてへのポインターが無効になります。

動的配列の欠点

配列が非常に大きく、多くの場合、オブジェクトを追加および削除する必要があるとします。 さらに、オブジェクトは他の場所にコピーされることが多く、多くのポインターが無効になります。 動的配列の途中で頻繁に変更する必要がある場合は、これに適した線形データ構造のタイプがあります...

リンクリスト

配列はメモリの連続ブロックであり、各要素は次から次へと配置されます。 リンクリストは、オブジェクトのチェーンです。 リンクリストは、主要なプログラミング言語の標準ライブラリにも存在します。 C ++では、それらはlistと呼ばれます 。 JavaおよびC＃では、これはLinkedListです。 リンクリストは、一連のノードで構成されます。 各ノードは次のようになります。

 //    sometype data; Node* next;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このタイプの構造を作成します。











各ノードは次のものに接続します。

リンクリストに追加する

リンクリストへのオブジェクトの追加は、新しいノードの作成から始まります。 データはノードの内部にコピーされます。 次に、挿入ポイントがあります。 次のオブジェクトへの新しいノードのポインターは、その後の次のノードを指すように変更されます。 最後に、新しいノードの前にあるノードは、新しいノードを指すようにポインターを変更します。

リンクリストから削除する

リンクリストからオブジェクトが削除されると、ノードは削除されるノードの前になります。 削除されたオブジェクトの次のノードを指すように変更されます。 その後、削除されたオブジェクトは安全に消去できます。

リンクリストの利点

リンクリストの最大の利点は、リストへのオブジェクトの追加と削除です。 リストの中央を変更するのは非常に高速です。 動的配列は理論的に各要素のオフセットを引き起こす可能性があり、リンクリストは他のすべてのオブジェクトをその場所に保持することに注意してください。

リンクされたリストの欠点

動的配列はメモリの連続ブロックであることを思い出してください。



配列の500番目の要素を取得する必要がある場合は、500個の「場所」を先に見てください。 リンクリストでは、メモリが連鎖されます。 500番目の要素を見つける必要がある場合は、チェーンの先頭から開始し、そのポインタを次の要素に移動し、次に次の要素に移動するなど、500回繰り返す必要があります。



リンクリストへのランダムアクセスは非常に遅いです。



リンクリストの別の重大な欠点は特に明らかではありません。 各ノードには少し余分なスペースが必要です。 彼はどのくらいのスペースが必要ですか？ ポインタのサイズだけが必要だと思うかもしれませんが、これは完全に真実ではありません。 オブジェクトを動的に作成する場合、常に小さなマージンがあります。 C ++などの一部のプログラミング言語は、メモリページで動作します。 通常、ページは4キロバイトかかります。 追加および削除演算子を使用すると、1バイトのみを使用する必要がある場合でも、メモリのページ全体が割り当てられます。



JavaとC＃では、すべてが少し異なって配置され、小さなオブジェクト用の特別なルールがあります。 これらの言語は4キロバイトのメモリページ全体を必要としませんが、それでもわずかなマージンがあります。 標準ライブラリを使用する場合、2番目の欠点を心配する必要はありません。 無駄なスペースを最小限に抑えるように書かれています。

おわりに

これら3つのタイプ（配列、動的配列、およびリンクリスト）は、より複雑なデータコンテナーのほぼすべての基礎を形成します。 大学で勉強するとき、データ構造の研究における最初のタスクの1つは、動的配列とリンクリストのクラスの独自の実装です。



これらの構造はプログラミングの基本です。 どんな言語を勉強しても、それを使ってデータを操作します。

パート2.エンドポイントを持つ線形データ構造

スタック

たくさんの紙があると想像してください。



1枚のシートをスタックに入れます。 これで、トップシートにのみアクセスできます。



別のシートをスタックに入れます。 前のシートは非表示になり、アクセスできなくなりました。トップシートを使用できます。 トップシートを完成したら、スタックからそれを削除して、下のシートにアクセスできるようにします。



これがスタックの考え方です。 スタックはLIFO構造です。 これは後入れ先出しの略です。 スタックに追加およびスタックから削除すると、最後に追加されたアイテムが最初に削除されます。



スタックに必要な操作は、プッシュ、ポップ、およびトップの3つだけです。



プッシュは、オブジェクトをスタックにプッシュします。 ポップは、スタックからオブジェクトを削除します。 Topは、スタック上の最新のオブジェクトを提供します。 ほとんどの言語のこれらのコンテナは、標準ライブラリの一部です。 C ++では、これらはstackと呼ばれます 。 JavaおよびC＃では、これはスタックです。 （はい、名前の唯一の違いは大文字です。）スタックの内部は、多くの場合、動的配列として実装されます。 このデータ構造から思い出すと、動的配列での最速の操作は、要素の追加と削除です。 スタックは常に最後に追加および削除するため、通常、スタック上のオブジェクトのプッシュおよびポップは非常に高速です。

キュー

あなたが何かのために並んでいると想像してください。



列に並んでいる最初の人が出され、その後彼は去ります。 その後、それが提供され、2番目が並んでいます。 他の人々が列になって、その端に立っています。 これは、キューのデータ構造の考え方です。











キューはFIFO構造です（先入れ先出し、「先入れ先出し」）。



キューに追加およびキューから削除すると、最初に追加されるアイテムが最初に取得されます。 キューに必要な操作は、Push_Back、Pop_Front、Front、およびBackだけです。 Push_Backは、アイテムをキューの最後に追加します。 Pop_Frontは、キューの先頭から要素を削除します。 フロントとバックを使用すると、キューの両端にアクセスできます。



多くの場合、プログラマはキューの両端から要素を追加または削除する必要があります。 このような構造は、両端キュー、両端キューと呼ばれます。 この場合、Push_FrontとPop_Backの操作がさらに追加されます。 これらのコンテナは、ほとんどの主要言語にも含まれています。 C ++では、これらはqueueおよびdequeです。 Javaは、キューと双方向キューのインターフェースを定義し、それらをLinkedListを介して実装します。 C＃にはQueueクラスがありますが、Dequeクラスはありません。



キューと両面キューの内部は非常に複雑になる可能性があります。 オブジェクトはどちらの端からでも行き来できるので、内側のコンテナはキューを最初と最後から大きくしたり短くしたりできなければなりません。 多くの実装は、メモリの複数のページを使用します。 どちらかの端が現在のページを超えて大きくなると、追加のページが追加されます。 ページが不要になった場合、削除されます。 Javaは次の方法を使用します。リンクリストにはメモリページではなく、少し余分なメモリが必要ですが、この言語ではこの実装は非常にうまく機能します。

優先キュー

これは、キューの非常に一般的なバリエーションです。 優先キューは、通常のキューに非常に似ています。



プログラムは、最後から要素を追加し、最初から要素を抽出します。 違いは、キューの特定の要素に優先順位を付けることができることです。 最も重要な要素はすべてFIFO順に処理されます。 次に、FIFOの順序で、優先度の低い要素が処理されます。 したがって、優先度が最も低い要素がFIFO順に処理されるまで繰り返します。



キューの残りの部分よりも高い優先度で新しいアイテムを追加すると、すぐにキューの一番上に移動します。 C ++では、この構造はpriority_queueと呼ばれます 。 Javaでは、これはPriorityQueueです。 C＃標準ライブラリには優先キューはありません。 優先キューは、組織のプリンターの最初に並ぶだけでなく、便利です。 これらは、検索手順A *などのアルゴリズムの便利な実装に使用できます。 最も可能性の高い結果には、より高い優先順位、より低い可能性-低い優先順位を与えることができます。 A *検索をソートおよび整理するための独自のシステムを作成できますが、組み込みの優先度キューを使用する方がはるかに簡単です。

おわりに

スタック、キュー、双方向キュー、および優先度キューは、他のデータ構造に基づいて実装できます。 これらは基本的なデータ構造ではありませんが、よく使用されます。 有限データ要素のみで作業する必要がある場合に非常に効果的であり、中間要素は重要ではありません。

パート3.ツリーとヒープ。

ツリーのデータ構造

データツリーは多くの場合に非常に役立ちます。 ビデオゲームの開発では、ツリー構造を使用してスペースを細分化し、開発者はゲームワールドの各オブジェクトをチェックすることなく、近くのオブジェクトをすばやく見つけることができます。 ツリー構造はコンピュータサイエンスの基本ですが、実際には、ほとんどの標準ライブラリはツリーベースのコンテナを直接実装していません。 その理由を詳しく説明します。

シンプルなツリー

木は…木です。 実際のツリーにはルート、ブランチがあり、ブランチの端には葉があります。











ツリーデータ構造はルートノードから始まります。 各ノードは子ノードに分岐できます。 ノードに子がない場合、リーフノードと呼ばれます。 複数の木がある場合、これはフォレストと呼ばれます。 これがツリーの例です。 実際のツリーとは異なり、それらは上から下に成長します。通常、ルートノードは上から描画され、葉は下から描画されます。











最初の質問の1つは、各ノードが子をいくつ持つことができるかということです。



多くのツリーには、2つ以下の子ノードがあります。 それらは二分木と呼ばれます。 上記の例は、バイナリツリーを示しています。 通常、子は左右の子ノードと呼ばれます。 ゲームで一般的な別のツリータイプは、4つの子ノードを持つツリーです。 グリッドをカバーするために使用できるクアッドツリーツリーでは、通常、ドーターノードは閉じる方向に名前が付けられます：NorthWest（北西）またはNW、NorthEast（北東）またはNE、SouthWest（南西）またはSW南東（南東）またはSE。



ツリーは多くのアルゴリズムで使用されています（すでにバイナリツリーについて説明しました）。 バランスの取れたツリーとアンバランスのツリーがあります。 赤黒木、AVL木、および他の多くがあります。



ツリー理論は便利ではありますが、ストレージスペースとアクセス速度という深刻な欠陥に悩まされています。 ツリーを保存する最良の方法は何ですか？ 最も簡単な方法は、リンクされたリストを作成することです;それは最悪であることが判明しました。 バランスの取れたバイナリツリーを構築する必要があるとします。 以下のデータ構造から始めます。

 //   Node* left; Node* right; sometype data;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

簡単です。 ここで、1024個の要素を格納する必要があると想像してください。 次に、1024個のノードの場合、2048個のポインターを保存する必要があります。



これは正常で、ポインタは小さく、少しのスペースでできます。



オブジェクトを配置するたびに、追加のリソースのごく一部が使用されることを覚えているかもしれません。 追加のリソースの正確な量は、使用している言語のライブラリによって異なります。 多くの一般的なコンパイラとツールでは、データを格納するためのほんの数バイトからデバッグを簡素化するための数キロバイトまで、さまざまなオプションを使用できます。 割り当てに少なくとも4 KBのメモリが必要なシステムで作業しました。 この場合、1024要素には約4 MBのメモリが必要です。 通常、状況はそれほど悪くありませんが、多くの小さなオブジェクトを格納するための追加コストは非常に急速に増加しています。



2番目の問題は速度です。 オブジェクトがメモリ内に隣接している場合、これが好きなプロセッサ。 最新のプロセッサには、非常に高速なメモリ（キャッシュ）があり、ほとんどのデータで非常にうまく機能します。 プログラムが単一のデータを必要とする場合、キャッシュはこの要素とその隣の要素をロードします。 データが非常に高速なメモリにロードされない場合（これは「キャッシュミス」と呼ばれます）、プログラムは作業を一時停止し、データのロードを待機します。 最も明白な形式では、ツリーの各要素が独自のメモリに格納されている場合、それらの要素の1つが他の要素の隣にあるわけではありません。 ツリーがトラバースされるたびに、プログラムは一時停止します。



ツリーの作成がそのような問題に直接関連している場合、ツリーのように機能するデータ構造を選択する必要がありますが、欠点はありません。 そして、この構造は呼ばれています...

束

混乱させるために、2種類のヒープがあると言います。



1つはメモリ内のヒープです。 これは、オブジェクトが格納されるメモリの大きなブロックです。 ただし、別のヒープについて説明します。



ヒープデータ構造は、本質的にツリーと同じです。 ルートノード、各ノードに子ノードなどがあります。 ヒープは制限を追加するため、ソートは常に特定の順序で実行する必要があります。 ソート関数が必要です-通常は「より小さい」演算子です。



ヒープにオブジェクトを追加または削除すると、構造はそれ自体をソートして「完全な」ツリーになります。ツリーの各レベルは、すべてが片側にシフトされる最後の行のみを除いて埋められます。 これにより、ストレージ領域とヒープ検索を非常に効率的に提供できます。



ヒープは、単純な配列または動的な配列に格納できます。つまり、配置に使用されるスペースはほとんどありません。 C ++には、独自の開発者コンテナにヒープを実装できるpush_heap（）やpop_heap（）などの関数があります。 標準のJavaおよびC＃ライブラリには、同様の機能はありません。 同じ情報を持つツリーと束を次に示します。

標準ライブラリにない理由

これらは、シンプルで基本的な非常に便利なデータ構造です。 多くの人々は、標準ライブラリに存在すべきだと考えています。数秒で、検索エンジンで何千ものツリー実装を見つけることができます。



木は非常に有用で基本的ですが、より良いコンテナがあることがわかります。ツリーの利点（安定性と形状）とヒープの利点（スペースと速度）を備えた、より複雑なデータ構造があります。より高度なデータ構造は、通常、データテーブルとルックアップテーブルの組み合わせです。 2つのテーブルを組み合わせることで、迅速なアクセス、迅速な変更が可能になり、タイトな状況でもルーズな状況でも明確に現れます。要素を追加および削除するときに要素を転送する必要がなく、不要なメモリを消費せず、長時間使用してもメモリを断片化しません。

おわりに

「ツリー」データ構造について知っておくことが重要です。これは、仕事では頻繁に使用する必要があるためです。また、これらのデータ構造は、直接実装されたときに不利な点があることを知ることも重要です。独自のツリー構造を実装できますが、よりコンパクトな型があることを知ってください。標準ライブラリで実際に使用されていないのに、なぜそれらについて話したのですか？次のトピックで内部構造として使用されます。

パート4.非線形データ構造。

これらのデータ構造は、配列やリストとは異なります。配列は順次コンテナーです。それらの要素は順番に配置されます。特定の順序で複数のアイテムを追加すると、それらはその順序のままになります。



非線形データ構造は、必ずしも追加された順序のままになるとは限りません。アイテムを追加または削除すると、他のアイテムの順序が変わる場合があります。内部では、前の部分で説明したツリーとヒープで構成されています。



このようなデータ構造には多くのバリエーションがあります。最も基本的なのは、データディクショナリと、順序付きおよび無秩序なセットです。

データ辞書

通常の辞書は、一連の単語（キー）と定義（値）で構成されます。キーはアルファベット順になっているため、どのアイテムでも非常にすばやく見つけることができます。



辞書がソートされていない場合、その中の単語を見つけることは非常に困難でした。



辞書内の項目を並べ替えるには、比較またはハッシュの2つの主な方法があります。従来の比較によるシーケンスは、通常、より直感的です。これは、すべてがアルファベット順または番号順にソートされている紙の辞書順のように見えます。



この方法でアイテムをソートする場合、比較関数が必要になる場合があります。通常、この関数はデフォルトでは「小なり」演算子です（たとえば<b）。



アイテムをソートする2番目の方法は、ハッシュを使用することです。ハッシュは、単にデータブロックを単一の数値に変換する方法です。たとえば、文字列「blue」のハッシュは0xa66b370dで、文字列「red」のハッシュは0x3a72d292です。データディクショナリがハッシュを使用する場合、通常はソートされていないと見なされます。実際、それは依然として、人にとって便利な基準ではなく、ハッシュでソートされています。データディクショナリも同様に機能します。辞書の使用と従来のソートとハッシュソートの速度にはわずかな違いがあります。違いは非常に小さいため、無視できます。



C ++には、コンテナファミリmap / mutimapまたはunordered_map / unordered_multimapがあります。 Javaでは、ファミリーはHashMapと呼ばれます。TreeMapのかのLinkedHashMap。 C＃では、これはDictionaryまたはSortedDictionaryです。それぞれに独自の実装機能があります。たとえば、ハッシュまたは比較によるソート、重複の仮定がありますが、一般的には概念は同じです。各標準ライブラリには、順序付けされたバージョン（比較が指定されている）と順序付けされていないバージョン（ハッシュ関数が使用される）があることに注意してください。データディクショナリにアイテムを追加した後、値を変更できますが、キーは変更できません。



紙の辞書の類推に戻りましょう。本の中で単語を動かさずに単語の定義を変更できます。単語のスペルを変更した場合、最初のスペルを削除して、新しいスペルで単語を再挿入する必要があります。教科書で作品の詳細を調べることができます。辞書はデータを検索するときは非常に高速で、値を追加または削除するときは非常に遅くなる可能性があることを知るだけで十分です。

順序付きおよび順序なしセット

順序付きセットは辞書とほぼ同じです。キーと値の代わりに、キーのみがあります。単語と定義を含む従来の辞書の代わりに、単語のみがあります。多くは、追加データなしで単語のみを保存する必要がある場合に便利です。 C ++では、構造のファミリーはset / multisetまたはunordered_set / unordered_multisetと呼ばれます。 Javaでは、HashSet、TreeSet、またはLinkedHashSetです。 C＃では、これらはHashSetおよびSortedSetと呼ばれます。



辞書と同様に、順序付けされたバージョン（比較が指定されている場合）と順序付けされていないバージョン（ハッシュ関数が使用されている場合）があります。キーを追加した後、変更することもできません。代わりに、古いオブジェクトを削除して新しいオブジェクトを挿入する必要があります。多くの場合、データディクショナリと同じ方法で実装され、値のみを保存します。それらは同じ方法で実装されるため、同じ特性を持ちます。値は非常に高速に検索され、セット内で検出されますが、要素を追加および削除するときの動作は遅くなります。

おわりに

データディクショナリのコンテナのクラス、順序付きセットと順序なしセットは、迅速なデータ取得に非常に役立ちます。多くの場合、これらはツリーまたはハッシュテーブルとして実装されますが、これはこの点で非常に効果的です。一度データを作成する必要があり、頻繁に参照する場合に使用します。要素の追加や削除にはあまり効果的ではありません。コンテナに変更を加えると、コンテナ内でシフトまたは並べ替えが発生する可能性があります。この使用パターンに従う必要がある場合は、順序付けられたリンクリストを選択することをお勧めします。

パート5.データ構造の正しい選択。

前のパートでは、最も一般的に使用されるデータ構造をリストしました。



簡単に繰り返します。



線形構造が存在します：配列、動的配列、および関連する配列。それらは、配置された順序のままであるため、線形です。配列はランダムアクセスで非常に高速で、最後に追加したり削除したりする際のパフォーマンスが比較的良好です。リンクリストは、頻繁に追加や削除が行われるため、非常に優れています。



エンドポイントを持つ線形データ構造があります：スタックとキューのファミリー。どちらも、実世界の対応物とほぼ同じように機能します。スタック、たとえばプレートのスタックやデータスタックでは、何かを押し上げることができ、最上部の要素にアクセスして、この要素を押すことができます。行と人の行は、行の末尾に追加して行の先頭から削除することで機能します。



次に、非線形データ構造があります。データ辞書、順序付けられた無秩序なセットです。それらはすべて内部的に非線形であり、追加する順序は、基本的にそれらを戻す順序とは関係ありません。データ辞書は、実際の紙の辞書とほぼ同じように機能します。彼には鍵（私たちが探している言葉）と意味（言葉の定義）があります。順序付きセットは、キーを含むが値を含まないデータディクショナリとまったく同じであり、ソートされます。順序付けられていないセットは、オブジェクトの単なる「バッグ」です。名前は少し紛らわしいです、なぜなら実際にはそれらは注文されているからです、ただ注文する方法は人にとって不便です。これらの構造はすべて、迅速な検索に最適です。

正しい選択の効果

ほとんどの場合、プログラマはデータセットを繰り返し処理する必要があります。



通常、セットが配置される順序は気にしません。最初から始めて各要素にアクセスするだけです。この非常に一般的な状況では、データ構造の選択はそれほど重要ではありません。



疑わしい場合は、通常、動的配列が最良の選択です。比較的中立でありながら、任意のボリュームに拡張できます。これにより、後で別のデータ構造に簡単に置き換えることができます。しかし、時には構造が非常に重要です。



ゲームで最も一般的なタスクの1つはパスを見つけることです。ポイントAからポイントBへのルートを見つける必要があります。最も一般的なパス検索アルゴリズムの1つはA *です。 A *アルゴリズムには、部分パスを含むデータ構造があります。構造は、最も可能性の高い部分パスがコンテナの前にあるようにソートされます。このパスが評価され、終了していない場合、アルゴリズムはこの部分パスをいくつかの大きな部分パスに変換し、コンテナに追加します。



このコンテナとして動的配列を使用するのは、いくつかの理由で適切ではありません。まず、動的配列の先頭から要素を削除することは、実行可能な最も遅い操作の1つです。第二に、追加するたびに動的配列を再ソートするのも遅くなります。上記から覚えているように、このタイプのアクセスに最適化されたデータ構造があります。最初から削除し、最後から追加し、最適なパスに基づいて自動ソートが実行されます。A *パスコンテナの理想的な選択は優先度キューであり、言語に組み込まれ、完全なデバッグを提供します。

パターンの選択

データ構造の選択は、主に使用パターンに依存します。

動的配列-デフォルトの選択

疑わしい場合は、動的配列を使用してください。C ++では、これはvectorです。Javaでは、これはArrayListと呼ばれます。C＃では、これはListです。一般に、動的配列が必要です。ほとんどの操作で高速であり、他のすべてのユーザーでも高速です。別のデータ構造が必要であることがわかった場合、そこから移動するのが最も簡単です。

スタックは片方だけです

片方だけから追加と削除を使用する場合は、スタックを選択します。このスタック C ++でスタック JavaやC＃インチ積み重ねられたデータ構造を使用する多くのアルゴリズムがあります。最初に思い浮かぶのは、2スタック計算機です。ハノイタワーなどの数値タスクは、スタックを使用して解決できます。ただし、おそらくゲームでこれらのアルゴリズムを使用することはないでしょう。ただし、多くの場合、ゲームツールはデータの解析を行い、パーサーはスタックされたデータ構造を積極的に使用して、要素ペアの正しい組み合わせを保証します。さまざまなAIタイプを扱う場合、スタックされたデータ構造はプッシュダウンオートマトンと呼ばれるマシンファミリーにとって非常に便利です。

待ち行列のファミリー-最初に来た人、最初に出た人。

両端のみを追加および削除する場合は、キューまたは双方向キューを使用します。C ++では、キューまたはdequeです。Javaでは、QueueまたはDequeインターフェースを使用できます。どちらもLinkedListを使用して実装されます。C＃にはQueueクラスがありますが、組み込みのDequeはありません。重要なイベントを最初に発生させたいが、それ以外はすべて順番に発生させたい場合は、優先度キューを選択します。C ++ではpriority_queue、JavaではPriorityQueueです。C＃では、自分で実装する必要があります。

非線形構造-クイック検索。

要素の安定したグループを作成し、基本的に任意の検索を実行する場合、非線形構造のいずれかを選択する必要があります。データペアを保存するものもあれば、個別のデータを含むものもあります。それらのいくつかは便利な形式でソートされ、他はコンピューターにとって便利な順序でソートされます。それらのすべての組み合わせのリストを作成しようとすると、別の記事を書く必要があります（または前の部分を再度読むことができます）。

リンクリスト-頻繁に変更を保持

コンテナの中央を頻繁に変更し、リストを順番に走査する必要がある場合は、リンクリストを使用します。 C ++では、listと呼ばれます。 JavaおよびC＃では、これはLinkedListです。リンクリストは、データが入ってくるばかりで順序を維持する必要がある場合や、アイテムを定期的に並べ替えたり移動したりする必要がある場合に最適なコンテナです。

おわりに

適切なデータ構造を選択すると、アルゴリズムの速度に大きく影響します。基本的なデータ構造、その長所と短所を理解することは、あらゆるタスクに最も効率的な構造を使用するのに役立ちます。最終的にそれらを詳細に研究することをお勧めします。コンピュータサイエンスを専攻する大学でこれらのデータ構造を完全に調査するには、通常数週間かかります。基本的なデータ構造を理解し、長期の大学滞在なしに適切なデータ構造を選択できることを願っています。



これで記事は終わりです。読んでくれてありがとう。