Проверка наличия элемента в массиве строк

#java #массивы

Есть метод, который проверяет наличие элемента в массиве:

private boolean existA(String a) {
    for (String s : massStringA) {
        if (a.equals(s)) {
            return true;
        }
    }
    return false;
}




Является ли этот метод оптимальным, или же это "велосипед", и существует более оптимальное
решение этой задачи?
    

Ответы

Ответ 1

Если не касаться вопроса сортировки, то более короткой формой будет

return Arrays.asList(massStringA).contains(s);


(заметьте, Arrays.asList() не создаёт копию массива, а использует оригинал, так что
это не удваивает расход памяти).


Ответ 2

Если массив может быть отсортирован, то тогда можно ускорить механизм поиска.

String[] massStringA = ...;

// массив будет изменен!
Arrays.sort(massStringA);
if(Arrays.binarySearch(massStringA, a) >= 0) {
    // строка найдена
};


Если массив нельзя изменять и используется Java 8, то можно применить Stream

if(Arrays.stream(massStringA).anyMatch(s -> s.equals(a))) {
    // строка найдена
}


Ответ 3

Более оптимальное решение - скопировать String[] в HashSet, после чего использовать
метод contains у HashSet.

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

private static final int
        STRINGS_COUNT = 100 * 1000,
        TESTS_COUNT = 100 * 1000;

private static final HashSet hashSet = new HashSet<>();
private static final String[] massStringA = new String[STRINGS_COUNT];

public static void main(String[] args)
{
    for (int i = 0; i < STRINGS_COUNT; i++)
    {
        massStringA[i] = createString(i);
    }

    long startTime = System.currentTimeMillis();
    hashSet.addAll(Arrays.asList(massStringA));
    System.out.println("Copy time: " + (System.currentTimeMillis() - startTime) + "ms");

    Random rand = new Random();
    String[] testStrings = new String[TESTS_COUNT];
    for (int i = 0; i < TESTS_COUNT; i++)
    {
        int randValue = rand.nextInt(STRINGS_COUNT * 10);
        testStrings[i] = createString(randValue);
    }

    startTime = System.currentTimeMillis();
    int matches = 0;
    for (int i = 0; i < TESTS_COUNT; i++)
    {
        if (existA(testStrings[i]))
        {
            matches++;
        }
    }
    System.out.println("Array search time: " + (System.currentTimeMillis() - startTime)
+ "ms, matches: " + matches);

    startTime = System.currentTimeMillis();
    matches = 0;
    for (int i = 0; i < TESTS_COUNT; i++)
    {
        if (Arrays.asList(massStringA).contains(testStrings[i]))
        {
            matches++;
        }
    }
    System.out.println("Arrays.asList search time: " + (System.currentTimeMillis()
- startTime) + "ms, matches: " + matches);

    startTime = System.currentTimeMillis();
    matches = 0;
    for (int i = 0; i < TESTS_COUNT; i++)
    {
        if (hashSet.contains(testStrings[i]))
        {
            matches++;
        }
    }
    System.out.println("HashSet search time: " + (System.currentTimeMillis() - startTime)
+ "ms, matches: " + matches);
}

private static String createString(int number)
{
    int value = number;
    StringBuilder sb = new StringBuilder();
    while (value > 0)
    {
        sb.append((char)(value % 80 + 47));
        value /= 80;
    }
    return sb.toString();
}

private static boolean existA(String a)
{
    for (String s : massStringA)
    {
        if (a.equals(s))
        {
            return true;
        }
    }
    return false;
}


Для 100 тысяч тестов при 100 тысячах строк результаты такие:

Copy time: 16ms
Array search time: 69762ms, matches: 9858
Arrays.asList search time: 73248ms, matches: 9858
HashSet search time: 14ms, matches: 9858


Для миллиона тестов при 10 тысячах строк:

Copy time: 3ms
Array search time: 17775ms, matches: 99845
Arrays.asList search time: 17537ms, matches: 99845
HashSet search time: 26ms, matches: 99845


Ответ 4

Можно использовать метод contains


  public boolean contains(CharSequence s)


Вот пример проверки наличия строки "abc" в строке "abcdgd;aoihvfsl": 

String string = "abcdgd;aoihvfsl";
if (string.contains(String.valueOf("abc"))


В данном случае возвратит true.