Browse Category: Notatki

Notatka: Sortowanie bąbelkowe

Zacząłem sobie przypominać czy też uczyć się algorytmów, ostatnio przerobiłem drzewo binarne jako strukturę danych, dzisiaj zabiorę się za Sortowanie Bąbelkowe.

Na czym polega ten algorytm?

Jak sama nazwa wskazuje jest to algorytm sortujący dane, nie jest on najszybszy ale o tym za chwilę. Algorytm ten jest stosunkowo prosty w implementacji. Swoją nazwę wziął od tego, że największa liczba w sortowanej kolekcji jest podobna do pęcherzyka powietrza (bąbelka) wypływającego pod wpływam ciśnienia z wody. Tutaj tak samo tutaj “wypychamy” największą liczbę na ostatnie miejsce (też zależy w którą stronę sortujemy). Efekt ten uzyskuję się poprzez zamianę dwóch sąsiadujących elementów kolekcji, w taki sposób, że gdy liczba na pozycji N jest mniejsza niż następna czyli N+1 to trzeba je zamienić miejscami.

Przykład:

Dłuższy przykład można zobaczyć tutaj: link. Pan programista (jak mniemam) świetnie pokazuje przykład sortowania bąbelkowego krok po kroku, polecam. Ja pokaże to tylko na 4 liczbach:

[4, 1, 3, 2]

Aby posortować taką tablicę należy wykonać następujące czynności:

  • porównać 4 i 1, 4 jest większe więc zamieniamy z 1 i jest: [1, 4, 3, 2]
  • porównać 4 i 3, 4 jest większe więc zamieniamy z 3 i jest: [1, 3, 4, 2]
  • porównać 4 i 2, 4 jest większe wiec zamieniamy z 2 i jest: [1, 3, 2, 4]

W ten sposób “przepchnęliśmy” największą liczbę czyli 4 na koniec kolekcji. Oczywiście to nie koniec bo taką operację trzeba powtórzyć tak aby całość była przesortowana. Złożoność obliczeniowa w najgorszym przypadku to O(n2) więc może to trochę potrwać. Zatem dalej porównując:

  • porównać 1 i 3, 1 jest mniejsze więc zostaje na swojej pozycji
  • porównać 3, 2, 3 jest większe więc zamieniamy z 2 i jest: [1, 2, 3, 4]
  • porównać 3 i 4, 3 jest mniejsze więc zostaje na swojej pozycji

Mogło by się wydawać, że to już koniec ale w niezoptymalizowanej wersji algorytmu wykona się to wszystko jeszcze raz pomimo, że kolekcja jest już posortowana.

Złożoność obliczeniowa i optymalizacja

W najgorszym przypadku jest to właśnie O(n2), jeśli użyjemy optymalizacji można w najlepszym przypadku zejść do O(n) a w typie optymalizacji użytym na filmie O(n) i złożoności pamięci O(1). Tak jak pokazał to Pan na filmie, można to zoptymalizować na 2 sposoby. Ja pisząc swój algorytm na początku z głowy, szukając czy dałoby się to napisać funkcyjnie, natknąłem się na inne możliwości zapisu algorytmu a także kolejną formę optymalizacji.

  1. Optymalizacja 1 – brak sprawdzania całości jeszcze raz po przesortowaniu, trzeba dołożyć dodatkową flagę i jeśli nie było “zamian” w poprzednim przejściu to zakończyć pętlę sprawdzania bo mamy już tablicę przesortowaną na 100%
  2. Optymalizacja 2 – brak sprawdzania liczb które są najbardziej od prawej, w skrócie jeśli mamy 2,1, 3, 6, 7, 8 to po co sprawdzać za każdym następnym przejściem 6, 7, 8? Przecież one już się nie zmienią. Czyli jeśli nie było zamiany z ostatnią pozycją to zmniejszamy długość sprawdzania o 1 i tak za każdym razem.
  3. Optymalizacja 3 – znaleziona tu, jest to jakby połączenie dwóch poprzednich optymalizacji, algorytm zatrzymuje się jeśli w poprzednim przebiegu nie było żadnej zmiany oraz nie uwzględnia ostatnich pozycji

