ツールを直接知る：最も一般的に使用されるデータ構造の概要

少し前に、私はある大規模で尊敬される会社にインタビューに行きました。 インタビューはうまくいき、私はそれを気に入ってくれました。 しかし、翌日、報告会の過程で、インタビュー中に少なくとも1つの質問に対する答えが間違っていることがわかりました。

質問：大量のデータのpython dictでの検索が、インデックス付き配列の繰り返し処理よりも速いのはなぜですか？

回答：dictはキーハッシュを保存します。 dict値のキーを検索するたびに、まずそのハッシュを計算し、次に（突然）バイナリ検索を実行します。 したがって、複雑さはO（log（N））です！

実際、ここにはバイナリ検索はありません。 そして、アルゴリズムの複雑さはO（log（N））ではなく、Amortです。 O（1）-python dictはハッシュテーブルと呼ばれる構造に基づいているため。

間違った答えの理由は、 私の好きな言語のコレクションを使って、作品の根底にある構造を徹底的に研究することを気にしなかったからです 。 確かに、いくつかのよく知られている開発者の調査によると、これは私の問題であるだけでなく、多くの人がお気に入りのPLでコレクションがどのように機能するかさえ考えていないことがわかりました。 しかし、私たちはそれらを一度ではなく毎日使用しています。 この記事のアイデアが生まれました。


記事内の構造の分類に関するいくつかの言葉。 使用済み情報のリストにリストされているソースを調べると、この記事の分類がどのソースの分類にも対応していないことに気付くでしょう（一部のソースではまったくありません）。 これは、構造体を使用するという文脈で構造体を検討する方が適切だと思われたためです。 たとえば、PHP / Python / C ++の連想配列または.Net / Pythonのリスト。

行きましょう。

1.配列-インデックス付き配列です。

配列は、同じタイプの要素で構成される固定サイズのコレクションです。

インターフェース：

• get_element_at（i）：O（1）複雑さ
• set_element_at（i、value）：O（1）複雑さ

配列内の検索は、インデックス=>複雑さO（N）で要素をソートすることにより実行されます。

アイテムのインデックスアクセス時間が一定なのはなぜですか？ 配列は同じ型の要素で構成され、サイズが固定されており、メモリの連続領域に配置されています=>配列のj番目の要素を取得するには、配列の先頭へのポインタを取得し、要素サイズにそのインデックスを掛けた値を追加するだけです。 この単純な計算の結果は、配列の目的の要素のみを指します。
*aj = beginPointer + elementSize*j-1


例：
/++: int i_array[10];
java/C#: int[10] i_array;
Python: array.array
php: SplFixedArray


2.リスト。

リストは、任意のタイプの可変長の要素のリストです（つまり、リストに要素を追加したり、いつでも削除したりできます）。 このリストを使用すると、アイテムを反復処理したり、インデックスでアイテムを取得したり、アイテムを追加および削除したりできます。 リストの実装は異なり、主なものは（単一/双方向）リンクリストとベクターです。 古典的なリストは、直接およびイテレータを介してそれを操作する機能を提供します;以下で両方のクラスのインターフェースを検討します。

リストインターフェイス：

• prepend（item）：リストの一番上にアイテムを追加します。
• append（item）：リストの最後にアイテムを追加します。
• insert_after（リスト反復子、アイテム）：現在のアイテムの後にアイテムを追加します。
• remove_firts（）：最初の要素を削除します。
• remove_after（リスト反復子）：現在のアイテムの後にあるアイテムを削除します。
• is_empty（）：リストは空です。
• get_size（）：リストのサイズを返します。
• get_nth（n）：n番目の要素を返します。
• set_nth（n、value）：値をn番目の要素に設定します。

リストイテレータインターフェイス：

• get_value（）：現在の要素の値を取得します。
• set_value（）：値を現在の要素に設定します。
• move_next（）：次のアイテムに移動します。
• equal（リスト反復子）：別の反復子が同じリスト項目を参照しているかどうかを確認します。

一部の（ほとんど解釈される）プログラミング言語では、これらの2つのインターフェイスが「接着」および「トリミング」されていることに注意してください。 たとえば、Pythonでは、リスト型のオブジェクトを反復できますが、インデックスから直接アクセスすることでリストから取得することもできます。

実装のリストに移りましょう。

2.1単一のリンクリスト

単方向リンクリスト（単一リンクリスト）は、コンテナのチェーンです。 各コンテナには、要素へのリンクと次のコンテナへのリンクが含まれているため、単一のリンクリストを常に前に進み、現在の要素の値を常に取得できます。 コンテナはメモリ内に配置することができます=>単純に接続されたリストに新しい要素を追加するのは簡単です。

運用コスト：

• 付加：O（1）
• insert_after：O（1）
• remove_first / remove_after：O（1）
• get_nth / set_nth：O（N）

