Kolekcje

UWAGA! Znajomość kolekcji i umiejętność dobrania odpowiedniego rodzaju kolekcji do konkretnej sytuacji to BARDZO ISTOTNA umiejętność programisty.

Kolekcje to grupa interfejsów, klas i algorytmów służąca do przechowywania grup elementów w formie zbiorów, list, kolejek oraz map. Użycie odpowiedniej kolekcji w odpowiedniej sytuacji pozwala na znaczące ziększenie wydajności programu.

Używanie kolekcji w języku Java zapewnia:

Kolekcje to zestaw struktur danych.

Składniki, z których zbudowane są te struktury:

W dokumentacji kolekcji Javy używana jest następująca notacja (na przykładzie interfejsu Collection):

Collection<E> oraz Map<K,V>

oraz opisy metod, np.:

boolean add( E element ) oraz V put( K key, V value )

E, K oraz V oznaczają dowolne typy obiektowe. Jeśli podczas tworzenia kolekcji podamy określoną klasę obiektów w danej kolekcji, wówczas wszystkie metody tej kolekcji będą operować właśnie na takiej klasie obiektów.

Np. zapis:

List<String> list = new ArrayList<String>();
Set<Animal> set = new HashSet<Animal>();

oznacza, że zostanie utworzona lista obiektów typu String oraz zbiór obiektów typu Animal. To z kolei oznacza, że wszystkie metody danej kolekcji będą operowały odpowiednio na danych typu/klasy String oraz danych typu/klasy Animal. Czyli w tym przypadku:

String str = "Łańcuch";
Animal bird = new Animal( "Bird" );

list.add( str );  // do listy list zostanie dodany obiekt klasy String
set.add( bird );  // do zbioru set zostanie dodany obiekt klasy Animal

Rodzaje kolekcji

Hierarchia dziedziczenia interfejsów kolekcji

Złożoność obliczeniowa algorytmów w kolekcjach