Kod:

Aby pokazać różnice czasowe i ilości porównań stworzyłem sobie klasę implementującą 3 interfejsy, Sort, OptimizedSort, SuperOptimizedSort (tak wiem nazwy mogłyby być lepsze :)). Są 3 i są generyczne, ponieważ mogą mi się jeszcze przydać przy następnych algorytmach i dla innych typów, poza tym zachowana zostaje zasada Segregacji Interfejsów (I w mnemoniku SOLID). Następnie zaimplementowałem w klasie BubbleSort wszystkie 3 metody (po jednej z każdego interfejsu). Następnie wrzuciłem to w wątki bo przy większych liczbach może to być czasowo problematyczne. Dodałem też drukowanie ilości porównań wewnątrz algorytmu.

Interfejsy:

public interface SortAlgorithm> {
    T[] sort(T[] arrayToSort);
}
public interface OptimizedSort> {
    T[] optimizedSort(T[] arrayToSort);
}
public interface SuperOptimizedSort {
    T[] mostOptimizedSort(T[] arrayToSort);
}

Klasa BubbleSort:

package sorting;

import static java.lang.String.format;

public class BubbleSort> implements SortAlgorithm, OptimizedSort, SuperOptimizedSort {

    //iteration way, non optimized
    @Override
    public T[] sort(T[] arrayToSort) {
        int count = 0;
        for (int i = 0; i < arrayToSort.length - 1; i++) {
            for (int j = 0; j < arrayToSort.length - 1; j++) {
                count++;
                if (arrayToSort[j].compareTo(arrayToSort[j + 1]) > 0) {
                    swapElements(arrayToSort, j, j + 1);
                }
            }
        }
        printNumberOfComparisions(count, "(non optimized)");
        return arrayToSort;
    }

    //optimized sort with additional flag
    @Override
    public T[] optimizedSort(T[] arrayToSort) {
        int count = 0;
        boolean swapped = true;
        for (int i = 1; i < arrayToSort.length && swapped; i++) {
            swapped = false;
            for (int j = 0; j < arrayToSort.length - i; j++) {
                count++;
                if (arrayToSort[j].compareTo(arrayToSort[j + 1]) > 0) {
                    swapElements(arrayToSort, j, j + 1);
                    swapped = true;
                }
            }
        }
        printNumberOfComparisions(count, "(optimized)");
        return arrayToSort;
    }

     /* optimized way 1 + 2 from here: http://www.algorytm.org/algorytmy-sortowania/sortowanie-babelkowe-bubblesort/bubble-3-j.html */
    @Override
    public T[] mostOptimizedSort(T[] arrayToSort) {
        int count = 0;
        int n = arrayToSort.length - 1;
        while (n > 0) {
            int last = 0;
            for (int j = 0; j < n; j++) {
                count++;
                if (arrayToSort[j].compareTo(arrayToSort[j + 1]) > 0) {
                    swapElements(arrayToSort, j, j + 1);
                    last = j;
                }
            }
            n = last;
        }
        printNumberOfComparisions(count, "(most optimized)");
        return arrayToSort;
    }

    private void swapElements(T[] arrayToSort, int i, int j) {
        T temp = arrayToSort[i];
        arrayToSort[i] = arrayToSort[j];
        arrayToSort[j] = temp;
    }

    private void printNumberOfComparisions(int count, String typeOfOptimization) {
        System.out.printf("Number of comparisions %s: %d%n", typeOfOptimization, count);
    }
}

Klasa Main gdzie tworze sobie wątki:

import java.util.Arrays;
import java.util.Random;

public class Main {

    public static void main(String[] args) throws InterruptedException {
        Random random = new Random();
        Integer[] array = new Integer[1000];
        
        final int length = array.length;
        array = Arrays.stream(array).map(x -> random.nextInt(length)).toArray(Integer[]::new);

        final Integer[] copyOfArray = Arrays.copyOf(array, array.length);

        Thread t = getThreadWithTimeCounter(() -> printAfterSort(copyOfArray), "non-sorted");
        t.start();

        Thread t1 = getThreadWithTimeCounter(() -> printAfterOptimizedSort(copyOfArray), "optimized");
        t1.start();

        Thread t2 = getThreadWithTimeCounter(() -> printAfterMostOptimizedSort(copyOfArray), "most-optimized");
        t2.start();
    }

    private static Thread getThreadWithTimeCounter(Runnable runnable, String name) {
        Thread t = new Thread(() -> {
            long startTime = System.currentTimeMillis();
            runnable.run();
            long endTime = System.currentTimeMillis();
            System.out.printf("Time in millis for runnable %s %d%n", name,  endTime - startTime);
        });
        return t;
    }

    private static void printAfterSort(Integer[] array) {
        Integer[] copy = Arrays.copyOf(array, array.length);
        BubbleSort bubbleSort = new BubbleSort<>();
        bubbleSort.sort(copy);
//        System.out.println(Arrays.toString(bubbleSort.sort(copy)));
    }

    private static void printAfterOptimizedSort(Integer[] array) {
        Integer[] copy = Arrays.copyOf(array, array.length);
        OptimizedSort optimizedSort = new BubbleSort<>();
        optimizedSort.optimizedSort(copy);
//        System.out.println(Arrays.toString(optimizedSort.optimizedSort(copy)));
    }

    private static void printAfterMostOptimizedSort(Integer[]  array) {
        Integer[] copy = Arrays.copyOf(array, array.length);
        SuperOptimizedSort bubbleSort = new BubbleSort<>();
        bubbleSort.mostOptimizedSort(copy);
//    
 System.out.println(Arrays.toString(bubbleSort.mostOptimizedSort(copy)));
    }
}

Wnioski:

O ile w mniejszych zbiorach danych nie widać szczególnej różnicy między Optymized i SuperOptimized to w przypadku większych zbiorów różnice są zauważalne.

Dla 100_000 elementów wyniki przedstawiają się u mnie następująco:

Number of comparisions (most optimized): 704632143
Time in millis for runnable most-optimized: 50785

Number of comparisions (optimized): 704948251
Time in millis for runnable optimized: 51876

Number of comparisions (non optimized): 1409865409
Time in millis for runnable non-sorted: 96376

Widać więc ile porównań było w najmniej optymalnej wersji, jest to cały rząd wielkości więcej porównań. Algorytmy optymalne różnią się o 316_108 porównań, to dość sporo, choć czasowo to tylko około sekunda różnicy.

Algorytm bąbelkowy nie może wydajny ale ma fajną nazwę, do tego jest dość prosty w implementacji, więc można go łatwo przyswoić.

Linki z których korzystałem:

http://www.algorytm.org/algorytmy-sortowania/sortowanie-babelkowe-bubblesort/bubble-3-j.html

https://stackoverflow.com/questions/27639792/java-implementation-of-bubble-sort-in-functional-style

Notatka: Binary Tree

Ta notatka dotyczy dość znanej i popularnej strukturze jaką jest drzewo binarne.

Co to jest drzewo binarne?

Drzewa posiadają korzeń, gałęzie oraz liście, w strukturze drzewa jest podobnie, z tym, że jest różne nazewnictwo poszczególnych elementów takiej struktury. Drzewo binarne wyróżnia się tym, że liczba gałęzi od każdego wierzchołka nie jest większa niż 2. Powiedzmy, że pierwszym wierzchołkiem jest korzeń, nie może mieć on więcej niż 2 dzieci, następnie schodzimy niżej i każde z jego dzieci też nie może mieć więcej niż 2 dzieci i tak dalej…

https://www.pngitem.com/pimgs/m/491-4915022_binary-search-tree-hd-png-download.png

