Javaにおけるコレクションクラスの遍歴性能分析

5711 ワード

概要
Java言語では、リスト、Setなどの抽象データ型が定義され、各抽象データ型の各具体的な実装が定義され、下位層ではArrayListやLinkedListなどの異なる実装方式が採用されているデータセットフレームワークが提供されている.
このほか,Javaはデータセットの遍歴に対して,いくつかの異なる方法を提供している.開発者は、各遍歴方式の特徴、適用場面、および異なる下位実装における表現を明確に理解しなければならない.以下、この内容を詳しく分析します.
データ要素はどのようにメモリに保存されますか?
データ要素はメモリにあり、主に2種類のストレージ方式があります.
1、逐次記憶、Random Access(または直接記憶、Direct Access):
このように、隣接するデータ要素は隣接するメモリアドレスに格納され、メモリアドレス全体が連続している.要素の位置から直接メモリアドレスを算出し、直接読み取りを行うことができます.特定の位置要素を読み出す平均時間複雑度はO(1)である.このデータ構造は挿入や削除が面倒で、クエリーが便利です.通常,この特性は配列に基づいて実現される集合のみである.JavaではArrayListに代表される.
2、チェーンストレージ、Sequential Access:
この方法では、データ要素を独立した空間に配置し、メモリ内の各要素のメモリアドレスは隣接する必要はありません.したがって、各要素には、次の要素のインデックス、すなわち次の要素のメモリアドレスを保存する必要があります.したがって、このデータ構造は挿入と削除が便利ですが、検索が面倒で、要素の位置に基づいてメモリアドレスを直接計算することができず、要素を順番に読み取るしかありません.特定の位置要素を読み出す平均時間複雑度はO(n)である.主にチェーンテーブルに代表されます.JavaではLinkedListに代表される.
Javaで提供される遍歴方法はどれらがありますか?
1、従来のforサイクル遍歴、カウンタに基づく:
遍歴者は自分で集合の外部でカウンタを維持し、各位置の要素を順番に読み取り、最後の要素に読み込んだ後、停止します.主に要素の位置によって要素を読み取る必要があります.これも最も原始的な集合遍歴方法です.書き方:

for (int i = 0; i < list.size(); i++) {
    list.get(i); 
}

2、反復器遍歴、Iterator:
反復器(Iterator)モードは、カーソル(Cursor)モードとも呼ばれます.GOFは、オブジェクトの内部の詳細を露出することなく、コンテナオブジェクト内の各要素にアクセスする方法を提供すると定義しています.定義から分かるように、反復モードはコンテナのために生成されます.コンテナオブジェクトへのアクセスは、必然的に遍歴アルゴリズムに関連することが明らかになった.1つの方法は、遍歴方法を容器オブジェクトに詰めることです.もう一つの方法は、容器を使う人に自分で実現させることです.どちらも問題を解決できる.しかし、前の状況では、コンテナは過剰な機能を受けており、自分の「コンテナ」内の要素のメンテナンス(追加、削除など)だけでなく、自分のインタフェースも提供しています.また、遍歴状態が保存されているため、同じコンテナオブジェクトを同時に複数遍歴することはできません.2つ目の方法は手間が省けますが、容器の内部の細部を明らかにします.反復器モードの出現は,上記の2つのケースの弊害をよく解決した.IteratorはもともとOOの設計モードであり,主な目的は異なるデータ集合の特徴を遮蔽し,集合のインタフェースを統一することである.構造的には、反復モードがクライアントとコンテナの間に反復ロールを追加していることがわかります.反復器ロールの追加により、コンテナ内部の詳細の露出を回避し、設計シンボルの「単一職責原則」を回避できます.JavaはOO言語として、当然CollectionsでもIteratorモードをサポートしています.反復モードの書き方は次のとおりです.

Iterator iterator = list.iterator();
while (iterator.hasNext()) {
    iterator.next();
}

3、foreach循環遍歴:
foreach内部もIterator方式で実現され、明示的に宣言されたIteratorとカウンタを遮断している.利点:コードが簡潔で、エラーが発生しにくい.欠点:単純な遍歴しかできず、遍歴中にデータセットを操作(削除、置換)することはできません.書き方は以下の通りです.

for (ElementType element : list) {
}

