[aczutuse]

Jak zrobię se algorytm sortowania na ArrayList zamiast [] to będzie znacząco wolniej se?
#java #programowanie

[Karatte]

@aczutuse: nie

[Krolik]

@aczutuse: na 99% będzie identycznie bo ArrayList używa pod spodem zwykłej tablicy, ale jeśli pytasz o takie niuanse wydajnościowe to zapewne wybrałeś zły język. Java i dobra wydajność to oksymoron.

[Triathlete1987]

@aczutuse: ArrayList jest implementacją listy, która działa trochę inaczej niż tablica. W przeciwieństwie do tablic, ArrayList może dynamicznie zmieniać swój rozmiar, co oznacza, że może przechowywać dowolną liczbę elementów. To jednak oznacza, że niektóre operacje na ArrayList mogą być wolniejsze niż na tablicach.

Sortowanie jest jednym z takich przypadków. Sortowanie tablicy jest zwykle szybsze niż sortowanie ArrayList, ponieważ ArrayList musi dynamicznie zarządzać swoim rozmiarem podczas sortowania, co dodaje dodatkowy overhead.

To

[Krolik]

Sortowanie tablicy jest zwykle szybsze niż sortowanie ArrayList, ponieważ ArrayList musi dynamicznie zarządzać swoim rozmiarem podczas sortowania, co dodaje dodatkowy overhead.

@Triathlete1987: co za bzdura, rozmiar listy nie zmienia się w trakcie stosowania.

[Krolik]

@aczutuse: moja poprzednia wypowiedź była niepełna. Jest jednak jeden przypadek kiedy zwykła tablica będzie szybsza - mianowicie jeśli masz tablice elementów prostych (np int, long). Do ArrayList nie wyrzucisz wartości prostych, tylko musisz je opakować w odpowiedni typ opakowujący np. Integer lub Long i te opakowania będą wprowadzać znaczny narzut, ale nie tylko przy sortowaniu ale wszelkich innych operacjach na liście, nie mówiąc już o tym że taka lista będzie zajmować

[Triathlete1987]

@Krolik: Sortowanie tablicy jest zazwyczaj szybsze niż sortowanie ArrayList, ponieważ tablica jest strukturą danych o stałym rozmiarze, podczas gdy ArrayList jest strukturą danych o rozmiarze zmiennym. To oznacza, że sortowanie tablicy nie wymaga alokowania dodatkowej pamięci lub przenoszenia elementów do nowych miejsc w pamięci podczas procesu sortowania. Z tego powodu sortowanie tablicy jest zazwyczaj szybsze niż sortowanie ArrayList.

Należy jednak pamiętać, że różnice w szybkości sortowania mogą zależeć od wielu czynników,

[Krolik]

@Triathlete1987: nie wiesz jak działa sortowanie. W żadnym przypadku nie ma tam żadnej alokacji nowego miejsca. Nie bardzo też rozumiem jak chciałbyś sortować tablice bez przenoszenia elementów na inne miejsca pamięci xD (zakładając że dane na wyjściu są w złej kolejności). Nie przeklejaj więcej odpowiedzi z Chat GPT, bo chat GPT zna się na programowaniu jak świnia na gwiazdach.

[Triathlete1987]

@Krolik: W 5 minut obaliłeś moją teorię - dzięki! ( ͡° ͜ʖ ͡°)

[aczutuse]

@Krolik: niby czemu słaba wydajnosć? tylko 2 razy wolniejsze od jezykow kompilowanych se jest, a nowy gc ZGC ma latency rzędu 5 ms.

[Saly]

@aczutuse: ArrayList to pod spodem tablica obiektów. Jak sortujesz obiekty to jest tak samo. Jak sortujesz prymitywy to może być dużo wolniej. Jest to ograniczenie tego jak działają generyki w Javie. W przyszłości ma temu zaradzić https://openjdk.org/projects/valhalla/ . Dzisiaj jak potrzebujesz wysokiej wydajności to jedyne co zostaje to grzeczne CTRL+C i CTRL+V dla każdego typu prymitywnego, który chcesz wspierać ( ͡° ͜ʖ ͡°) Tak robi klasa Arrays

[aczutuse]

@Triathlete1987: tyko, ze ja se uzywam wlasnego algorytmu sortowania to czu ma mi sie zmieniac se

[aczutuse]

@Saly: sortuję se generyczny obiekt to będzie wolniej?

czyli zamiast robić sortowanie na E[] robię na ArrayjList

[Saly]

a nowy gc ZGC ma latency rzędu 5 ms

@aczutuse: latency != throughput. Niskie latency sprawia, że pauzy są niskie co nie zmienia faktu, że pauz jest dużo. Tradycyjne javowe gc są zoptymalizowane pod throughput. Jak nie dbasz o długość pauz to lepiej dostać jedną x 200 ms niż 100 x 5ms

[Saly]

@aczutuse: jak używasz generyków to jeden pies. ArrayList to pod spodem zwykła tablica https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/util/ArrayList.java#L111 ,

[aczutuse]

@Saly: wiem o tym, ale pod kątem throupput tez jest zoptymalizowany se ale nie znam wartosci

[Saly]

@aczutuse: wszystko jest zoptymalizowane pod latency i throughput ( ͡° ͜ʖ ͡°) Tutaj ważniejsze są priorytety jednego nad drugim. Wybierając niskie latency musisz częściej odpalać gc (żeby robic mniej rzeczy na raz) przez co płacisz dodatkowo za koszt stały jak i narzut całej machinerii gc. Wybierając high throughput może się okazać, że pauza będzie bardzo długa.

[aczutuse]

@Saly: no ja to wiem, jet jeszcze kwestia memory... ale jak pytałem chłopa na rekrutacji o throupghput to powiedział, że nie wie se, ale podjarał się, że latency ma 5 ms... no a requestów na sekundę trochę mieli, jusz nie pamiętam se...

[M.....f]

@aczutuse:

niby czemu słaba wydajnosć? tylko 2 razy wolniejsze od jezykow kompilowanych

Po pierwsze to jakieś banialuki i różnica jest większa, ale nawet jeśli to osoba, której zależy na wydajności wybierze C++/Rusta. Po co walczyć o 5ns w Javie jak można zdobyć sekundy w C++?

[aczutuse]

@Malkof: to poka takie benchmarki, bo te co ja widziałem to różnica była x2. A było to kilka lat temu, java się rozwija, JIT coraz lepszy, gc coraz szybsze.

[Saly]

@aczutuse: w przypadku serwisów jak najniższe latency ma sens, bo w najgorszym przypadku czas requestu jest uzależniony od długości pauzy na wszystkich serwisach w łańcuszku wywołań