Jak widać na powyższym drzewie, wierzchołek może mieć maksymalnie 2 gałęzie, ale może mieć też 1.

Szukanie w drzewie binarnym

Aby wyszukiwać w drzewie binarnym powinno być ono prawidłowo poukładane/posortowane, gałąź po lewej stronie zawsze powinna mieć niższą wartość niż gałąź po prawej stronie. Jest to wtedy tak zwane Binarne Drzewo Poszukiwań (BST – Binary Search Tree). Sprawia to, że bardzo łatwo szukać elementu w takim drzewie. Powiedzmy, że w strukturze której zdjęcie jest wyżej, chcemy wyszukać liczbę 4. Idąc od góry sprawdzamy czy liczba 4 jest większa czy mniejsza niż root (8), jest mniejsza więc idziemy w lewą stronę, teraz czy liczba 4 jest większa czy mniejsza niż liczba 3? Jest większa więc idziemy w prawo, jesteśmy teraz przy liczbie 6 która jest większa niż 4 więc idziemy w lewo. I voila! Po 3 sprawdzeniach znaleźliśmy liczbę.

W Javie to będzie np. taki kod, samo sprawdzanie czy element istnieje w drzewie:

/* 
ten kod pochodzi z tego filmu: https://www.youtube.com/watch?v=oSWTXtMglKE 
aczkolwiek przepisałem go do IDE i w pełni go rozumiem 
*/
public class Node {

    private Node left, right;
    private final int data;

    public Node(int data) {
        this.data = data;
    }

    public boolean contains(int value) {
        if (value == data) {
            return true;
        } else if (value < data) {
            if (left == null) {
                return false;
            } else {
                return left.contains(value);
            }
        } else {
            if (right == null) {
                return false;
            } else {
                return right.contains(value);
            }
        }
    }
}

Dodawanie elementu do drzewa

Dodawanie odbywa się w taki sam sposób jak wyszukiwanie wartości z tym, że szukamy dogodnego miejsca do umieszczenia nowego elementu. Sprawdzamy czy wartość nowego elementu, jest mniejsza czy większa niż porównywany wierzchołek. Jeśli mniejsza to idziemy w lewo, jeśli większa to w prawo, i tak aż znajdziemy miejsce...

W Javie można to napisać z użyciem rekurencji:

/* 
ten kod pochodzi z tego filmu: https://www.youtube.com/watch?v=oSWTXtMglKE 
aczkolwiek przepisałem go do IDE i w pełni go rozumiem 
*/
public void insert(int value) {
    if (value <= data) {
        if (left == null) {
            left = new Node(value);
        } else {
            left.insert(value);
        }
    } else {
        if (right == null) {
            right = new Node(value);
        } else {
            right.insert(value);
        }
    }
}

Jaki jest problem z wyszukiwaniem i dodawaniem nowego elementu?

Jeśli dodajemy posortowane elementy, to po prostu robi nam się zwykła lista (taka jedna długa gałąź), co znacznie obniża efektywność takiego rozwiązania, w najgorszym przypadku wpadamy w złożoność obliczeniową O(n) czy to przy wyszukiwaniu z takiego "drzewa" czy przy dodawaniu. Zoptymalizowane drzewa mają tą złożoność na poziomie O(log n). Takie drzewo to np. drzewo czerwono-czarne.

Przechodzenie po drzewie - traversing

Są 3 sposoby przechodzenia po drzewie binarnym. Uporządkowane (inorder), ?przed uporządkowaniem? (preorder) i ?po uporządkowaniu? (postorder). Nie wiem jak to do końca dobrze przetłumaczyć więc tak to zostawię.

  • Preorder - root, później lewa, później prawa
  • Inorder - lewa, root, prawa
  • Postorder - lewa, prawa, root

Najlepiej jest przechodzić w sposób inorder czyli uporządkowany wtedy idąc od lewej do prawej, wartości wierzchołków są w kolejności rosnącej.

Drukowanie inorder, pozostałem przechodzenia wyglądają tak samo tylko trzeba pozamieniać linie.

