Wskazówki dotyczące korzystania z kolekcji

1. Spis zbiorów

Jak być może pamiętasz, Java posiada przydatne narzędzie do przechowywania obiektów tego samego typu – kolekcje.

Spróbujmy przypomnieć główne interfejsy kolekcji:

Lista , zestaw , mapa i kolejka .

Jak zwykle nie ma dobrych ani złych narzędzi, jeśli używasz ich zgodnie z ich przeznaczeniem. W tym celu ty i ja musimy dokładnie zrozumieć ich funkcje, aby wiedzieć, kiedy i jakiej kolekcji użyć.

1.Lista

Zacznijmy od najczęściej używanej kolekcji.

Lista jest bardzo podobna do najczęściej spotykanej tablicy. Nazwa mówi nam, że jest to lista (lista).

Ta kolekcja pozwala nam wygodnie przechowywać listę obiektów tego samego typu bez martwienia się o rozmiar samej kolekcji, tak jak robiliśmy to przy użyciu tablic. Elementy kolekcji są dostępne za pomocą indeksu. Jeśli wiemy dokładnie, gdzie znajduje się obiekt i musimy często uzyskiwać do niego dostęp bez konieczności częstego dodawania lub usuwania elementów, lista jest idealna.

2. Ustaw

Zestaw (zestaw) ma zupełnie inną strukturę.

Przede wszystkim Set powinien być używany, gdy potrzebujemy przechowywać unikalne przedmioty. Załóżmy, że jest to zestaw autorów w bibliotece, w której każdy autor jest wyjątkowy. Ale nie możemy po prostu uzyskać dostępu do naszego zestawu autorów i wyodrębnić z niego konkretnego autora. Funkcjonalność Zestaw daje nam możliwość szybkiego sprawdzenia, czy dany autor jest obecny w naszej bibliotece, np. sprawdzenie jego obecności w zbiorze Zestaw . Można też przejść przez całą kolekcję, dla każdego elementu, ale nie jest to optymalne.

Oznacza to, że w naszej bibliotece Zestaw może służyć jako coś w rodzaju zbioru wszystkich autorów, aby szybko sprawdzić, czy ten autor jest reprezentowany w bibliotece.

3.mapa

Mapa (słownik) przypomina bardziej kartotekę, w której każda komórka jest podpisana, aw niej możemy przechowywać zarówno pojedyncze obiekty, jak i całe struktury. Mapa powinna być używana w przypadkach, gdy konieczne jest zachowanie zgodności jednej wartości z drugą.

W Map nazywa się to dopasowaniem klucz-wartość.

Dzięki tej strukturze w naszej bibliotece możemy użyć obiektu autora jako klucza i Listy książek jako wartości. Tym samym po sprawdzeniu obecności autora w bibliotece w Zbiorze , będziemy mogli pobrać Listę z jego książkami z Mapy przy użyciu tego samego obiektu autora .

4.Kolejka

Kolejka (kolejka) - to kolekcja zbudowana jako kolejka. Co więcej, ta kolejka może być nie tylko LIFO (Last In First Out - ostatni wchodzi, pierwszy wychodzi), ale także FIFO (First In First Out - pierwszy wchodzi, pierwszy wychodzi). A kolejka może być dwukierunkowa, z wyjściami po obu stronach.

To narzędzie jest przydatne w przypadkach, gdy obiekty wchodzące do naszej klasy, metody, muszą być używane w kolejności, w jakiej zostały otrzymane. Na przykład w naszej bibliotece.

Możemy dodać nowo przybyłych gości do Kolejki i obsłużyć ich pojedynczo, rozdając książki, po które do nas przychodzą.

Jak ty i ja widzimy, wszystkie struktury są dobre, jeśli są używane zgodnie z ich przeznaczeniem. W ramach jednego przykładu, biblioteki, wykorzystaliśmy wszystkie cztery rodzaje kolekcji.

2. Trudność

Jak już wspomniano, kolekcje, które rozważaliśmy powyżej, to interfejsy, co oznacza, że ​​muszą mieć implementacje, których będziemy używać.

Ponieważ wbijanie gwoździ pod mikroskopem nie jest najlepszym pomysłem, powinniśmy wiedzieć, która implementacja kolekcji jest lepsza w danej sytuacji.

Najczęściej przy wyborze konkretnego instrumentu patrzymy na 2 wskaźniki:

• Jak dobrze to narzędzie pasuje do zadania?
• Jak szybko to zadziała

Jeśli w jakiś sposób wymyśliliśmy wybór narzędzia odpowiedniego do zadania, to szybkość jego pracy jest czymś nowym.

Wskaźnik prędkości jest często wyrażany w kategoriach złożoności czasowej i oznaczany dużą literą O.

Jaka jest w ogóle ta złożoność czasowa?

Mówiąc prościej, ta złożoność oznacza czas potrzebny do przetworzenia algorytmu, który jest zawarty w kolekcji dla określonej akcji (dodanie, usunięcie elementu, wyszukiwanie).

ArrayList vs LinkedList

Przyjrzyjmy się temu przy użyciu dwóch implementacji interfejsu List , ArrayList i LinkedList .