例：
/++: std::list //Bidirectional Linked List
Java: java.util.LinkedList
c#: System.Collection.Generic.LinkedList //Bidirectional Linked List
php: SplDoublyLinkedList // Bidirectional Linked List


双方向リンクリストの詳細は考慮しませんが、双方向リンクリストと単一リンクリストの違いは、コンテナ内に次へのリンクだけでなく前のコンテナへのリンクがあることです。これにより、リスト内を前方だけでなく後方にも移動できます。

2.2ベクトル

Vectorは、インデックス配列の拡張によるListの実装です。

運用コスト：

• 付加：O（N）
• 追加：Amort.O（1）
• insert_after：O（N）
• remove_first / remove_after：O（1）
• get_nth / set_nth：O（1）

明らかに、ベクターの主な利点は、通常のインデックス付き配列から継承されたインデックスによる要素への迅速なアクセスです。 Vectorの反復も非常に簡単です。特定のカウンターを1つ増やし、インデックスでアクセスするだけです。 ただし、要素へのアクセス速度を上げるには、要素を追加する時間を支払う必要があります。 Vector'aの中央（挿入後）に要素を挿入するには、反復子の現在位置と配列の最後の間にあるすべての要素をコピーする必要があります。その結果、平均アクセス時間はO（N）になります。 配列の中央の要素を削除し、配列の先頭に要素を追加することでも同じです。 配列の最後に要素を追加することはO（1）で行うことができますが、できない場合があります-再び配列を新しい配列にコピーする必要がある場合、ベクターの最後に要素を追加することはAmortによって行われます。 O（1）。

例：
/++: std::vector
Java: java.util.ArrayList
C#: System.Collections.ArrayList, System.Collections.List
Python: list


3.連想配列（辞書/マップ）

キー=>値のペアのコレクション。 要素（値）には任意の型を指定できます。通常、キーは文字列/整数のみですが、実装によっては、キーとして使用できるオブジェクトの範囲を広げることができます。 連想配列のサイズは、要素を追加/削除することで変更できます。

インターフェース：

• add（key、value）-要素を追加します
• reassign（key、value）-要素を置き換える
• delete（キー）-アイテムを削除します
• ルックアップ（キー）-要素を見つける

連想配列には、HashMapとBinary Treeの2つの主要な実装があります。

3.1ハッシュテーブル

名前から推測できるように、ここではハッシュが使用されます。 ハッシュテーブルの仕組みは次のとおりです。キーからのハッシュ値がインデックスとして機能する同じインデックス付き配列に基づいており、値はキーと格納された要素（バケット）を含むオブジェクトへの参照です。 アイテムを追加するとき、ハッシュ関数はキーからハッシュを計算し、対応するインデックスを持つ配列セルに追加されるアイテムへのリンクを保存します。 要素にアクセスするには、再びキーからハッシュを取得し、通常の配列と同様に機能して、要素へのリンクを取得します。

好奇心reader盛な読者は、この糖尿病の実施に特有の問題に気付くかもしれません。

• キーからのハッシュが、たとえば1928132371827612に等しい場合、これは適切なサイズの配列が必要であることを意味しますか？ そして、要素が2つしかない場合はどうでしょうか？
• しかし、2つの異なるキーからのハッシュが一致したらどうなるでしょうか？

これらの2つの問題は関連しています：少数の要素を格納する場合、長いハッシュを計算できないことは明らかです-ハッシュ関数は通常次のようになるため、不当なメモリコストが発生します。
index = f(key, arrayLength)


つまり、キー値に加えて、配列の現在のサイズも受け取ります。これは、ハッシュの長さを決定するために必要です。3つの要素のみを格納する場合、長さ32ビットのハッシュを作成しても意味がありません。 ハッシュ関数のこの動作の裏側は、衝突の可能性です。 衝突は実際にはハッシュテーブルの特徴であり、衝突を解決するには2つの方法があります。

連鎖：

配列Hの各セルは、キーの同じハッシュ値に対応するキーと値のペアのリンクリスト（チェーン）へのポインターです。 衝突は、単純に1要素よりも長いチェーンの出現につながります。

オープンアドレス指定：

配列Hは、キーと値のペア自体を保存します。 要素挿入アルゴリズムは、新しい要素が書き込まれる最初の空きセルが見つかるまで、ある順序で配列Hのセルをチェックします。 この順序はオンザフライで計算され、チェーンを持つハッシュテーブルに必要なポインターのメモリを節約します。


運用コスト：

• 追加：Amort.O（1）/ O（N）
• 再署名：Amort.O（1）/ O（N）
• 削除：Amort.O（1）/ O（N）
• ルックアップ：Amort.O（1）/ O（N）