/* 
ten kod pochodzi z tego filmu: https://www.youtube.com/watch?v=oSWTXtMglKE 
aczkolwiek przepisałem go do IDE i w pełni go rozumiem 
*/
public void printInOrder() {
        if (left != null) {
            left.printInOrder();   // (1)
        }
        System.out.println(data); //(2)
        if (right != null) {
            right.printInOrder(); //(3)
        }
}

Jeśli chcemy wydrukować w kolejnośći preorder to będzie idąc od góry (2), (1), (3), a jeśli w kolejności postorder to: (1), (3), (2).

Zadanie z drzewem binarnym

Dana funkcja isBinaryTree(strArr) jako argument przyjmuje tablicę Stringów, tablica ta zawiera pary liczb w następującym formacie: (i1, i2), gdzie i1 reprezentuje gałąź dziecko, a i2 reprezentuje gałąź rodzica dla i1. Np. ["(1, 2)", "(2, 4)", "(7, 2)"], jest to wtedy poprawne drzewo binarne, ponieważ każda gałąź ma nie więcej niż dwoje dzieci. Program ma zwracać boolean true jeśli dane drzewo jest poprawnym drzewem binarnym, i false jeśli nie jest. Wszystkie dane gałęzie będą unikalne to znaczy będzie tylko jeden node z daną wartością np. 2.

Moje rozwiązanie:

public static boolean isBinaryTree(String[] nodeValuesArray) {
    //najpierw wyjąłbym sobie wartości liczbowe z typu String
    Integer[] numbers = convertToIntegerArray(nodeValuesArray);
    /* żaden node nie może być rodzicem więcej niż 2 razy,
        można wywnioskować że wystarczy po prostu sprawidzić czy liczba na drugiej pozycji występuje więcej
        niż 2 razy, jeśli nie, to będzie to poprawne drzewo binarne */
    Map collect = IntStream.range(0, numbers.length)
            .filter(i -> i % 2 == 0)
            .map(i -> numbers[i+1])
            .boxed()
            .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
    return collect.values().stream().noneMatch(occurrence -> occurrence > 2);
}

private static Integer[] convertToIntegerArray(String[] nodeValuesArray) {
    return Arrays.stream(nodeValuesArray)
            .map(string -> string.replaceAll("\\)|\\(", ""))
            .map(string -> string.split(","))
            .flatMap(Stream::of)
            .map(Integer::parseInt)
            .toArray(Integer[]::new);
}

public static void main(String[] args) {
        String[] firstTree = {"(1,2)", "(2,4)", "(5,7)", "(7,2)", "(9,5)"};
        String[] secondTree = {"(1,2)", "(3,2)", "(2,12)", "(5,2)"};
        String[] thirdTree = {"(3,8)", "(10,8)", "(1,3)", "(6,3)", "(4,6)", "(7,6)", "(14,10)", "(13,14)"};

        System.out.println(isBinaryTree(firstTree)); //output true
        System.out.println(isBinaryTree(secondTree)); //output false
        System.out.println(isBinaryTree(thirdTree)); //output true
    }

Trochę "shackowałem" system bo nie użyłem nigdzie algorytmu drzewa, sprawdziłem po prostu czy "rodzic" występuje w tablicy stringów więcej niż 2 razy, jeśli tak to drzewo nie jest poprawne bo może mieć maksymalnie dwoje dzieci. Jak widać trzy podane "testy" przeszły, jeśli jednak jest jakieś drzewo, które jest poprawne a mój algorytm zwraca zły wynik, skontaktuj się ze mną abym mógł poprawić rozwiązanie.

Linki:

https://pl.wikipedia.org/wiki/Drzewo_binarne

https://pl.wikipedia.org/wiki/Binarne_drzewo_poszukiwa%C5%84

Notatka: Cachowanie w Springu

Cachowanie – zapisywanie danych lub wyników jakiejś operacji (możliwe że długotrwałej lub łączącej się z bazą danych) w pamięci o lepszych parametrach w celu optymalizacji dostępu do danych (w najbliższym czasie) oraz odciążenia zasobów.

