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; } }"
@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
@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
@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
@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
@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.
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;
}
}"
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
https://pastebin.com/QTYahtWX
ale wciąż 60% za wydajność
Komentarz usunięty przez autora
@makeDoise: to jakiś raper?
@Krolik: takich rad to nie słuchaj. Po odpaleniu jvm czasem Java wyprzedzi inne "szybsze" jezyki
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
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