1. Обзор
В этом кратком руководстве мы узнаем, как определить, все ли элементы в списке одинаковы.
Мы также рассмотрим временную сложность каждого решения, используя нотацию Big O, что дает нам наихудший сценарий.
2. Пример
Предположим, у нас есть следующие 3 списка:
notAllEqualList = Arrays.asList("Jack", "James", "Sam", "James");
emptyList = Arrays.asList();
allEqualList = Arrays.asList("Jack", "Jack", "Jack", "Jack");
Наша задача — предложить разные решения, которые возвращают true только для emptyList и allEqualList .
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 и результирующий размер меньше или равен 1, то мы знаем, что все элементы в списке равны:
public boolean verifyAllEqualUsingHashSet(List<String> list) {
return new HashSet<String>(list).size() <= 1;
}
Преобразование списка в HashSet стоит O(n) времени, а вызов size занимает O(1) . Таким образом, у нас все еще есть общая временная сложность O(n) .
5. API коллекций
Другое решение — использовать метод Frequency (Collection c, Object o) API коллекций . Этот метод возвращает количество элементов в коллекции c , соответствующих объекту o .
Итак, если результат частоты равен размеру списка, мы знаем, что все элементы равны:
public boolean verifyAllEqualUsingFrequency(List<String> list) {
return list.isEmpty() || Collections.frequency(list, list.get(0)) == list.size();
}
Как и в предыдущих решениях, временная сложность равна O(n) , поскольку внутри Collections.frequency() используется базовый цикл.
6. Потоки
Stream API в Java 8 дает нам еще больше альтернативных способов определения, равны ли все элементы в списке.
6.1. отчетливый()
Давайте рассмотрим одно конкретное решение, использующее метод Different() .
Чтобы убедиться, что все элементы в списке равны, мы подсчитываем различные элементы его потока:
public boolean verifyAllEqualUsingStream(List<String> list) {
return list.stream()
.distinct()
.count() <= 1;
}
Если счетчик этого потока меньше или равен 1, то все элементы равны и мы возвращаем true .
Общая стоимость операции составляет O(n), то есть время, необходимое для прохождения всех элементов потока.
6.2. все совпадения()
Метод allMatch() API Stream предоставляет идеальное решение для определения того, все ли элементы этого потока соответствуют предоставленному предикату: ``
public boolean verifyAllEqualAnotherUsingStream(List<String> list) {
return list.isEmpty() || list.stream()
.allMatch(list.get(0)::equals);
}
Подобно предыдущему примеру с использованием потоков, этот пример имеет временную сложность O(n) , то есть время прохождения всего потока.
7. Сторонние библиотеки
Если мы застряли на более ранней версии Java и не можем использовать Stream API, мы можем использовать сторонние библиотеки, такие как Google Guava и Apache Commons .
Здесь у нас есть два очень похожих решения, перебирающих список элементов и сопоставляющих его с первым элементом. Таким образом, мы можем легко вычислить временную сложность 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 Гуава
В 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 также предоставляет служебный класс IterableUtils с набором статических служебных методов для работы с экземплярами Iterable .
В частности, статический метод 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 и затем показывая альтернативные способы с использованием Stream API и сторонних библиотек Google Guava и Apache Commons.
Мы также узнали, что каждое из решений дает нам одинаковую временную сложность O(n) . Тем не менее, мы должны выбрать лучший в зависимости от того, как и где он будет использоваться.
И обязательно ознакомьтесь с полным набором примеров на GitHub .