W samym hibernate istnieją trzy rodzaje cache: cache I poziomu (na poziomie sesji), cache II poziomu (na poziomie SessionFactory) oraz query cache (do cachowania zapytań do bazy danych).

Oprócz tego istnieje także Spring Cache, czyli cache na poziomie aplikacji.

Aby użyć cache w Springu należy (używając Spring Boot):

  • pobrać zależnośći do projektu – Spring Cache oraz zewnętrznego providera, jednego z dostępnych który implementuje standard JSR-107 (inaczej JCache). Dostępni providerzy to: EhCache3, HazelCast, Caffeine. Można tez korzystać z Redisa, ja skorzystam z EhCache3.
<dependency>
  <groupId>org.springframework.boot</groupId>
  <artifactId>spring-boot-starter-cache</artifactId>
</dependency>
<dependency>
  <groupId>org.ehcache</groupId>
  <artifactId>ehcache</artifactId>
  <version>${ehcache.version}</version>
</dependency>
  • dodać properties ze ścieżką konfiguracyjną do EhChache3 do application.properties (lub yaml jak ktoś woli)
spring.cache.ehcache.config=classpath:ehcache.xml
  • dodać plik konfiguracyjny (który nazwałem ehcache.xml) do folderu resources, nagłówki xml można skopiować z dokumentacji EhCache3. Można też skonfigurować providera programowo
<cache-template name="default">
  <key-type>java.lang.Long</key-type>
  <expiry>
    <ttl unit="minutes">30</ttl>
  </expiry>
  <resources>
    <heap unit="entries">1000</heap>
    <offheap unit="MB">500</offheap>
  </resources>
</cache-template>
<cache alias="findAllBooks" uses-template="default"/>
<cache alias="findBookById" uses-template="default"/>
<cache alias="findAllPosts">
  <expiry>
    <ttl unit="minutes">10</ttl>
  </expiry>
  <heap unit="entries">500</heap>
</cache>

Jak widać można użyć cache-template i predefiniować sobie ustawienia lub dla każdego cache użyć innych ustawień jak np. czas po którym wpis z cache ma zostać usunięty.

  • użyć adnotacji @Cacheable na metodzie którą chce się cachować, np. w taki sposób:
@Transactional
@Cacheable(cacheNames = "findBookById", key = "#id")
public Book findById(Long id) {
    return bookRepository.findById(id).orElseThrow(
exceptionHelper.getEntityNotFoundException(id, Book.class));
}

I już, meotda (o nazwie cache która powinna być taka sama zarówno na metodzie jak i w pliku konfiguracyjnym) będzie cachowana po kluczu id!

Dodatkowe proste metody to:

@CachePut(cacheNames = "findBookById", key = "#result.id")

który służy do update wpisu w cache po danym kluczu, oraz

@CacheEvict(cacheNames = "findBookById")

która czyści cache o danej nazwie (można ustawić np. na metodzie usuwającej rekord z bazy danych).

Problem z @CachePut pojawia się jeśli chce się updatować całą kolekcję, nie ma wbudowanej adnotacji (z tego co mi wiadomo) i trzeba sobie radzić samemu. Ja po zasięgnięciu opinii ze StackOverFlow postanowiłem po prostu czyścić cache listy po update jednego rekordu. Może jest to trochę nadmiarowe jednak wydaję sie, że poprawne. Aby to zrobić trzeba wstrzyknąć CacheManager cachemanager; a następnie wyczyścić cache metodą: cacheManager.getCache("findAllBooks").clear();

Narazie to tyle ile wiem na temat cache springowego, jeśli dowiem się coś więcej będę dopisywał w tym poście.

Linki:

Dokumentacja EhCache3: https://www.ehcache.org/documentation/3.0/

Cachowanie w Spring Boot: https://www.youtube.com/watch?v=lWv3uBLO2LU


Close Bitnami banner
Bitnami