«Проверьте, содержит ли массив 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 лучше всего подходит для поиска в списке значений. Однако нам нужно создать их заранее и сохранить в наборе.