Javaコレクションの時間計算量

投稿日: 2019-10-18 2022-10-26
タグ: Algorithms, Java, Java Collections, Java List, Java Map, Java Set

1. 概要

このチュートリアルでは、 Java CollectionAPIのさまざまなコレクションのパフォーマンスについて説明します。コレクションについて話すとき、私たちは通常、リスト、マップ、およびセットデータ構造、およびそれらの一般的な実装について考えます。

最初に、一般的な操作に関するBig-Oの複雑さの洞察を見ていきます。次に、いくつかの収集操作の実行時間の実数を示します。

2. 時間計算量

通常、時間計算量について話すときは、Big-O表記を指します。簡単に言えば、この表記は、アルゴリズムを実行する時間が入力サイズとともにどのように増加するかを示しています。

Big-O表記理論および実用的なJavaの例の詳細については、役立つ記事をご覧ください。

3. リスト

順序付けられたコレクションである単純なリストから始めましょう。

ここでは、 ArrayList、LinkedList、、およびCopyOnWriteArrayListの実装のパフォーマンスの概要を見ていきます。

3.1. ArrayList

JavaのArrayListは、配列によってサポートされています。これは、その実装の内部ロジックを理解するのに役立ちます。 ArrayList のより包括的なガイドは、この記事ので入手できます。

それでは、最初に、一般的な操作の時間計算量を高レベルで説明します。

add（） – O（1）の時間がかかります。ただし、最悪のシナリオでは、新しい配列を作成してすべての要素をその配列にコピーする必要がある場合、それは O（n）です。
add（index、element） –平均して O（n）時間で実行されます
get（） –常に定数時間 O（1）操作
remove（） –線形 O（n）時間で実行されます。削除の対象となる要素を見つけるには、配列全体を反復処理する必要があります。
indexOf（） –これも線形時間で実行されます。内部配列を反復処理し、各要素を1つずつチェックするため、この操作の時間計算量には常に O（n）時間が必要です。
contains（） –実装は indexOf（）、に基づいているため、 O（n）時間でも実行されます。

3.2. CopyOnWriteArrayList

List インターフェースのこの実装は、マルチスレッドアプリケーションを操作するときに有益です。これはスレッドセーフであり、このガイドで詳しく説明されています。

CopyOnWriteArrayListのBig-O表記のパフォーマンスの概要は次のとおりです。

add（） –値を追加する位置に依存するため、複雑さは O（n）です。
get（） –は O（1）定数時間演算です
remove（） – O（n）時間かかります
contains（） –同様に、複雑さは O（n）です。

ご覧のとおり、このコレクションの使用は、 add（）メソッドのパフォーマンス特性のために非常にコストがかかります。

3.3. LinkedList

LinkedListは、データフィールドを保持するノードと別のノードへの参照で構成される線形データ構造です。その他のLinkedListの機能については、こちらの記事をご覧ください。

いくつかの基本的な操作を実行するために必要な時間の平均見積もりを提示しましょう。

add（） –リストの最後に要素を追加します。テールを更新するだけなので、 O（1）一定時間の複雑さです。
add（index、element） –平均して O（n）時間で実行されます
get（） –要素の検索には O（n）時間がかかります。
remove（element） –要素を削除するには、最初にその要素を見つける必要があります。この操作はO（n）です。
remove（index） –インデックスで要素を削除するには、最初にリンクを最初からたどる必要があります。したがって、全体的な複雑さは O（n）です。
contains（） – O（n）の時間計算量もあります

3.4. JVMのウォーミングアップ

さて、理論を証明するために、実際のデータで遊んでみましょう。 より正確には、最も一般的な収集操作のJMH（Java Microbenchmark Harness）テスト結果を示します。

JMHツールに慣れていない場合は、この便利なガイドを確認してください。

まず、ベンチマークテストの主なパラメータを示します。

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@Warmup(iterations = 10)
public class ArrayListBenchmark {
}

次に、ウォームアップの反復回数を10に設定します。結果の平均実行時間もマイクロ秒単位で表示したいことに注意してください。

3.5. ベンチマークテスト

次に、パフォーマンステストを実行します。まず、ArrayListから始めます。

@State(Scope.Thread)
public static class MyState {

    List<Employee> employeeList = new ArrayList<>();

    long iterations = 100000;

    Employee employee = new Employee(100L, "Harry");

    int employeeIndex = -1;

    @Setup(Level.Trial)
    public void setUp() {
        for (long i = 0; i < iterations; i++) {
            employeeList.add(new Employee(i, "John"));
        }

        employeeList.add(employee);
        employeeIndex = employeeList.indexOf(employee);
    }
}

ArrayListBenchmark 内に、Stateクラスを追加して初期データを保持します。

ここでは、EmployeeオブジェクトのArrayListを作成します。それで setUp（）メソッド内の100.000アイテムで初期化します。 @Stateは、@Benchmarkテストが同じスレッド内で宣言された変数に完全にアクセスできることを示します。