Świetnie wyjaśniona kwestia złożoności algorytmów (na stronie https://kobietydokodu.pl/niezbednik-juniora-kolekcje-w-jezyku-java/):

Notacja dużego O używana do porównywania złożoności obliczeniowej algorytmów.

Notacja ta określa jak bardzo zwiększy się czas potrzebny na wykonanie operacji na danych wraz ze wzrostem liczby danych wejściowych.

Na początek przykład operacji sortowania. Najprostszym sposobem na porównanie różnych podejść jest zmierzenie czasu sortowania tych samych elementów, np. 100 liczb. Metoda A zrobi to w 10 jednostek czasu a metoda B zrobi to w 20 jednostek czasu. Czy znaczy to, że metoda A jest lepsza / wydajniejsza? Absolutnie nie! Wykonując próbę dla 1000 liczb okaże się, że metoda A potrzebuje już 100 jednostek czasu, a metoda B tylko 50. Aby rozwiązać ten problem wprowadzono notację dużego o, która mówi nam nie ile czasu zajmie pewna operacja, ale jak ten czas się zmienia w zależności od ilości danych, na których pracujemy.

Brzmi skomplikowanie, ale to naprawdę proste! Weźmy dla przykładu algorytm, który losuje liczbę z przedziału (a, b). Dla uproszczenia pomyślmy o tym jako o człowieku, który z worka wszystkich możliwych liczb z tego przedziału wybiera jedną. Czy czas potrzebny na wybranie tej liczby zmieni się w zależności od tego czy w worku będzie 5, 50 czy 500000 liczb? Nie! Oznacza to, że algorytm ten działa w czasie stałym, który oznaczamy jako O(1). A dlaczego O(1) a nie np. O(3) ? Ponieważ interesuje nas jedynie sposób, w jaki ten czas rośnie, a nie sam czas. Jeśli jest stały, używamy po prostu jednostki, aby pokazać, że się nie zmienia.

Jako drugi przykład weźmy algorytm, który dla każdej liczby od zera do x wypisuje ją na konsoli. W zależności od wejścia (x w tym wypadku) nasz algorytm będzie musiał wykonać różną ilość operacji — w tym wypadku dla każdej jednej liczby będzie to określona, stała liczba operacji (ponownie, nie ma znaczenia, czy będą to 3 operacje czy 50, ważne, że jest to stała ilość). Dlatego algorytm ten ma złożoność obliczeniową O(n).

A co, jeśli poprzedni algorytm zmodyfikujemy tak, aby wypisywał też kwadrat tej liczby? Nic się nie zmieni, ponieważ wypisanie oraz obliczenie kwadrata liczby są operacjami o stałym czasie wykonania, a więc złożoność nadal będzie wynosiła O(n).

Złożoność jest bardzo ważna ponieważ często nie wiemy, ile dokładnie danych będzie przetwarzanych w naszym systemie i przez to nie jesteśmy w stanie wykonać miarodajnych prób czasowych. Nawet jesli byśmy to zrobili, te założenia będą się zmieniać z czasem. Dlatego o ile nie jesteśmy absolutnie pewni, że będziemy przetwarzać określoną, niewielką ilość informacji (np. kilkanaście) w danym miejscu, zawsze powinniśmy wybierać algorytm o najmniejszej złożoności, a nie taki, który działa szybciej (czasowo) podczas testów. Oczywiście od tej reguły można robić wyjątki, ale tylko pod warunkiem, ze naprawdę wiemy co robimy, a decyzja ta została zweryfikowana i udokumentowana w specyfikacji projektu.

Strona z tabelą złożoności wszystkich algorytmów dostępnych w kolekcjach: http://infotechgems.blogspot.ie/2011/11/java-collections-performance-time.html.

Wybrane klasy kolekcji Java oraz złożoność obliczeniowa podstawowych operacji

java.util.Set (zbiór)

java.util.List (lista)

java.util.Queue

java.util.Map

Szczegółowy opis kolekcji w języku Java:

Ciekawy przykład użycia interfejsów kolekcji

Niżej pokazany jest program generujący tablicę częstotliwości występowania odmiennych słów na liście słów przekazanych jako artumenty wywołania programu. Każde unikatowe słowo z listy argumentów programu jest traktowane jako kolejny klucz w kolekcji typu Map i każdy klucz jest mapowany na wartość określającą liczbę wystąpień danego słowa na wejściowej liście argumentów.

01 import java.util.*;
02 
03 public class FrequencyMapProgram {
04     public static void main( String[] args ) {
05         // Tworzymy mapę z kluczami typu String i wartościami typu Integer (klasa osłonowa dla int)
06         Map<String, Integer> map = new HashMap<String, Integer>();    
07 
08         // Inicjujemy mapę częstotliwości, pobierając kolejne słowa z listy argumentów wywołania programu
09         for( String word : args ) {
10             Integer frequency = map.get( word ); // metoda Map.get( Object key ) zwraca wartość (obiekt), 
11                                                  // na którą zmapowany jest dany klucz, albo zwraca null, 
12                                                  // jeśli dany klucz nie występuje.
13             map.put( word, ( frequency==null ) ? 1 : frequency+1 );
14         }
15
16         System.out.println( "Liczba odmiennych słów: " + map.size() );
17         System.out.println( map );
18     }
19 }
 

Ciekawym rozwiązaniem jest użycie wyrażenia warunkowego występującego jako drugi parametr wywołania metody map.put(…). Użycie takiej konstrukcji powoduje, że wartość, na którą mapowany jest dany klucz (określone słowo) - czyli wartość określająca częstotliwość występowania danego słowa - jest ustawiana na wartość 1, jeśli dane słowo dotychczas nie wystąpiło, albo - jeśli dane słowo wystąpiło, wartość jest zwiększana o jeden.

Uruchomienie tego kodu przy użyciu następujących argumentów wywołania programu:

java FrequencyMapProgram zuza ela ala ela zuza ola zuza ala baba tata ela

Spowoduje wyświetlenie NA PRZYŁAD następującego wyniku:

Liczba odmiennych słów: 6
{baba=1, ola=1, ala=2, zuza=3, ela=3, tata=1}

Zauważ, że w wyniku słowa występują w przypadkowej kolejności - nie związanej z kolejnością słów w wejściowym zestawie słów.

Poniżej pokazane są przykłady łatwej i sprytnej zamiany typów kolekcji w celu odpowiedniego usprawnienia programu.

Przykłady te dobrze ilustrują elastyczność hierarchicznej struktury interfejsów kolekcji oraz pokazują korzyści wynikające z używania ich.

Załóżmy, że chcemy uzyskać wynik w formie listy słów uporządkowanych alfabetycznie.

Aby to osiągnąć, wystarczy zmienić (w wierszu 06 kodu programu) typ implementacji interfejsu kolekcji Map z klasy HashMap na TreeMap, w której nowe elementy są dodawane tak, aby struktura była natychmiast uporządkowana - posortowana rosnąco względem wartości kluczy.

Wówczas dla tego samego zestawu słów wejściowych uzyskamy następujący - uporządkowany alfabetycznie wynik:

Liczba odmiennych słów: 6
{ala=2, baba=1, ela=3, ola=1, tata=1, zuza=3}

Załóżmy teraz, że chcemy, aby słowa występowały w kolejności, w jakiej zostały podane w wejściowym zestawie słów.

Aby to osiągnąć, wystarczy zmienić (w wierszu 06 kodu programu) typ implementacji interfejsu kolekcji Map na LinkedHashMap, w której zachowywana jest koejność zgodna z kolejnością dodawania par klucz-wartość.

Wówczas dla tego samego zestawu słów wejściowych uzyskamy następujący wynik - uporządkowany zgodnie z kolejnością wystąpienia poszczególnych słów w wejściowym zestawie słów:

Liczba odmiennych słów: 6
{zuza=3, ela=3, ala=2, ola=1, baba=1, tata=1}

Szczegółowy opis kolekcji w języku Java: