Как искать имя из списка 10 миллионов случайных имен в JAVA?

Question

У меня есть arraylist, который может содержать 10 миллионов случайных имен.Какой алгоритм поиска наиболее эффективен и как?

Answer 1

Пока у вас достаточно памяти - сортируйте свой список o (n * log (n)), а затем используйте двоичный поиск o (ln (n)).

List<String> yourNames = ...;
Collections.sort(yourNames);
...

int pos = Collections.binarySearch(yourNames, "tanmoy biswas");
if ( pos < 0 ) { 
  System.out.println("Not found");
}

Когда вы получите OOM

// before sort or do the intern during load of the data
for(int i = 0; i < yourNames.size(); i++) {
    yourNames.set(i, yourNames.get(i).intern());
} 

Answer 2

Без дополнительной информации я бы предположил, что вы хотите набор

List<String> list =
Set<String> set = new HashSet<String>(list);

// to perform a lookup. This is O(1)
boolean isInArray = set.contains(wordToSearchFor);

Answer 3

Поиск в неупорядоченном списке не эффективен.Вот ваши варианты в порядке возрастания сложности:

1. Первое, что вы можете сделать, это отсортировать список.Это позволит вам запустить бинарный поиск по вашим данным.Вы можете найти точные совпадения или совпадения префиксов за время O (log (n)).
2. Еще один шаг: загрузите свои данные в HashSet.Хэш-наборы действительно хороши в поиске точных совпадений, но мало что могут сделать.
3. Подумайте об использовании базы данных, которая индексирует ваши данные или даже Lucene.Это предпочтительный вариант, поскольку он предлагает самый широкий выбор поисковых запросов.