最後に、 add（）、contains（）、indexOf（）、remove（）、、 get（）メソッドのベンチマークテストを追加します。

@Benchmark
public void testAdd(ArrayListBenchmark.MyState state) {
    state.employeeList.add(new Employee(state.iterations + 1, "John"));
}

@Benchmark
public void testAddAt(ArrayListBenchmark.MyState state) {
    state.employeeList.add((int) (state.iterations), new Employee(state.iterations, "John"));
}

@Benchmark
public boolean testContains(ArrayListBenchmark.MyState state) {
    return state.employeeList.contains(state.employee);
}

@Benchmark
public int testIndexOf(ArrayListBenchmark.MyState state) {
    return state.employeeList.indexOf(state.employee);
}

@Benchmark
public Employee testGet(ArrayListBenchmark.MyState state) {
    return state.employeeList.get(state.employeeIndex);
}

@Benchmark
public boolean testRemove(ArrayListBenchmark.MyState state) {
    return state.employeeList.remove(state.employee);
}

3.6. 試験結果

すべての結果はマイクロ秒単位で表示されます。

Benchmark                        Mode  Cnt     Score     Error
ArrayListBenchmark.testAdd       avgt   20     2.296 ±   0.007
ArrayListBenchmark.testAddAt     avgt   20   101.092 ±  14.145
ArrayListBenchmark.testContains  avgt   20   709.404 ±  64.331
ArrayListBenchmark.testGet       avgt   20     0.007 ±   0.001
ArrayListBenchmark.testIndexOf   avgt   20   717.158 ±  58.782
ArrayListBenchmark.testRemove    avgt   20   624.856 ±  51.101

結果から、testContains（）メソッドとtestIndexOf（）メソッドがほぼ同時に実行されることがわかります。また、残りの結果から、 testAdd（）メソッドと testGet（）メソッドのスコアの大きな違いをはっきりと見ることができます。要素の追加には2.296 マイクロ秒かかり、要素の取得は0.007マイクロ秒の操作です。

さらに、要素の検索または削除には、およそ700マイクロ秒のコストがかかります。これらの数値は、 add（）、、および get（）が O（1）の時間計算量を持ち、他のメソッドはO（n）です。この例のn=10.000要素。

同様に、CopyOnWriteArrayListコレクションに対して同じテストを作成できます。必要なのは、employeeListのArrayListをCopyOnWriteArrayListインスタンスに置き換えることだけです。

ベンチマークテストの結果は次のとおりです。

Benchmark                          Mode  Cnt    Score     Error
CopyOnWriteBenchmark.testAdd       avgt   20  652.189 ±  36.641
CopyOnWriteBenchmark.testAddAt     avgt   20  897.258 ±  35.363
CopyOnWriteBenchmark.testContains  avgt   20  537.098 ±  54.235
CopyOnWriteBenchmark.testGet       avgt   20    0.006 ±   0.001
CopyOnWriteBenchmark.testIndexOf   avgt   20  547.207 ±  48.904
CopyOnWriteBenchmark.testRemove    avgt   20  648.162 ± 138.379

ここでも、数字は理論を裏付けています。ご覧のとおり、 testGet（）は平均0.006ミリ秒で実行され、 O（1）と見なすことができます。 ArrayListと比較すると、testAdd（）メソッドの結果に大きな違いがあることにも気づきます。ここでは、add（）メソッドとArrayListのO（1）のO（n）の複雑さがあります。

パフォーマンスの数値が0.051と比較して878.166であるため、時間の直線的な増加を明確に確認できます。

今はLinkedListの時間です：

Benchmark        Cnt     Score       Error
testAdd          20     2.580        ± 0.003
testContains     20     1808.102     ± 68.155
testGet          20     1561.831     ± 70.876 
testRemove       20     0.006        ± 0.001

スコアから、LinkedListの要素の追加と削除が非常に高速であることがわかります。

さらに、追加/削除操作と取得/含む操作の間には、パフォーマンスに大きなギャップがあります。

4. マップ

最新のJDKバージョンでは、 Map 実装のパフォーマンスが大幅に向上しています。たとえば、 LinkedList をHashMap、、およびLinkedHashMap内部実装。 これにより、HashMap衝突時の要素ルックアップの最悪のシナリオがO（n）からO（log（n））に短縮されます。

ただし、適切な .equals（）および .hashcode（）メソッドを実装すると、衝突が発生する可能性は低くなります。

HashMap の衝突の詳細については、この記事をご覧ください。 この記事から、HashMapからの要素の保存と取得には一定のO（1）時間がかかることもわかります。

**4.1. O（1）操作のテスト**

それでは、実際の数値を見てみましょう。まず、 HashMap ：