ここで、最初の値は平均複雑度、2番目は最悪の場合の操作の複雑度です。 この違いの原因は次のとおりです。要素を追加するときに、配列がいっぱいの場合、ハッシュテーブル全体を再構築する必要がある場合があります。 要素を検索すると、衝突の長い連鎖に出くわすことが判明する場合があります。また、すべての要素をソートする必要があります。

例：
c++: QHash boost::unordered_map/boost::unordered_set (by NickLion )
java: java.util.HashMap<K,V>
c#: System.Collections.Hashtable, System.Collections.Dictionary<K, V>
python: dict
php: array()


3.2バイナリツリー

実際には、バイナリツリーだけでなく、自己バランス型バイナリツリーもあります。 さらに、連想配列を実装するために使用できるいくつかの異なるツリーがあることに注意する必要があります：赤黒ツリー、AVLツリーなど。 これらのツリーはそれぞれ別の記事、または複数のトピック（おそらく非常に慎重にツリーを研究する場合）のトピックであるため、これらの各ツリーを詳細に検討することはしません。 一般的な原則のみを説明します。

定義：バイナリツリー-各ノードが2つ以下の子孫（子）を持つツリー状のデータ構造。 原則として、最初のノードは親ノードと呼ばれ、子は左と右の相続人と呼ばれます。 ノードに子孫がない場合、リーフノードと呼ばれます。

たとえば、バイナリ検索ツリーを見てみましょう。各ノードは、3つの要素を含むコンテナです。データ-実際に添付されたデータ（データには要素自体とキー値の両方が含まれます）、左-基になる左ノードと右へのリンク-適切な基になるノードへのリンク。 この場合、次のルールが満たされます：キー[左[X]] <キー[X]≤キー[右[X]]-つまり、親ノードのデータキーは左息子のデータキーより大きく、右息子のデータキーよりも緩やかに小さいです。 要素を検索するとき、キーの値を現在のノードのキーと比較するたびにツリーを一周し、比較の結果に基づいて、どの方向に進むべきかを決定します。 そのような検索の複雑さは安定してO（logN）であることを計算するのは簡単です。 新しいノードを追加するとき、新しい要素をどこに貼り付けるかを見つけるまで、一般的に同様の手順を実行します。 確かに、このようなツリーはまだバランスを取る必要があることに注意する必要がありますが、これは既に省略します。 好奇心reader盛な読者は、ソースのリストを調べて必要な情報を見つけます。

運用コスト：

• 追加：Amort.O（lgN）
• 再署名：Amort.O（lgN）
• 削除：Amort.O（lgN）
• ルックアップ：Amort.O（lgN）

例：
c++: std::map, std::set
java: java.util.TreeMap<K,V>, java.util.Map<K,V> -
c#: :( SortedDictionary(by NickLion )
python: -
php: -


4.セット。

要素の不変のセット。 セットは一度だけ定義されます-作成時に、その後要素への読み取り専用アクセスを提供します。 セットから要素を削除したり、セットの要素を変更したりすることが不可能であるように、セットを展開することはできません。 このコレクションを実装するためのベースとして、通常ハッシュテーブルが使用されます。ハッシュテーブルの説明は上記にあります。

セットは、単に数学的なセットの抽象化の実装です。 一意の区別可能な要素のセット。 （ ATP DanilI ）
例：
c++: std::set
java: java.util.Set
C#: System.Collections.HashSet
python: set/frozenset


データ構造の比較特性：


さまざまなプログラミング言語のデータ構造：

参照：

データ構造（en）
データ構造（rus）
バイナリ検索ツリー（en）
バイナリ検索ツリー（rus）

また、著者はPHPのソースコードを見て、 STLのドックを読みました。

更新しました。 はい、pythonには通常のインデックス付き配列（array.array）があります。 エンチャントナーに感謝します。 修正されたように、型は必ずしも数値ではなく、型を指定できます。

更新しました。 テキストで行われた多くの修正。 idemura 、 zibada 、 tzlom 、 SiGMan 、 freeOne 、 Slaffko 、 korvindest 、 Laplace 、編集者、編集者に感謝！

更新しました。
ジバダのコメントから：
はい、Mapイテレーションの説明がないという理由だけで、ハッシュがあるときにツリーが必要であると思われる理由は、記事からは一般に明確ではありません。 （O（logN）vs O（1））。

その場合、マップ（またはセット）要素をリストすることができます。
-保証されていない順序（HashMap、一部のスクリプト言語の組み込みハッシュ）。
-追加する順に（LinkedHashMap、他のスクリプト言語の組み込みハッシュ）;
-キーの昇順+特定の範囲内のキーのみを反復処理する機能。

ただし、後者の場合、ツリーに代わるものは、各変更後またはリクエストの前にコレクション全体を完全にソートすることです。
これは大きなコレクションでは長くて悲しいですが、小さなコレクションでは機能します。したがって、ツリーはスクリプト言語に特に埋め込まれていません。