各遍歴方法の実現原理は何ですか.
1、従来のforサイクル遍歴、カウンタに基づく:
遍歴者は自分で集合の外部でカウンタを維持し、各位置の要素を順番に読み取り、最後の要素に読み込んだ後、停止します.主に、要素の位置によって要素を読み取る必要があり、遍歴順に格納されるデータ構造に適しています.
2、反復器遍歴、Iterator:
各具体的に実装されるデータセットは、一般に対応するIteratorを提供する必要がある.従来のforサイクルに比べて、Iteratorは明示的な遍歴カウンタに取って代わった.したがって、シーケンスベースのコレクションを格納するIteratorは、直接位置別にデータにアクセスできます.一方、チェーンストレージセットに基づくIteratorでは、通常の実装では、現在のループの位置を保存し、現在の位置に基づいてポインタを前または後ろに移動する必要があります.
3、foreach循環遍歴:
逆コンパイルされたバイトコードによると、foreach内部もIterator方式で実現されているが、Javaコンパイラがこれらのコードを生成してくれただけだ.
各ループ方式は異なるストレージ方式に対して、性能はどうですか?
1、従来のforサイクル遍歴、カウンタに基づく:
要素ベースの位置なので、位置別に読み込みます.従って,シーケンス記憶では,特定の位置要素を読み出す平均時間複雑度がO(1)であるため,集合全体を巡る平均時間複雑度がO(n)であることが分かる.一方,チェーンストレージでは,特定の位置要素を読み取る平均時間複雑度はO(n)であるため,集合全体を巡る平均時間複雑度はO(n 2)である.ArrayListが位置によって読み取ったコード:直接要素の位置によって読み取った.

transient Object[] elementData;
public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}
E elementData(int index) {
    return (E) elementData[index];
}

LinkedListが位置別に読み取るコード:毎回0番目の要素から後ろに読み取る必要がありますが、内部は小さな最適化が行われています.

transient int size = 0;
transient Node first;
transient Node last;
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
Node node(int index) {
    if (index < (size >> 1)) { //           ，        
        Node x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else { //           ，        
        Node x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

2、反復器遍歴、Iterator:
では、RandomAccessタイプのセットでは、あまり意味がありません.逆に、いくつかの追加の操作のため、追加の実行時間が増加します.しかしSequential Accessの集合にとっては重大な意義があり,Iterator内部では現在の遍歴の位置が維持されているため,遍歴するたびに次の位置を読み取るには集合の最初の要素から探す必要はなく,ポインタを1桁後ろにシフトすればよいので,集合全体を遍歴する時間の複雑さはO(n)に低下する.LinkedListの反復器を例にとると、その内部実装は、現在遍歴している位置を維持し、ポインタを操作して移動すればよい:コード:

public E next() {
    checkForComodification();
    if (!hasNext())
        throw new NoSuchElementException();
    lastReturned = next;
    next = next.next;
    nextIndex++;
    return lastReturned.item;
}
public E previous() {
    checkForComodification();
    if (!hasPrevious())
        throw new NoSuchElementException();
    lastReturned = next = (next == null) ? last : next.prev;
    nextIndex--;
    return lastReturned.item;
}

3、foreach循環遍歴:
Javaバイトコードを分析すると、foreachの内部実装原理はIteratorによって実現されていることがわかりますが、このIteratorはJavaコンパイラが生成してくれたので、手動で書く必要はありません.しかし、毎回タイプ変換チェックを行うため、Iteratorよりも時間がかかりますが、時間の複雑さはIteratorと同じです.
各遍歴方式はどんな場合に適用されますか?
1、従来のforサイクル遍歴、カウンタに基づく:
遍歴順序記憶セットに適用され、読み取り性能が比較的高い.ループチェーンストレージの集合には適用されず、時間の複雑さが大きすぎます.
2、反復器遍歴、Iterator:
順次格納されるデータ構造については、あまり時間を気にしない場合は、この方法をお勧めします.コードがより簡潔で、Off-by-Oneの問題も防止されています.チェーンストレージ:このような遍歴方式が推奨され、平均時間複雑度がO(n)に低下する
3、foreach循環遍歴:
foreachはコードをより簡潔にするだけですが、遍歴中にデータセット(削除など)を操作できないため、使用しない場合があります.それ自体はIteratorに基づいて実現されていますが、タイプ変換の問題で直接使用するよりも遅くなりますが、時間の複雑さは同じです.
Javaのベストプラクティス
Javaデータセットフレームワークでは、メソッドがなく、タグだけのRandomAccessインタフェースが提供されています.一般に、リストインタフェースのインプリメンテーションによって使用され、リストのインプリメンテーションがRandom Accessをサポートするか否かをマークするために使用される.1つのデータセットがインタフェースを実現することは、位置による要素の読み取りの平均時間複雑度がO(1)であり、例えばArrayListをサポートすることを意味する.インタフェースが実装されていない場合は、LinkedListのようなRandom Accessがサポートされていないことを示す.JDK開発者もこの問題に気づいているようですが、リストを巡回したい場合は、Random Accessをサポートしているかどうかを判断することをお勧めします.以下のようにします.

if (list instanceof RandomAccess) {
  //     for    。
} else {
  //  Iterator  foreach。
}

アリババJava開発規約を分析する

GitHub Actionsでthree.jsの単体テスト