Эффективный способ реализации метода String Array "in" с использованием Java

Question

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

Одна из моих проблем заключается в определении, находится ли строка вArray of Strings.

Я мечтаю сделать "searchString.isIn (stringArray);"но я понимаю, что класс String этого не обеспечивает.

Есть ли более эффективный способ сделать это, кроме этой заглушки?

private boolean isIn(String searchString, String[] searchArray)
{
  for(String singleString : searchArray)
  {
    if (singleString.equals(searchString)
      return true;
  }

  return false;
}

Спасибо!

Answer 1

Возможно, вы захотите взглянуть на HashMap или HashSet , оба из которых обеспечивают получение с постоянным временем, и это так же просто, как и:

hashSet.contains(searchString)

ДополнительноHashSet (и HashMap для его ключей) предотвращает дублирование элементов.

Если вам нужно сохранить их в порядке вставки, вы можете посмотреть на их Связанные аналоги, и если вам нужно сохранитьих сортируют, TreeSet , и TreeMap может помочь (заметьте, однако, что TreeSet и TreeMap не обеспечивают постоянный поиск по времени).

Answer 2

Все остальные, кажется, рассматривают этот вопрос в более широком контексте (что, безусловно, верно). Я только отвечаю на этот бит:

Одна из моих проблем связана с определение, находится ли строка в массиве струн.

Это просто:

return Arrays.asList(arr).contains(str)

Справка:

Arrays.asList(array)

Answer 3

Если пространство поиска (ваша коллекция строк) ограничено, я согласен с уже опубликованными ответами. Однако, если у вас большой набор строк и вам необходимо выполнить достаточное количество поисков (чтобы перевесить накладные расходы на установку), вы можете также рассмотреть кодирование строк поиска в структуре данных trie . Опять же, это было бы выгодно только в том случае, если строк достаточно и вы выполняете поиск достаточно времени, чтобы оправдать накладные расходы на установку.

Answer 4

Как отметил Zach, вы можете использовать hashset для предотвращения дублирования и использовать метод contains для поиска строки, которая возвращает true при обнаружении совпадения. Вам также необходимо переопределить equals в вашем классе.

public boolean equals(Object other) { return other != null && other instanceof L && this.l == ((L)other).l;

Answer 5

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

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

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

Answer 6

Как объяснялось ранее, вы можете использовать Set (см. http://download.oracle.com/javase/1.5.0/docs/api/java/util/Set.html и особенно метод boolean contains(Object o)) для этой цели.Вот быстрый и грязный пример, который демонстрирует это:

String[] a = {"a", "2"};
Set<String> hashSet = new HashSet<String>();
Collections.addAll(hashSet, a);
System.out.println(hashSet.contains("a"));  // Returns true
System.out.println(hashSet.contains("2"));  // Returns true
System.out.println(hashSet.contains("e"));  // Returns false

Надеюсь, это поможет;)

Answer 7

Если вы делаете это много, вы можете сначала отсортировать массив и выполнить двоичный поиск для ваших строк.