Поиск строки в отсортированном списке в Java и, возможно, во всех строках, начинающихся с части строки

Question

Какой самый эффективный способ реализовать поиск строки в отсортированном списке строк в Java?

А как насчет поиска всей строки, начинающейся с части строки?

Спасибо за помощь.

Answer 1

Я думаю, вы ищете Collections # binarySearch для обоих требований.

Answer 2

Список действительно не подходит для этого. Прежде всего, binarySearch в лучшем случае выполнит O (N) для связного списка - поскольку список не поддерживает произвольный доступ, вы ничего не получите, отсортировав его.

То, что вы ищете, это три . Вики-страница описывает преимущества и то, как это работает достаточно хорошо, чтобы я не тратил свое время на попытки превзойти его. Хотя он не описывает преимущества перед отсортированным LinkedList, просто помните, что вставка в отсортированный LinkedList - это O (N) обходов ссылок и O (log n) сравнений элементов, как и поиск объекта. Это более эффективно и все еще поддерживает все операции, которые вы получили бы из отсортированного связанного списка.

Google находит несколько результатов для библиотек, которые поддерживают такую ​​структуру, как эта , но я не использовал ни одну из них. Это все еще довольно простая структура данных (по сравнению, например, с деревьями AVL), поэтому вы можете легко реализовать ее самостоятельно.

Answer 3

Вы можете просто использовать Collections.binarySearch () .

Answer 4

Для поиска не начинающих строк (т. Е. 'And' match 'andrew', 'candy' и 'sand') вам придется использовать грубую силу.

Для начала строки используйте BST.

Answer 5

http://en.wikipedia.org/wiki/Binary_search при условии, что вы используете java.util.ArrayList или аналогичную несвязанную структуру.

Answer 6

другой. Светоносный рот:

Какой самый эффективный способ реализовать поиск строки в отсортированном списке строк в Java?

Как уже упоминалось, вы можете использовать для этого Collections.binarySearch (...) . Убедитесь, что ваш список отсортирован, иначе вы, скорее всего, не получите правильные результаты.

другой. Светоносный рот:

А как насчет поиска всей строки, начинающейся с части строки?

Либо просматривайте список от начала до конца и проверяйте каждое слово, либо создайте (или возьмите из сети) радикальное дерево , которое может найти слова, начинающиеся с определенной (под) строки, гораздо быстрее чем перебирать список слов.