Проверьте, содержит ли массив Java значение

1. Обзор

В этой статье мы рассмотрим различные способы поиска в массиве указанного значения.

Мы также сравним, как они работают с помощью JMH (жгут проводов Java Microbenchmark), чтобы определить, какой метод работает лучше всего.

2. Настройка

Для наших примеров мы будем использовать массив, содержащий случайно сгенерированные Строки для каждого теста:

String[] seedArray(int length) {
    String[] strings = new String[length];
    Random value = new Random();
    for (int i = 0; i < length; i++) {
        strings[i] = String.valueOf(value.nextInt());
    }
    return strings;
}

Чтобы повторно использовать массив в каждом тесте, мы объявим внутренний класс для хранения массива и количества, чтобы мы могли объявить его область для JMH:

@State(Scope.Benchmark)
public static class SearchData {
    static int count = 1000;
    static String[] strings = seedArray(1000);
}

3. Основной поиск

Три часто используемых метода поиска массива-это Список, Набор, или цикл , который проверяет каждый элемент, пока не найдет совпадение.

Давайте начнем с трех методов, которые реализуют каждый алгоритм:

boolean searchList(String[] strings, String searchString) {
    return Arrays.asList(SearchData.strings)
      .contains(searchString);
}

boolean searchSet(String[] strings, String searchString) {
    Set stringSet = new HashSet<>(Arrays.asList(SearchData.strings));
    
    return stringSet.contains(searchString);
}

boolean searchLoop(String[] strings, String searchString) {
    for (String string : SearchData.strings) {
        if (string.equals(searchString))
        return true;
    }
    
    return false;
}

Мы будем использовать эти аннотации классов, чтобы сообщить JMH, чтобы вывести среднее время в микросекундах и выполнить пять итераций прогрева, чтобы убедиться, что наши тесты надежны:

@BenchmarkMode(Mode.AverageTime)
@Warmup(iterations = 5)
@OutputTimeUnit(TimeUnit.MICROSECONDS)

И запускайте каждый тест в цикле:

@Benchmark
public void searchArrayLoop() {
    for (int i = 0; i < SearchData.count; i++) {
        searchLoop(SearchData.strings, "T");
    }
}

@Benchmark
public void searchArrayAllocNewList() {
    for (int i = 0; i < SearchData.count; i++) {
        searchList(SearchData.strings, "T");
    }
}

@Benchmark
public void searchArrayAllocNewSet() {
    for (int i = 0; i < SearchData.count; i++) {
        searchSet(SearchData.strings, "S");
    }
}

Когда мы выполняем 1000 поисков для каждого метода, наши результаты выглядят примерно так:

SearchArrayTest.searchArrayAllocNewList  avgt   20    937.851 ±  14.226  us/op
SearchArrayTest.searchArrayAllocNewSet   avgt   20  14309.122 ± 193.844  us/op
SearchArrayTest.searchArrayLoop          avgt   20    758.060 ±   9.433  us/op

Поиск по циклу более эффективен, чем другие. Но это, по крайней мере, частично из-за того, как мы используем коллекции.

Мы создаем новый экземпляр List с каждым вызовом search List() и новый List и новый HashSet с каждым вызовом searchSet() . Создание этих объектов создает дополнительные затраты, которых нет при циклическом прохождении по массиву.

4. Более Эффективный Поиск

Что происходит, когда мы создаем отдельные экземпляры List и Set , а затем повторно используем их для каждого поиска?

Давайте попробуем:

public void searchArrayReuseList() {
    List asList = Arrays.asList(SearchData.strings);
    for (int i = 0; i < SearchData.count; i++) {
        asList.contains("T");
    }
}

public void searchArrayReuseSet() {
    Set asSet = new HashSet<>(Arrays.asList(SearchData.strings));
    for (int i = 0; i < SearchData.count; i++) {
        asSet.contains("T");
    }
}

Мы запустим эти методы с теми же аннотациями JMH, что и выше, и включим результаты для простого цикла для сравнения.

Мы видим очень разные результаты:

SearchArrayTest.searchArrayLoop          avgt   20    758.060 ±   9.433  us/op
SearchArrayTest.searchArrayReuseList     avgt   20    837.265 ±  11.283  us/op
SearchArrayTest.searchArrayReuseSet      avgt   20     14.030 ±   0.197  us/op

Во время поиска Список немного быстрее, чем раньше, Набор падает до менее чем 1 процента времени, необходимого для цикла!

Теперь, когда мы удалили время, необходимое для создания новых коллекций из каждого поиска, эти результаты имеют смысл.

Поиск хэш-таблицы, структуры , лежащей в основе HashSet , имеет временную сложность 0(1), в то время как массив, лежащий в основе ArrayList , равен 0(n).

5. Бинарный поиск

Другим методом поиска массива является двоичный поиск . Хотя двоичный поиск очень эффективен, он требует, чтобы массив был отсортирован заранее.

Давайте отсортируем массив и попробуем двоичный поиск:

@Benchmark
public void searchArrayBinarySearch() {
    Arrays.sort(SearchData.strings);
    for (int i = 0; i < SearchData.count; i++) {
        Arrays.binarySearch(SearchData.strings, "T");
    }
}

SearchArrayTest.searchArrayBinarySearch  avgt   20     26.527 ±   0.376  us/op

Двоичный поиск очень быстр, хотя и менее эффективен, чем HashSet: наихудшая производительность двоичного поиска равна 0(log n), что ставит его производительность между поиском по массиву и хэш-таблицей.

6. Заключение

Мы видели несколько методов поиска по массиву.

Основываясь на наших результатах, HashSet лучше всего подходит для поиска по списку значений. Однако нам нужно создать их заранее и сохранить в наборе .

Как всегда, полный исходный код примеров доступен на GitHub .