1. 概要
このクイックチュートリアルでは、リストのすべての要素が同じであるかどうかを判断する方法を説明します。
また、Big O表記を使用して各ソリューションの時間計算量を確認し、最悪のシナリオを示します。
2. 例
次の3つのリストがあるとしましょう。
notAllEqualList = Arrays.asList("Jack", "James", "Sam", "James");
emptyList = Arrays.asList();
allEqualList = Arrays.asList("Jack", "Jack", "Jack", "Jack");
私たちのタスクは、emptyListとallEqualListに対してのみtrueを返すさまざまなソリューションを提案することです。
3. 基本的なループ
まず、すべての要素が等しくなるためには、すべてが最初の要素と等しくなければならないのは事実です。 ループでそれを利用しましょう:
public boolean verifyAllEqualUsingALoop(List<String> list) {
for (String s : list) {
if (!s.equals(list.get(0)))
return false;
}
return true;
}
時間計算量はO(n)ですが、多くの場合、早期に終了する可能性があるため、これは便利です。
4. HashSet
HashSet はすべての要素が異なるため、使用することもできます。 I リストをHashSetに変換し、結果のサイズが1以下の場合、リスト内のすべての要素が等しいことがわかります。
public boolean verifyAllEqualUsingHashSet(List<String> list) {
return new HashSet<String>(list).size() <= 1;
}
リストをHashSetに変換するには、O(n)時間かかりますが、呼び出しサイズにはO(1)かかります。 したがって、 O(n)の合計時間計算量がまだあります。
5. コレクションAPI
別の解決策は、 Collections APIのfrequency(Collection c、Object o)メソッドを使用することです。 このメソッドは、オブジェクトoに一致するコレクションc内の要素の数を返します。
したがって、頻度の結果がリストのサイズと等しい場合、すべての要素が等しいことがわかります。
public boolean verifyAllEqualUsingFrequency(List<String> list) {
return list.isEmpty() || Collections.frequency(list, list.get(0)) == list.size();
}
以前のソリューションと同様に、時間計算量は O(n)です。これは、内部的に Collections.frequency()が基本的なループを使用するためです。
6. ストリーム
Java8のStreamAPIは、リスト内のすべてのアイテムが等しいかどうかを検出するさらに多くの代替方法を提供します。
6.1. distinct()
distinct()メソッドを使用する1つの特定のソリューションを見てみましょう。
リスト内のすべての要素が等しいかどうかを確認するために、そのストリームの個別の要素をカウントします:
public boolean verifyAllEqualUsingStream(List<String> list) {
return list.stream()
.distinct()
.count() <= 1;
}
このストリームの数が1以下の場合、すべての要素が等しく、trueを返します。
操作の総コストはO(n)、であり、これはすべてのストリーム要素を通過するのにかかる時間です。
6.2. allMatch()
Stream APIのallMatch()メソッドは、このストリームのすべての要素が提供された述語と一致するかどうかを判断するための完璧なソリューションを提供します。
public boolean verifyAllEqualAnotherUsingStream(List<String> list) {
return list.isEmpty() || list.stream()
.allMatch(list.get(0)::equals);
}
ストリームを使用する前の例と同様に、これには O(n)の時間計算量があります。これは、ストリーム全体をトラバースする時間です。
7. サードパーティのライブラリ
以前のバージョンのJavaでスタックしていて、Stream APIを使用できない場合は、GoogleGuavaやApacheCommonsなどのサードパーティライブラリを利用できます。
ここでは、非常によく似た2つのソリューションがあります。要素のリストを反復処理し、それを最初の要素と照合します。 したがって、時間計算量を O(n)と簡単に計算できます。
7.1. Mavenの依存関係
どちらかを使用するには、プロジェクトにそれぞれguavaまたはcommons-collections4を追加できます。
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>31.0.1-jre</version>
</dependency>
<dependency>
<groupId>org.apache.commons</groupId>
<artifactId>commons-collections4</artifactId>
<version>4.1</version>
</dependency>
7.2. Google Guava
Google Guavaでは、リスト内のすべての要素が述語を満たす場合、静的メソッドIterables.all()はtrueを返します。
public boolean verifyAllEqualUsingGuava(List<String> list) {
return Iterables.all(list, new Predicate<String>() {
public boolean apply(String s) {
return s.equals(list.get(0));
}
});
}
7.3. Apache Commons
同様に、 Apache Commons ライブラリは、Iterableインスタンスを操作するための静的ユーティリティメソッドのセットを備えたユーティリティクラスIterableUtilsも提供します。
特に、静的メソッド IterableUtils.matchesAll()は、リスト内のすべての要素が述語を満たす場合、trueを返します。
public boolean verifyAllEqualUsingApacheCommon(List<String> list) {
return IterableUtils.matchesAll(list, new org.apache.commons.collections4.Predicate<String>() {
public boolean evaluate(String s) {
return s.equals(list.get(0));
}
});
}
8. 結論
この記事では、リストのすべての要素が等しいかどうかを確認するさまざまな方法を学びました。まず、単純なJava機能から始めて、 StreamAPIと3番目のパーティライブラリGoogleGuavaおよびApacheCommons。
また、各ソリューションが O(n)の同じ時間計算量を与えることも学びました。 ただし、使用方法と使用場所に応じて最適なものを選択するのは私たちの責任です。
また、GitHubでサンプルの完全なセットを確認してください。