コレクションの使用に関するヒント

1. コレクション一覧

覚えているかもしれませんが、Java にはコレクションがあり、同じタイプのオブジェクトを保存するための便利なツールです。

主なコレクション関連のインターフェイスを思い出してみましょう。

リスト、セット、マップ、キュー。

いつものことですが、ツールは必ずしも良いか悪いかというとそうではありません。重要なのは、そのツールを本来の目的に使用しているかどうかです。そのためには、どのコレクションをいつ使用するかを判断するために、その特定の機能を徹底的に理解する必要があります。

1. リスト

最もよく使用されるコレクションから始めましょう。

単純な古い配列にできるだけ近いリストをリストします。

このコレクションを使用すると、配列を使用する場合のようにコレクション自体のサイズを気にすることなく、同じ型のオブジェクトのリストを簡単に保存できます。コレクションの要素にはインデックスによってアクセスします。オブジェクトの場所が正確にわかっていて、頻繁に要素を追加または削除する必要がなく、頻繁にアクセスする必要がある場合は、リストが理想的です。

2.セット

セットの構造は全く異なります。

Set は、固有のオブジェクトを保存する必要がある場合に最適です。たとえば、各著者が固有である図書館内の一連の著者。しかし、そこから特定の著者をただ取得することはできません。Setを使用すると、特定の作成者がライブラリに存在するかどうかをすばやく確認できます。つまり、一意のオブジェクトが Set に存在するかどうかを確認できます。コレクション全体を反復処理して各要素にアクセスすることもできますが、それは最適ではありません。

言い換えれば、私たちのライブラリの場合、セットはすべての一意の著者のコレクションを表すことができ、特定の著者が存在するかどうかをすぐに確認できます。

3. 地図

マップはファイル キャビネットに似ており、各ファイルが署名され、個々のオブジェクトまたは構造全体を保存できます。Map は、ある値から別の値へのマッピングを維持する必要がある場合に使用する必要があります。

Mapの場合、これらの関係はキーと値のペアと呼ばれます。

著者オブジェクトをキーとして使用し、書籍のリスト ( Listオブジェクト) を値として使用することで、この構造をライブラリで使用できます。したがって、Setをチェックして著者オブジェクトがライブラリに存在するかどうかを確認した後、同じ著者オブジェクトを使用してMapからその著者の書籍のListを取得できます。

4. 待ち行列

Queue は、驚くべきコレクションです。— キューの動作を実装します。また、キューはLIFO (後入れ先出し) またはFIFO (先入れ先出し) のいずれかになります。さらに、キューは双方向、つまり「ダブルエンド」にすることができます。

この構造は、クラスに追加されたオブジェクトを受信した順序で使用する必要がある場合に役立ちます。たとえば、私たちの図書館を考えてみましょう。

新しく到着した訪問者をキューに追加し、順番にサービスを提供し、目的の書籍を発行します。

ご覧のとおり、これらの構造はそれぞれ、意図された目的に使用されれば優れたものになります。そして、1 つのライブラリの例で 4 種類のコレクションすべての有効な使用法が見つかりました。

2. 複雑さ

すでに述べたように、上で検討したコレクションはインターフェイスです。つまり、コレクションを使用するには実装が必要です。

顕微鏡を使って釘を打つことが最良のアイデアではないのと同様に、コレクションのすべての実装がすべての状況に適しているわけではありません。

業務に適したツールを選択するときは、通常、次の 2 つの特性に注目します。

• ツールは仕事にどの程度適合しますか?
• どのくらいの速さで仕事が完了しますか?

私たちは仕事に適したツールを選択する方法を見つけるのにしばらく時間を費やしてきましたが、そのスピードは新しいものです。

コンピューティングでは、ツールの速度は時間計算量の観点から表現されることが多く、大文字の O で表されます。

時間計算量とは一体何でしょうか?

簡単に言えば、時間計算量は、コレクション内のアルゴリズムが特定のアクション (要素の追加/削除、要素の検索) を実行するのに必要な時間を示します。

ArrayList と LinkedList の比較

Listインターフェイスの 2 つの実装、ArrayListとLinkedListを使用してこれを見てみましょう。

外見上、これらのコレクションの操作は次のように似ています。