Częściowo o różnicy między tymi dwoma implementacjami jest mowa w tym artykule .

Zewnętrznie praca z tymi kolekcjami jest podobna:

List<String> arrayList = new ArrayList<>();
arrayList.add(String);
arrayList.get(index);
arrayList.remove(index);
arrayList.remove(String);
 
List<String> linkedList = new LinkedList<>();
 
linkedList.add(String);
 
linkedList.get(index);
linkedList.remove(index);
linkedList.remove(String);
    

Jak widać, w obu przypadkach dodajemy, pobieramy i usuwamy element z listy w ten sam sposób. Dzieje się tak, ponieważ tworzymy wdrożenia w oparciu o jeden interfejs. Ale na tym kończą się ich podobieństwa.

Ze względu na różną implementację interfejsu List te dwie struktury mają różną wydajność w różnych zastosowaniach.

Rozważmy przykład operacji usuwania i dodawania elementu.

Jeśli musimy usunąć element ze środka ArrayList , za każdym razem nadpiszemy resztę listy po usuwanym elemencie.

Powiedzmy, że mamy listę 5 elementów i musimy usunąć trzeci.

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
list.remove(2);
    

W takim przypadku po usunięciu jedna komórka zostanie zwolniona i będziemy zmuszeni nadpisać 4. element w miejsce 3. i 5. w miejsce 4.

To jest najbardziej nieefektywne.

To samo stanie się podczas dodawania elementu na środku listy.

LinkedList jest ułożony inaczej. Dodawanie lub usuwanie z niego elementów jest szybkie, ponieważ wystarczy zmienić odniesienia w poprzednim i następnym elemencie, wyłączając obiekt, który usuwamy z łańcucha elementów.

Na przykładzie tej samej listy 5 elementów, po usunięciu z niej 3-go, powinniśmy po prostu zmienić link do następnego elementu w 2-im i link do poprzedniego w 4-tym elemencie.

To samo, ale na odwrót, dzieje się, gdy element jest dodawany do listy.

Zauważ, o ile mniej pracy musimy wykonać na LinkedList w porównaniu do ArrayList . A to tylko 5 elementów. Gdyby na liście było 100 lub więcej pozycji, wyższość LinkedList byłaby bardziej namacalna.

Ale jak zmieni się sytuacja, jeśli uzyskamy dostęp do elementu za pomocą indeksu?

Tutaj wszystko będzie dokładnie odwrotnie.

Ponieważ ArrayList jest zaprojektowany jak zwykła tablica, bardzo łatwo będzie nam pobrać dowolny element według jego indeksu. Po prostu przesuwamy wskaźnik w określone miejsce i pobieramy element z komórki.

Ale w LinkedList to po prostu nie działa w ten sposób. Będziemy musieli przejść przez wszystkie elementy tablicy, aby znaleźć elementy o określonym indeksie. Tylko w tym przypadku sensowne jest nazywanie go nie indeksem, ale numerem seryjnym.

Spróbujmy ująć to wszystko w kategoriach dużego O?

Zacznijmy od uzyskania dostępu do elementu według indeksu.

W ArrayList dzieje się to w jednym kroku, niezależnie od lokalizacji elementu na liście. Na początku lub na końcu.

Złożoność czasowa w tym przypadku wyniesie O(1) .

W LinkedList będziemy musieli iterować po liczbie elementów, których indeksu potrzebujemy.

Złożoność czasowa takiego działania wyniesie O(n) - gdzie n to indeks elementu, którego potrzebujemy.

Okazuje się, że pod dużymi nawiasami umieszczamy liczbę odpowiadającą liczbie wykonanych akcji.

Wrócić do usuwania i dodawania?

Zacznijmy od LinkedList.

Ponieważ nie musimy wykonywać dużej liczby czynności, aby dodać lub usunąć element, a szybkość tej operacji nie zależy w żaden sposób od tego, gdzie znajduje się element, trudno będzie wyglądać tak - O (1 ) i nazywa się stałą.

Złożoność tej samej operacji dla ArrayList będzie już O (n) i nazywana jest liniową.

W algorytmach o złożoności liniowej czas działania zależy bezpośrednio od liczby elementów do przetworzenia. Może to również zależeć od pozycji elementu, na początku listy lub pod koniec.

Złożoność jest również logarytmiczna. Wygląda to tak - O(log n) .

Jako przykład możemy rozważyć posortowaną listę TreeSet zawierającą 10 liczb, w której musimy znaleźć liczbę 2.

Ponieważ lista jest posortowana i nie ma na niej duplikatów, możemy podzielić ją na pół i sprawdzić, w której części listy pozostaje żądana liczba, odrzucić jedną z części i powtórzyć kroki ponownie, aż dojdziemy do pożądanego elementu. W końcu znajdziemy liczbę, przetwarzając liczbę log(n) elementów.

Rzućmy okiem na tabelę opisującą złożoność pozostałych kolekcji.

Teraz, gdy ty i ja mamy tabelę zawierającą złożoność czasową popularnych kolekcji, możemy odpowiedzieć na pytanie, dlaczego spośród tak wielu kolekcji najczęściej używamy ArrayList , HashSet i HashMap .

Są po prostu najskuteczniejsze do większości zadań :)