Benchmark                         Mode  Cnt  Score   Error
HashMapBenchmark.testContainsKey  avgt   20  0.009 ± 0.002
HashMapBenchmark.testGet          avgt   20  0.011 ± 0.001
HashMapBenchmark.testPut          avgt   20  0.019 ± 0.002
HashMapBenchmark.testRemove       avgt   20  0.010 ± 0.001

ご覧のとおり、数値は上記のメソッドを実行するためのO（1）定数時間を証明しています。次に、HashMapテストスコアを他のMapと比較してみましょう。 ]インスタンススコア。

リストされているすべてのメソッドについて、 HashMap、LinkedHashMap、IdentityHashMap、WeakHashMap、EnumMap、およびConcurrentHashMapのO（1）があります。

残りのテストスコアの結果を表の形式で提示しましょう。

Benchmark      LinkedHashMap  IdentityHashMap  WeakHashMap  ConcurrentHashMap
testContainsKey    0.008         0.009          0.014          0.011
testGet            0.011         0.109          0.019          0.012
testPut            0.020         0.013          0.020          0.031
testRemove         0.011         0.115          0.021          0.019

出力数から、 O（1）時間計算量の主張を確認できます。

**4.2. O（log（n））操作のテスト**

ツリー構造TreeMapおよびConcurrentSkipListMapの場合、put（）、get（）、remove（）、およびcontainsKey（）の操作時間はO（log（n））です。

ここでパフォーマンステストがほぼ対数時間で実行されることを確認したいと思います。このため、n = 1000、10,000、100,000、1,000,000のアイテムでマップを継続的に初期化します。

この場合、実行の合計時間に関心があります。

items count (n)         1000      10,000     100,000   1,000,000
all tests total score   00:03:17  00:03:17   00:03:30  00:05:27

n = 1000、の場合、合計00:03:17ミリ秒の実行時間があります。で n = 10,000、 時間はほとんど変わりません、 00:03:18ミリ秒 n = 100,000 でマイナーな増加があります 00:03:30 。そして最後に、 n = 1,000,000の場合、実行は 00:05:27msで完了します。

ランタイム番号を各nのlog（n）関数と比較した後、両方の関数の相関が一致していることを確認できます。

5. セット

通常、Setは一意の要素のコレクションです。ここでは、 HashSet 、 LinkedHashSet 、 EnumSet、TreeSet、CopyOnWriteArraySet、、およびConcurrentSkipListSetのの実装について説明します。 Setインターフェース。

HashSet の内部をよりよく理解するために、このガイドが役立ちます。

それでは、時間計算量の数値を示しましょう。 HashSet、LinkedHashSet、およびEnumSetの場合、add（）、remove（）、contains（）の操作は、内部HashMap実装のおかげで一定のO（1）時間を要します。

同様に、 TreeSetには、前のグループにリストされた操作のO（log（n））時間計算量があります。これは、TreeMapの実装によるものです。 ConcurrentSkipListSet の時間計算量も、スキップリストのデータ構造に基づいているため、 O（log（n））時間です。

CopyOnWriteArraySet、の場合、 add（）、remove（）、および contains（）メソッドの平均時間計算量はO（n）です。

5.1. 試験方法

それでは、ベンチマークテストにジャンプしましょう。

@Benchmark
public boolean testAdd(SetBenchMark.MyState state) {
    return state.employeeSet.add(state.employee);
}

@Benchmark
public Boolean testContains(SetBenchMark.MyState state) {
    return state.employeeSet.contains(state.employee);
}

@Benchmark
public boolean testRemove(SetBenchMark.MyState state) {
    return state.employeeSet.remove(state.employee);
}

残りのベンチマーク構成はそのままにしておきます。

5.2. 数字の比較

HashSetおよびLinkedHashSetがn=1000である場合の実行時実行スコアの動作を見てみましょう。 10,000; 100,000アイテム。

HashSet、の場合、番号は次のとおりです。

Benchmark      1000    10,000    100,000
.add()         0.026   0.023     0.024
.remove()      0.009   0.009     0.009
.contains()    0.009   0.009     0.010

同様に、LinkedHashSetの結果は次のとおりです。

Benchmark      1000    10,000    100,000
.add()         0.022   0.026     0.027
.remove()      0.008   0.012     0.009
.contains()    0.008   0.013     0.009

ご覧のとおり、各操作のスコアはほぼ同じです。それらをHashMapテスト出力と比較すると、同じように見えます。

その結果、テストしたすべてのメソッドが一定の O（1）時間で実行されることを確認しました。

6. 結論

この記事では、Javaデータ構造の最も一般的な実装の時間計算量を紹介します。

JVMベンチマークテストを通じて、各タイプのコレクションの実際の実行時パフォーマンスを確認しました。また、異なるコレクションでの同じ操作のパフォーマンスを比較しました。その結果、ニーズに合った適切なコレクションを選択する方法を学びました。

いつものように、この記事の完全なコードは、GitHubでから入手できます。

getdocs

13036