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

1. Обзор

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

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

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<String> 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 при каждом вызове searchList() , а также новый 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

В то время как поиск по списку стал немного быстрее, чем раньше, Set сократился до менее 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 .