Kiedy wiesz, kiedy użyć TreeSet lub LinkedList?

Question

Jakie są zalety każdej z konstrukcji?

W moim programie będę wykonując kroki i zastanawiałem się, która to struktura danych powyżej Byłbym za pomocą:

1. Biorąc w niesegregowanych tablicy i dodając je do posortowanej struktura1.
2. Przejazd przez posortowanych danych i usuwania prawo jeden
3. dodawanie danych (nigdy usuwanie) i powrocie tej struktury jako tablica

Answer 1

Jeśli chcesz zachować to sortowane i to dołącz-głównie, TreeSet z Komparator to Twój najlepszy zakład. JVM musiałaby przejść od początku do listy LinkedList, aby zdecydować, gdzie umieścić przedmiot. LinkedList = O (n) dla dowolnych operacji, TreeSet = O (log (n)) dla podstawowych rzeczy.

Answer 2

Kiedy wiesz, kiedy użyć zestawu TreeSet lub LinkedList? Jakie są zalety każdej z konstrukcji?

Generalnie użytkownik decyduje o typie kolekcji opartym na właściwościach strukturalnych i właściwościach wydajności, które powinien on mieć. Na przykład TreeSet to zestaw, dlatego nie pozwala na duplikaty i nie zachowuje kolejności elementów. Natomiast lista powiązań jest listą i dlatego dopuszcza duplikaty i zachowuje porządek reklamowy. Po stronie wydajności, TreeSet daje wstawianie i usuwanie O(logN), podczas gdy LinkedList daje wstawianie O(1) na początku lub na końcu i wstawianie O(N) w wybranej pozycji lub usunięcie.

Szczegóły są podane we właściwej klasie i interfejsie javadocs, ale przydatne podsumowanie można znaleźć w Java Collections Cheatsheet.

W praktyce jednak wybór typu kolekcji jest ściśle związany z projektowaniem algorytmu. Te dwie kwestie muszą być wykonane równolegle. (Nie jest dobrym rozwiązaniem, że twój algorytm wymaga kolekcji z właściwościami X, Y i Z, a następnie odkrycie, że taki typ kolekcji nie istnieje.)

W twoim przypadku użycia wygląda na to, że TreeSet byłby lepiej dopasowany . Nie ma wydajnego sposobu (tj. Lepszego niż O(N^2)) do sortowania dużej listy powiązań, która nie wymaga przekształcenia jej w inną strukturę danych w celu sortowania. Nie ma skutecznego sposobu (tj. Lepszego niż O(N)) do wstawienia elementu do prawidłowej pozycji w uprzednio posortowanej liście połączeniowej. Trzecia część (kopiowanie do tablicy) działa równie dobrze z obiektem LinkedList lub TreeSet; jest to operacja O(N) w obu przypadkach.

[Jestem przy założeniu, że zbiory są na tyle duże, że duża złożoność O przewiduje rzeczywistą wydajność dokładnie ...]

Answer 3

TreeSet:

TreeSet wykorzystuje drzewo czerwono-czarne bazowych. Zestaw mógł więc być pomyślany jako dynamic search tree. Jeśli potrzebujesz struktury, która jest często używana do odczytu/zapisu, a także powinna zachowywać porządek, TreeSet jest dobrym wyborem.

Answer 4

Prawdziwy moc i zaletą TreeSet leży w interfejsie realizuje - NavigableSet

Dlaczego jest tak potężny, a w takim przypadku?

Żeglowny Set interfejs dodać na przykład te 3 ładne metod:

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

Te metody pozwalają zorganizować skuteczną algorytm wyszukiwania (bardzo szybko).

Przykład: musimy znaleźć wszystkie nazwy, które zaczynają się i kończą 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")); 

wyjściowa:

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

TreeSet nie wykracza ponad wszystkie elementy, stwierdzi, pierwszy i ostatni elemenets i zwraca nową kolekcję z wszystkimi elementami w zakresie.