List<String> arrayList = new ArrayList<>();
arrayList.add(String);
arrayList.get(index);
arrayList.remove(index);
arrayList.remove(String);
 
List<String> linkedList = new LinkedList<>();
 
linkedList.add(String);
 
linkedList.get(index);
linkedList.remove(index);
linkedList.remove(String);
    

ご覧のとおり、どちらのコレクション型でも、要素の追加、取得、削除は同じように見えます。これは、これらが同じインターフェイス上の実装であるためです。しかし、類似点はそこまでです。

Listインターフェイスの実装が異なるため、これら 2 つの構造は、他の構造よりも異なるアクションをより効率的に実行します。

要素の削除と追加を検討してください。

ArrayListの途中から要素を削除する必要がある場合は、削除する要素に続くリストの部分を上書きする必要があります。

5 つの要素のリストがあり、3 番目の要素を削除したいとします。

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
list.remove(2);
    

この場合、削除により 1 つのセルが解放されるため、3 番目があった場所に 4 番目の要素を書き込み、4 番目があった場所に 5 番目の要素を書き込む必要があります。

これは非常に非効率的です。

リストの途中に要素を追加する場合も同じことが起こります。

LinkedList は異なる構造になっています。要素の追加または削除は、前後の要素の参照を変更するだけで済むため、高速です。これにより、要素のチェーンから削除するオブジェクトが除外されます。

5 つの要素からなる同じリストの例に戻ると、3 番目の要素を削除した後は、2 番目の要素の参照を次の要素に変更し、4 番目の要素の参照を前の要素に変更するだけです。

要素がリストに追加されると、同じプロセスが逆に行われます。

ArrayListと比較して、LinkedListで行う必要がある作業がどれほど少ないかに注目してください。それはたったの5つの要素です。リストの要素数が 100 以上になると、LinkedListの優位性がさらに顕著になります。

しかし、インデックスによって要素にアクセスすると、状況はどう変わるでしょうか?

ここではすべてが正反対です。

ArrayList は通常の配列として構造化されているため、インデックスによって要素を取得するのは非常に簡単です。ポインタを特定の場所に移動し、対応するセルから要素を取得するだけです。

しかし、LinkedList はそのようには機能しません。特定のインデックスを持つ要素を見つけるには、リストのすべての要素を調べなければなりません。

これらすべてをビッグオーの観点から表現してみませんか?

まずはインデックスによって要素にアクセスしましょう。

ArrayListでは、要素がリスト内のどこにあるかに関係なく、これは 1 ステップで行われます。終わりでも始まりでも。

この場合、時間計算量はO(1)になります。

LinkedListでは、必要なインデックスの値と同じ数の要素を反復処理する必要があります。

このようなアクションの時間計算量はO(n)です。ここで、 n は必要な要素のインデックスです。

ここで、大括弧内に入れた数字が、実行されたアクションの数に対応していることがわかります。

シェルの削除と追加に戻りますか?

LinkedList から始めましょう。

要素を追加または削除するために多数のアクションを実行する必要はなく、この操作の速度は要素が配置されている場所にまったく依存しないため、複雑さは O(1) で表され、次のように言われます。一定であること。

ArrayListに対するこの操作の時間計算量もO(n)であり、これを線形計算量と呼びます。

線形複雑さのアルゴリズムでは、実行時間は処理される要素の数に直接依存します。また、要素の位置 (リストの先頭か末尾か) にも依存する場合があります。

時間計算量は対数になることもあります。これはO(log n)として表されます。

例として、10 個の数値で構成されるソートされたTreeSetを考えてみましょう。私たちは番号 2 を見つけたいと思っています。

リストはソートされており重複が含まれていないため、リストを半分に分割し、どちらの半分に目的の数値が含まれるかを確認し、無関係な部分を破棄して、目的の要素に到達するまでこのプロセスを繰り返すことができます。最終的には、log(n) 個の要素を処理した後にその数値が見つかります (または見つからないこともあります)。

以下の表は、残りのコレクションの時間計算量をまとめたものです。

人気のあるコレクションの時間計算量を示す表ができたので、なぜ非常に多くのコレクションの中でArrayList、HashSet、およびHashMap を最も頻繁に使用するのかという質問に答えることができます。

それは単に、それらがほとんどのタスクにとって最も効率的であるということです:)