1. 概要

HashSet は、一意の要素を格納するためのコレクションです。

このチュートリアルでは、 java .util.HashSetクラスのremoveAll()メソッドのパフォーマンスについて説明します。

2. HashSet.removeAll()

removeAll メソッドは、コレクションに含まれるすべての要素を削除します。

Set<Integer> set = new HashSet<Integer>();
set.add(1);
set.add(2);
set.add(3);
set.add(4);

Collection<Integer> collection = new ArrayList<Integer>();
collection.add(1);
collection.add(3);

set.removeAll(collection);

Integer[] actualElements = new Integer[set.size()];
Integer[] expectedElements = new Integer[] { 2, 4 };
assertArrayEquals(expectedElements, set.toArray(actualElements));

その結果、要素1と3がセットから削除されます。

3. 内部実装と時間計算量

removeAll()メソッドは、セットとコレクションのどちらが小さいかを判別します。 これは、セットとコレクションで size()メソッドを呼び出すことによって行われます。

コレクションの要素数がsetより少ない場合、指定されたコレクションを時間計算量 O( n )で繰り返します。 また、要素が時間計算量O(1)のセットに存在するかどうかもチェックします。 また、要素が存在する場合は、セットの remove()メソッドを使用してセットから削除されます。これも、時間計算量がO(1)です。 したがって、全体の時間計算量はO(n)です。

セットの要素数がコレクションより少ない場合は、O( n )を使用してこのセットを繰り返します。 次に、 contains()メソッドを呼び出して、各要素がコレクションに存在するかどうかを確認します。 そして、そのような要素が存在する場合、その要素はセットから削除されます。 したがって、これは contains()メソッドの時間計算量に依存します。

この場合、コレクションが ArrayList の場合、 contains()メソッドの時間計算量はO( m )です。 したがって、 ArrayListに存在するすべての要素をセットから削除するための全体的な時間計算量は、O(n * m)です。

コレクションが再びHashSetの場合、 contains()メソッドの時間計算量はO(1)です。 したがって、 HashSetに存在するすべての要素をセットから削除するための全体的な時間計算量は、O(n)です。

4. パフォーマンス

上記の3つのケースのパフォーマンスの違いを確認するために、簡単なJMHベンチマークテストを作成してみましょう。

最初のケースでは、セットとコレクションを初期化します。ここでは、コレクションよりも多くの要素がセットに含まれています。 2番目のケースでは、セットとコレクションを初期化します。コレクションには、セットよりも多くの要素があります。 そして3番目のケースでは、2つのセットを初期化します。ここで、2番目のセットは1番目のセットよりも多くの要素を持っています。

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 5)
public class HashSetBenchmark {

    @State(Scope.Thread)
    public static class MyState {
        private Set employeeSet1 = new HashSet<>();
        private List employeeList1 = new ArrayList<>();
        private Set employeeSet2 = new HashSet<>();
        private List employeeList2 = new ArrayList<>();
        private Set<Employee> employeeSet3 = new HashSet<>();
        private Set<Employee> employeeSet4 = new HashSet<>();

        private long set1Size = 60000;
        private long list1Size = 50000;
        private long set2Size = 50000;
        private long list2Size = 60000;
        private long set3Size = 50000;
        private long set4Size = 60000;

        @Setup(Level.Trial)
        public void setUp() {
            // populating sets
        }
    }
}

その後、ベンチマークテストを追加します。

@Benchmark
public boolean given_SizeOfHashsetGreaterThanSizeOfCollection_whenRemoveAllFromHashSet_thenGoodPerformance(MyState state) {
    return state.employeeSet1.removeAll(state.employeeList1);
}

@Benchmark
public boolean given_SizeOfHashsetSmallerThanSizeOfCollection_whenRemoveAllFromHashSet_thenBadPerformance(MyState state) {
    return state.employeeSet2.removeAll(state.employeeList2);
}

@Benchmark
public boolean given_SizeOfHashsetSmallerThanSizeOfAnotherHashSet_whenRemoveAllFromHashSet_thenGoodPerformance(MyState state) {
    return state.employeeSet3.removeAll(state.employeeSet4);
}

そしてここに結果があります:

Benchmark                                              Mode  Cnt            Score            Error  Units
HashSetBenchmark.testHashSetSizeGreaterThanCollection  avgt   20      2700457.099 ±     475673.379  ns/op
HashSetBenchmark.testHashSetSmallerThanCollection      avgt   20  31522676649.950 ± 3556834894.168  ns/op
HashSetBenchmark.testHashSetSmallerThanOtherHashset    avgt   20      2672757.784 ±     224505.866  ns/op

HashSet の要素がコレクションよりも少ない場合、 HashSet.removeAll()のパフォーマンスがかなり悪いことがわかります。これは、に引数として渡されます。 ] removeAll()メソッド。 ただし、他のコレクションが再び HashSet の場合、パフォーマンスは良好です。

5. 結論

この記事では、HashSetでの removeAll()のパフォーマンスを確認しました。 セットの要素がコレクションより少ない場合、 removeAll()のパフォーマンスは、コレクションの contains()メソッドの時間計算量に依存します。

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