Wydajne struktury danych: zbiory i mapy

Optymalizacja kodu w Javie

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Złożoność czasowa i pamięciowa w praktyce

Znamy już złożoność czasową i pamięciową!

Jak wykorzystać tę wiedzę, żeby pisać bardziej wydajny kod?

Wybierając odpowiednią strukturę danych!

System zarządzania użytkownikami

Budujemy system zarządzania użytkownikami
Musimy sprawdzić, czy użytkownik o danej nazwie istnieje
Używając listy: złożoność $O(n)$

public boolean usernameExists(ArrayList<String> users, String newUsername) {
    for (String username : users) {
        if (username.equals(newUsername)) {
            return true;
        }
    }
    return false;
}

Zbiory

Kolekcja unikalnych elementów z szybkim wyszukiwaniem
Średnia złożoność czasowa $O(1)$ dla dodawania, usuwania i sprawdzania, czy element istnieje

Ulepszone rozwiązanie systemu zarządzania użytkownikami:

public class UserRegistry {
    private HashSet<String> users = new HashSet<>();

    public boolean userExists(String username) {
        return users.contains(username); // O(1) average time
    }
}

Mapy

Jak słownik: słowo (klucz) -> definicja (wartość)
HashMap: średnia złożoność czasowa $O(1)$ dla operacji

public class UserCache {
    private HashMap<String, UserProfile> userProfiles = new HashMap<>();

    public UserProfile getUser(String username) {
        return userProfiles.get(username);  // O(1) average time
    }
}

Metoda hashcode

Co sprawia, że są szybkie -> hashCode()
W przykładzie z ArrayList nie znaliśmy indeksu szukanej nazwy użytkownika
Metoda hashcode() pozwala zamienić obiekt na indeks, którego możemy szukać
Na przykład pavlos.2020 -> 35189

pavlos.2020 przetworzone przez hashcode, wynik: 35189

Indeksowanie elementów

HashMap i HashSet mają pod spodem tablicę
Podczas dodawania elementu:
- Java wywołuje hashCode() na twoim elemencie, żeby uzyskać liczbę całkowitą
- Wykonuje na niej modulo, żeby ustalić numer kubełka

Przykład:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

"optimizingCodeInJava" -> 1406313774 // Implemented by Java
1406313774 % 16 = 14 <- that's our bucket!

Kolizje

Gdy kilka elementów trafia do tego samego kubełka
- To tzw. kolizja
Kubełek to LinkedList
Dlatego mówimy o $O(1)$ średnio

Warto zapamiętać

Wybór struktury danych przypomina dobór odpowiedniego narzędzia do pracy - młotek (ArrayList) świetnie sprawdza się przy gwoździach, ale słabo przy śrubach (gdzie lepiej sprawdzi się Set).

Otwarta skrzynka z narzędziami: młotek, śrubokręt, klucz i szczypce obok siebie

Czas na praktykę!

Optymalizacja kodu w Javie