[Y.....m]

#naukaprogramowania #programowanie #java

Hej. Proszę o rady, jak usprawnić ten kod, żeby algorytm był szybszy (w rozwiązaniu dostaję 40% za wydajność). I może jakieś rady na przyszłość, w jaki sposób myśleć o podobnych rozwiązaniach, do jakich struktur się odwoływać, jakich unikać itd:

"class Solution {
public int[] solution(int N, int[] A) {
int[] result = new int[N];
for(int i = 0; i < N; i++) {
result[i] = 0;
}
for(int i = 0; i < A.length; i++) {
if(A[i] >= 1 && A[i] <= N) {
result = increase(A[i], result);
} else if (A[i] == N + 1) {
maxCounter(result);
}
}
return result;
}
public int[] increase(int i, int[] j) {
j[i-1] += 1;
return j;
}

public int[] maxCounter(int[] j) {
int maxElement = 0;
for(int i = 0; i < j.length; i++) {
maxElement = Math.max(j[i], maxElement);
}
for(int z = 0; z < j.length; z++) {
j[z] = maxElement;
}
return j;
}
}"

[LazyInitializationException]

@YourDoom: wrzuć na pastebin i poprawnie sformatuj kod

[Saly]

@YourDoom: i powiedz jaki jest problem xd

[Y.....m]

@LazyInitializationException: https://pastebin.com/XtKs5x3K

[Y.....m]

@Saly: You are given N counters, initially set to 0, and you have two possible operations on them:

increase(X) − counter X is increased by 1,
max counter − all counters are set to the maximum value of any counter.
A non-empty array A of M integers is given. This array represents consecutive

[Afropolon]

@YourDoom Ostatni for niepotrzebny wystarczy if w for sprawdzający max i przypisanie. Pierwszy for czyszczący niepotrzebny.

[FocentDiutt]

@YourDoom: masz z zorzonosc kwadratowa, wywal szukanie maxa z maxCounters, i trzymaj/updateuj maxElement i w głównej petli

[makeDoise]

@YourDoom: Panie, a o big O żeś słyszał?

[Y.....m]

@FocentDiutt: @Afropolon: poprawione

https://pastebin.com/QTYahtWX

ale wciąż 60% za wydajność

[Y.....m]

Panie, a o big O żeś słyszał?

@makeDoise: to jakiś raper?

[FocentDiutt]

@YourDoom: moze takie cos, nie testowalem https://pastebin.com/JtS3tP87

[Krolik]

@YourDoom: rada od kogoś siedzącego niemal 20 lat w Javie: jak coś ma być szybkie to nie piszemy tego w Javie :P

[Y.....m]

@FocentDiutt: pętla, którą przeniosłeś, ma się wykonać tylko w szczególnym przypadku, a u ciebie wykonuje się zawsze?

[93michu93]

rada od kogoś siedzącego niemal 20 lat w Javie: jak coś ma być szybkie to nie piszemy tego w Javie :P

@Krolik: takich rad to nie słuchaj. Po odpaleniu jvm czasem Java wyprzedzi inne "szybsze" jezyki

[Krolik]

@93michu93: Tak piszą tylko ludzie, którzy nie potrafią pisać w tych szybszych językach. No chyba że dla Ciebie "szybszy" to Python, to wtedy zgoda.

Bez żadnych specjalnych optymalizacji, naiwnie przepisany kod z Javy do C++ lub Rust zwykle dostaje przyspieszenia w zakresie 2-5x jeśli chodzi o CPU i poprawy 10-100x jeśli chodzi o zużycie pamięci i nawet do 1000x jeśli chodzi o pauzy. Sprawdzone na niezliczonej liczbie realnych projektów. Natomiast

[FocentDiutt]

@YourDoom: tak, ale tylko raz, profit

[93michu93]

@Krolik: a przez te 20 lat klepania w javie ktoś ci o JIT wspomniał? Jeśli nie to doczytać sobie. Kurde nie mogę linka ze stacka wkleić tutaj. Wpisz Java cpp benchmark i na stacji masz ładnie opisane dlaczego have i c# bardzo często mogą być szybsze od cpp albo c

[Krolik]

@93michu93: po pierwsze to nie JIT, Java technicznie nie ma JITa, tylko ma hotspot. I fajnie, że przeczytałeś o tym na Wikipedii, tylko że fakt posiadania kompilatora do kodu maszynowego nie powoduje jeszcze że język jest szybki.

A na great language shout-out Java zawsze solidnie obrywała od cpp i się to nie zmieniło. Przy czym mikrobenchmarki to przypadek mocno optymistyczny dla Javy. Hotspot C2 mocno gubi się przy kodzie większym

[Y.....m]

@FocentDiutt: to muszę się temu przyjrzeć, bo nie przechodzi testów (wyniki niepoprawne)

[file_get_contents]

@YourDoom: Z drobnych rzeczy, to mógłbyś usunąć wyliczanie rozmiaru tablicy za każdym razem w tych pętlach. Nie wiem jaki to ma impakt w javie, ale w php jest zauważalny.