Wyzwanie Java #4: Algorytmy i struktury danych w języku Java

Programy operują na danych. Mogą one być wczytywane z plików, pochodzić z baz danych, z urządzeń i mierników czy być odbierane po sieci. Bez względu czy będziemy chcieli je tylko wyświetlić użytkownikowi, czy zrobić na nich jakąś zaawansowaną analizę matematyczną, zawsze będziemy potrzebowali w jakiś sposób je przechować w naszym programie. Mechanizm przechowywania w uporządkowany sposób informacji w naszym programie nazywamy strukturami danych. Na tych strukturach będą operować nasze algorytmy i bardzo często od wybranej struktury będzie zależeć wydajność danego algorytmu.

Algorytmy i struktury danych to podstawa na której opiera się cała dzisiejsza informatyka, dlatego na każdym kierunku studiów informatycznych jest przynajmniej jeden przedmiot poświęcony tym zagadnieniom. Powstało także mnóstwo książek na temat algorytmów i struktur danych, przy czym za jedną z czołowych pozycji uważana jest monografia “Sztuka programowania” napisana przez Donalda Knuth’a. Sam Bill Gates, założyciel firmy Microsoft, mawiał o tej książce: “Jeśli myślisz, że jesteś dobrym programistą (…) przeczytaj “Sztukę programowania” (…). Jeśli będziesz w stanie przeczytać całość, to zdecydowanie prześlij mi swoje CV”.

Zakres wiedzy do poznania dogłębnie algorytmów i struktur danych jest tak duży, że w tym poście opowiemy sobie tylko o podstawowych strukturach danych dostępnych w języku Java. Jako uzupełnienie polecam książkę Java 9 Data Structures and Algorithms, Debasish Ray Chawdhuri lub Data Structures and Algorithms in Java, 2nd Edition, Robert Lafore lub jakąkolwiek inną pozycję szeroko traktującą o tych zagadnieniach.

Tablice

Podstawową strukturą danych, dostępną w niemal każdym języku programowania są tablice. Tablice przechowują zbiór elementów tego samego typu z zachowaniem kolejności. Dostęp do dowolnego elementu w tablicy realizowany jest przez indeks (typu int) reprezentujący pozycję elementu w tablicy, zaczynając od zera. Oznacza to, że pierwszy element ma pozycję zero, drugi element pozycję jeden, trzeci dwa i tak dalej, aż do ostatniego elementu. Tablice też mają z góry określoną wielkość w momencie ich tworzenia, stąd od początku musimy wiedzieć ile elementów będziemy potrzebować przechować w naszej tablicy.

Tablicę deklarujemy podając jej typ, nazwę oraz używając nawiasów kwadratowych ”[]“:

int[] a;
long[] b;
String[] c;

W powyższym przykładzie zadeklarowaliśmy trzy tablice typu int, long oraz String. Istnieje także możliwość zadeklarowania tablic tak jak to się robi w języku C/C++, czyli podając nawiasy ”[]” obok nazwy, a nie typu:

int a[];
long b[];
String c[];

Żeby stworzyć tablicę, należy użyć słowa new poznanego w rozdziale poświęconym programowaniu obiektowemu. Oznacza to, że tablice w języku Java są obiektami.

int[] a = new int[100];
long b[] = new long[10];
String[] c = new String[5];

Podczas tworzenia tablic wymagane jest podanie długości, czyli liczby elementów, które będzie przechowywać. Podczas tej operacji tworzona jest sama tablica, jednak jest ona pusta w środku.

W celu wypełnienia tablicy, trzeba odwołać się do jej poszczególnych pozycji za pomocą indeksu (pamiętajmy o numeracji od zera):

a[0] = 5;
a[10] = 245;
a[34] = -27;

c[0] = "Ala";
c[2] = "ma";
c[4] = "kota";

Analogicznie możemy za pomocą indeksu dostać się do zawartości jakiegoś elementu w tablicy:

System.out.println("Element nr 0 z tablicy c ma wartość: " + c[0]);

Do stworzenia i odczytania elementów w tablicy możemy także użyć pętli, np. for:

for (var i = 0; i < 100; i++) {
    a[i] = i;
}

for (var i = 0; i < 100; i++) {
    System.out.println(a[i]);
}

W powyższym przykładzie nasza tablica została wypełniona liczbą taką jak numer indeksu tej liczby, czyli pozycji w tablicy a następnie wszystkie elementy zostały wyświetlone. Podczas inicjalizacji tablicy wszystkie typy proste jak int, long, boolean są inicjalizowane (uzupełniane) ich domyślnymi wartościami, czyli w przypadku int będzie to zero, zaś boolean wartość false. W przypadku typów złożonych, czyli obiektów, domyślnie dostajemy wartość null, co można zauważyć na poniższym przykładzie:

c[0] = "Ala";
c[2] = "ma";
c[4] = "kota";

for (var i = 0; i < 5; i++) {
    System.out.println(c[i]);
}

wynik programu powyżej:

Ala
null
ma
null
kota

Niestety, w powyższych przykładach kodu, zawsze musieliśmy wiedzieć jaką dana tablica ma długość, by wskazać to w pętli for. W zamian można użyć właściwości lenght tablicy:

for (var i = 0; i < c.length; i++) {
    System.out.println(c[i]);
}

Gdy korzystamy ze wszystkich elementów tablicy, o wiele wygodniejsze jest użycie nowej wersji pętli form, tak zwany foreach, czyli dla każdego elementu:

for (var element : c) {
    System.out.println(element);
}

Jedyne co tutaj musimy wskazać to nazwę zmiennej, w której będą umieszczane kolejne elementy tablicy. W naszym przypadku jest to zmienna “element”.

Jeśli z góry wiemy jakie elementy będziemy przechowywać w naszej tablicy, możemy użyć do jej stworzenia uproszczonego zapisu:

String[] names = {"Kasia", "Tomek", "Patryk"};

Zauważmy, że w powyższym przykładzie nie musieliśmy podawać długości tablicy, będzie ona równa liczbie elementów wskazanych przy jej tworzeniu, czyli w naszym przypadku będzie równa trzy.

Dla osób dociekliwych:

Tablice mogą również być wielowymiarowe. Można to rozumieć jako tablicę, która zawiera w sobie inne tablice. Można także tablice dwuwymiarową wyobrażać sobie jako szachownicę, zaś trójwymiarową jako kostkę rubika.

Poniżej przykład stworzenia i wyświetlenia tablicy dwuwymiarowej 3x3 liczb typu int:

int[][] tab = new int[3][3];

for (int i = 0; i < tab.length; i++) {
    for (int k = 0; k < tab[i].length; k++) {
        tab[i][k] = i + k;
    }
}

for (int i = 0; i < tab.length; i++) {
    for (int k = 0; k < tab[i].length; k++) {
        System.out.println("tab[" + i + "][" + k + "] = " + tab[i][k]);
    }
}

Kolekcje

Oprócz tablic, w języku Java mamy dostęp do bardziej zaawansowanych struktur danych, zwanych kolekcjami. Zbiór kolekcji dzieli sią na interfejsy, implementacje i algorytmy, które możemy wykonywać na kolekcjach. Interfejs opisuje nam daną kolekcję, inaczej kontener, czyli mówi z jakich metod możemy skorzystać w danej kolekcji. Implementacja to klasa, która realizuje dane operacje, jednak na różne sposoby. To trochę tak, jakby w tym samym samochodzie zamontować raz silnik benzynowy, a raz silnik Diesla. Silnik to nasz interfejs, zaś silnik benzynowy i silnik wysokoprężny to już jego dwie implementacje, które robią to samo - napędzają nasz samochód, ale w zupełnie inny sposób.

W zależności od wymagań naszego algorytmu, możemy wybrać zupełnie inną kolekcję lub jej implementację, by nasz program był jak najwydajniejszy. Dlatego gruntowna wiedza o algorytmach i strukturach danych bywa tak istotna przy tworzeniu oprogramowania, zwłaszcza obliczeniowego.

List

Kolekcje typu List (lista) są bardzo podobne do tablic. Tak samo jak one są zbiorem przechowującym elementy z zachowaniem ich kolejności. Mogą także przechowywać duplikaty. Jednak w przeciwieństwie do tablic, listy są dynamiczne, to znaczy, że w trakcie działania programu możemy dodawać nowe elementy i nie musimy podczas tworzenia listy podawać jej maksymalnej długości. Dwiema popularnymi implementacjami List są ArrayList i LinkedList. Pierwsza implementacja opiera się o tablicę (stąd nazwa ArrayList), druga jest tak zwaną listą powiązaną, gdzie elementy są ze sobą połączone niczym wagoniki w kolejce. W większości przypadków lista ArraList będzie wydajniejsza, stąd jeśli nie wiecie jaką wybrać, jest ona zdecydowanie bezpieczniejszym wyborem. Korzystanie z LinkedList w nieprawidłowy sposób często bywa źródłem problemów wydajnościowych w programach!

Poniżej przykład stworzenia listy i włożenia do niej elementów:

List<Integer> list = new ArrayList<>();
list.add(5);
list.add(4745);
list.add(-87);

Służy do tego metoda add która dodaje nowy element (u nas liczby 5, 4745 i -87) na końcu listy. Do listy możemy dodać dowolną inną kolekcję za pomocą metody addAll:

List<Integer> list = new ArrayList<>();
list.add(5);
list.add(4745);
list.add(-87);

List<Integer> list2 = new LinkedList<>();
list2.add(35);
list2.add(-14);

list.addAll(list2);

Nasze elementy możemy wkładać na dowolną pozycję, nie tylko ostatnie miejsce, wtedy należy podać w metodzie add lub addAll pozycję gdzie mają trafić nowe elementy:

List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);

List<Integer> list2 = new LinkedList<>();
list2.add(4);
list2.add(0, 5);  // liczba 5 trafia na początek listy nr 2

list.addAll(2, list2); // do listy 1 dodaję listę 2, od trzeciej pozycji (czyli po kolei: 1,2,5,4,3)

Do poszczególnych elementów listy można dostać się, podobnie jak w tablicach, za pomocą pętli foreach:

for (var element : list) {
    System.out.println(element);
}

lub bezpośrednio do dowolnego elementu za pomocą indeksu:

System.out.println(list.get(0));
System.out.println(list.get(3));

Interfejs List ma wiele przydatnych metod, w tym takie metody jak:

add i addAll - dodawanie elementu/-ów
clear - usunięcie wszystkich elementów
remove i removeAll - usunięcie elementu/-ów
isEmpty - sprawdzenie czy lista jest pusta
size - sprawdzenie wielkości
set - zamiana elementu na inny element
sort - posortowanie listy
toArray - zamiana na tablicę
indexOf - zwrócenie pozycji wskazanego elementu

Większość z powyższych metod pochodzi z interfejsu Collection, co oznacza, że jest dostępna dla wszystkich kolekcji zgodnie z diagramem przedstawionym wcześniej.

Poniżej przykład użycia części z powyższych metod:

List<Integer> collection1 = new ArrayList<>();
List<Integer> collection2 = new LinkedList<>();

collection1.add(1);  // dodawanie elementów
collection1.add(2);
collection1.add(3);

collection2.add(4);
collection2.add(0, 5); // dodanie elementu na początku kolekcji nr. 2

collection1.addAll(2, collection2); // łączenie kolekcji, druga kolekcja zacznie się po drugim elemencie

System.out.println("Elementy: ");
for (var element : collection1) {
    System.out.println(element);
}

System.out.println("Pozycja liczby 3 to: " + collection1.indexOf(3)); // pozycje w kolekcjach numerowane są także od zera!!!
collection1.remove(2); // usunięcie trzeciego elementu
System.out.println("Pozycja liczby 3 to: " + collection1.indexOf(3));

collection1.set(0, 10); // zamieniam pierwszy element na 10
System.out.println("Pierwszy element kolekcji: " + collection1.get(0));

collection1.clear();
System.out.println("Liczba elementów: " + collection1.size());

Set

Kolejną i bardzo często używaną w praktyce kolekcją jest Set (zbiór). W przeciwieństwie do list, zbiory nie pozwalają na dodawanie duplikatów.

Wyróżniamy aż trzy podstawowe implementacje:

HashSet - najpopularniejszy i zarazem najwydajniejszy, jednak nie zachowuje żadnego porządku (kolejności), co oznacza, że elementy będą zwracane w losowej kolejności, jest oparty o tablice mieszające
TreeSet - wolniejszy od HashSet, lecz zachowujący kolejność elementów ze względu na ich wartość (sortowanie), oparty na algorytmie drzewa czerwono czarnego, od którego pochodzi jego przedrostek “tree”
LinkedHashSet - podobnie do HashSet bazuje na tablicach mieszających, jednak z tą różnicą, że dzięki zastosowaniu dodatkowo listy powiązanej (linked list), zachowuje kolejność w jakiej elementy są dodawane do kolekcji

Poniżej przykładowy kod z użyciem dwóch implementacji interfejsu Set:

Set<Integer> collection1 = new TreeSet<>();
Set<Integer> collection2 = new HashSet<>();

collection1.add(1);  // dodawanie elementów
collection1.add(2);
collection1.add(3);

collection2.add(5);
collection2.add(4);

collection1.addAll( collection2); // łączenie kolekcji

System.out.println("Elementy: ");
for (var element : collection1) {
    System.out.println(element);
}

System.out.println("Liczba elementów: " + collection1.size());
collection1.remove(2); // usunięcie liczby dwa!
System.out.println("Liczba elementów: " + collection1.size());

collection1.clear();
System.out.println("Liczba elementów: " + collection1.size());

Map

Trzecią i zarazem niezwykle popularną kolekcją stosowaną przez programistów języka Java jest Map (mapa lub słownik). Kolekcja ta służy do przechowywania par klucz - wartość. Dlatego na diagramie kolekcji, nie są zależne od interfejsu Collection.

Mamy dostępne trzy podstawowe implementacje interfejsu Map:

HashMap - analogiczna do HashSet
TreeMap - analogiczna do TreeSet
LinkedHashMap - analogiczna do LinkedHashSet

Jak widać słowniki (map) są zbudowane i zachowują się jak zbiory (set), z tą różnicą, że operują na elementach będących parami.

Poniżej przykład użycia dwóch implementacji Map:

Map<Integer, String> collection1 = new TreeMap<>();
Map<Integer, String> collection2 = new HashMap<>();

collection1.put(1, "jeden");  // dodawanie elementów
collection1.put(2, "dwa");
collection1.put(3, "trzy");

collection2.put(5, "pięć");
collection2.put(4, "cztery");

collection1.putAll(collection2); // łączenie kolekcji

System.out.println("Klucze: ");
for (var key : collection1.keySet()) {
    System.out.println(key);
}

System.out.println("Wartości: ");
for (var value : collection1.values()) {
    System.out.println(value);
}

System.out.println("Pary: ");
for (var entry : collection1.entrySet()) {
    System.out.println(entry.getKey() + " -> " + entry.getValue());
}

System.out.println("Liczba elementów: " + collection1.size());
collection1.remove(2); // usunięcie pary pod kluczem dwa!
System.out.println("Liczba elementów: " + collection1.size());

collection1.clear();
System.out.println("Liczba elementów: " + collection1.size());

W przeciwieństwie do poprzednich kolekcji, dodawanie nowych elementów następuje dzięki metodom put i putAll, a nie add i addAll.

Znacząco też zmieniła się postać pętli foreach. W przypadku map, możemy iterować się po zbiorze kluczy (keySet), zbiorze wartości (values) oraz po zbiorze par (entrySet), gdzie każda para składa się z klucza i wartości.

Przedstawiona wiedza o tablicach i kolekcjach to niestety tylko wierzchołek góry lodowej, zwanej algorytmami i strukturami danych, dlatego zachęcamy wszystkich do rozszerzenia tej wiedzy o stosowne lektury. Java od wersji ósmej ma także dostępny bardzo rozbudowany mechanizm operacji na kolekcjach zwany strumieniami (streams), ale jemu poświęcimy oddzielne wyzwanie.

Wyzwanie

Czas na nasze wyzwanie. Tym razem rozbijemy je na dwie części, pierwszą z zastosowaniem samych struktur danych i drugą, znacznie trudniejszą, gdzie trzeba będzie wymyślić algorytm operujący na tych strukturach.

Zadanie nr 1

Dla tablicy wejściowej input zawierającą liczby typu int zwrócić tablicę zawierającą ilość elementów ujemnych oraz sumę elementów dodatnich. Jeśli tablica będzie pusta lub null, wtedy należy zwrócić pustą tablicę.

public static int[] countAndSumElements(int[] input) {
    // TODO tutaj kod
}

Przykład: Dla werjścia: input int[] {1, 2, 3, 4, 5, -3, -2, -1} program powinien zwrócić: int[] {3, 15}, czyli 3 liczby ujemne i suma liczb dodatnich równa 15.

Zadanie nr 2

Należy stworzyć algorytm sterujący pracą automatu z napojami. Zakładamy, że automat przyjmuje monety 1zł, 2zł i 5zł. Puszka napoju kosztuje 1zł. Na starcie automat nie ma żadnych pieniędzy.

Dla wskazanej listy wejściowej monet, należy zwrócić true lub false w zależności czy automat będzie w stanie zwrócić resztę. Każda moneta jest wrzucana przez innego klienta.

public static boolean vendingMachine(List<Integer> coins) {
    // TODO tutaj kod
}

Przykład: Dla monet: Listcoins = List.of(1, 2, 1, 1, 5) program zwróci wartość true, zaś dla monet: Listcoins = List.of(1, 2, 2, 5, 2) program powinien zwrócić wartość false, gdyż już dla drugiej monety 2zł nie będzie możliwości zwrócenia reszty kupującemu.

Rozwiązanie wyzwania #4 opublikujemy w piątek na stronie naszego wydarzenia na Facebooku.

Jak uda się Wam poprawnie wykonać zadanie - pochwalcie się tym koniecznie w przeznaczonym do tego poście na FB!

Kolejna część wyzwania za tydzień, 14 maja o godz. 10:00.

Powodzenia!

Gotowe rozwiązanie zadania 4 znajdziecie tutaj.

Wszystkie wspisy z serii #javowewyzwanie:

Wprowadzenie

Wyzwanie 1 - Hello world!

Wyzwanie 2 - Podstawowe instrukcje

Wyzwanie 3 - Programowanie obiektowe

Wyzwanie 4 - Algorytmy i struktury danych w języku Java

Wyzwanie 5 - Interfejsy i dziedziczenie