поиск по неупорядоченному списку без преобразования его в массив

Question

Есть ли способ сначала отсортировать, а затем искать объекты в связанном списке объектов. Я подумал только вам один из способов сортировки и двоичного поиска, что вы думаете? Спасибо

Answer 1

Это не очень хороший подход, ИМО. Если вы используете Collections.sort(list), где list - это LinkedList, это копирует list во временный массив, сортирует его, а затем копирует обратно в список, т.е. O(NlogN) для сортировки плюс 2 * O(N) копии. Но когда вы затем попытаетесь выполнить бинарный поиск (например, используя Collections.binarySearch(list), каждый поиск будет выполнять O(N) операций обхода списка. Таким образом, вы, возможно, не потрудились отсортировать список!

Другим подходом будет преобразование списка в массив или ArrayList, а затем сортировка и поиск в этом массиве / ArrayList. Это дает одну копию плюс один вид для настройки и O(logN) для каждого поиска.

Но ни один из них не является лучшим подходом. Это зависит от того, сколько раз вам нужно выполнить поисковые операции.

• Если вы просто хотите выполнить один поиск в списке, то вызов list.contains(...) будет O(N) ... и это лучше, чем все, что связано с сортировкой и двоичным поиском.

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

• Если вы хотите выполнить несколько поисков в списке, который постоянно меняется, где порядок не имеет значения, замените список на HashSet. Дополнительные затраты на обновление HashSet составят O(1) для каждого добавления / удаления и O(1) для каждого поиска.

• Если вы хотите выполнить многократный поиск в списке, который постоянно меняется, и порядок имеет значение, замените этот список на LinkedHashMap, упорядоченный по вставке. Это будет O(1) для каждого добавления / удаления и O(1) для каждого поиска ... но с большими константами пропорциональности, чем для HashSet.

Answer 2

• java.util.Collections # sort ()
• java.util.Collections # binarySearch ()

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

Обратите внимание, что реализация метода сортировки действительно преобразует список в массив, но вам не нужно явно преобразовывать список в массив перед вызовом метода:)

Answer 3

Возможно, вы захотите задать вопрос, является ли поиск по отсортированному списку лучшим вариантом для вашего варианта использования, поскольку он неэффективен. Сортировка списка - O (NlogN), а двоичный поиск - O (logN). Вы можете создать Set из ваших элементов списка и затем искать его с помощью метода contains, который является O (1), если вы просто хотите увидеть, существует ли элемент. Было бы намного проще дать вам несколько советов о том, какую коллекцию вы могли бы рассмотреть, если бы вы могли объяснить больше о вашем сценарии использования.

РЕДАКТИРОВАТЬ: рассмотрите проблемы производительности сортировки списков , если вы планируете сделать это для больших списков.