Когда вы знаете, когда использовать TreeSet или LinkedList?

Question

Каковы преимущества каждой структуры?

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

1. Принимая несортированный массив и добавление их в отсортированную структуру1.
2. Обход отсортированных данных и удаление правильных
3. Добавление данных (без удаления) и возврат этой структуры в виде массива

Answer 1

Когда вы знаете, когда использовать TreeSet или LinkedList?Каковы преимущества каждой структуры?

Как правило, вы выбираете тип коллекции на основе структурных и эксплуатационных свойств, которые вам необходимы.Например, TreeSet является множеством, и поэтому не допускает дублирования и не сохраняет порядок вставки элементов.В отличие от этого LinkedList является списком и, следовательно, допускает дублирование и сохраняет порядок вставки.Что касается производительности, TreeSet дает вам O(logN) вставку и удаление, тогда как LinkedList дает O(1) вставку в начале или конце и O(N) вставку в выбранную позицию или удаление.

Подробностивсе изложены в javadocs соответствующего класса и интерфейса, но полезное резюме можно найти в Таблице коллекций Java .

На практике выбор типа коллекции тесно связан сРазработка алгоритма.Два должны быть сделаны параллельно.(Нет смысла решать, что вашему алгоритму требуется коллекция со свойствами X, Y и Z, а затем обнаруживать, что такого типа коллекции не существует.)

В вашем случае использования выглядит, что TreeSet будетлучше подойдет.Не существует эффективного способа (т. Е. Лучше, чем O(N^2)) для сортировки большого LinkedList, который не требует превращения его в какую-либо другую структуру данных для выполнения сортировки.Не существует эффективного способа (т.е. лучше, чем O(N)) вставить элемент в правильную позицию в ранее отсортированном LinkedList.Третья часть (копирование в массив) одинаково хорошо работает с LinkedList или TreeSet;в обоих случаях это операция O(N).

[Я предполагаю, что коллекции достаточно велики, чтобы большая сложность O точно предсказывала фактическую производительность ...]

Answer 2

Подлинная сила и преимущество TreeSet заключается в интерфейсе, который он реализует - NavigableSet

Почему он такой мощный и в каком случае?

Интерфейс Navigable Set добавляет, например, эти 3 приятных метода:

    headSet(E toElement, boolean inclusive) 
    tailSet(E fromElement, boolean inclusive)
    subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)  

Эти методы позволяют организовать эффективный алгоритм поиска (очень быстрый).

Пример: нам нужночтобы найти все имена, которые начинаются с Milla и заканчиваются Wladimir:

    TreeSet<String> authors = new TreeSet<String>();
    authors.add("Andreas Gryphius");
    authors.add("Fjodor Michailowitsch Dostojewski");
    authors.add("Alexander Puschkin");
    authors.add("Ruslana Lyzhichko");
    authors.add("Wladimir Klitschko");
    authors.add("Andrij Schewtschenko");
    authors.add("Wayne Gretzky");
    authors.add("Johann Jakob Christoffel");
    authors.add("Milla Jovovich");
    authors.add("Taras Schewtschenko");
    System.out.println(authors.subSet("Milla", "Wladimir"));

output:

    [Milla Jovovich, Ruslana Lyzhichko, Taras Schewtschenko, Wayne Gretzky] 

TreeSet не охватывает все элементы, он находит первый и последний элементыи возвращает новую коллекцию со всеми элементами в диапазоне.

Answer 3

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

Состояние интерфейса Java Doc для Set:

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

Набор интерфейсов Java Doc

Answer 4

TreeSet:

TreeSet использует красно-черное дерево, лежащее в основе. Таким образом, набор можно представить как dynamic search tree. Когда вам нужна структура, которая часто используется для чтения / записи, а также для поддержания порядка, TreeSet - хороший выбор.

Answer 5

Если вы хотите сохранить сортировку и, в основном, добавление, TreeSet с компаратором - ваш лучший выбор.JVM должна будет сначала просмотреть LinkedList, чтобы решить, где разместить элемент.LinkedList = O (n) для любых операций, TreeSet = O (log (n)) для базовых вещей.