/ / Co powoduje, że mój kod zużywa tak dużo pamięci? - java, performance, scala, memory

Co sprawia, że ​​mój kod zużywa tak dużo pamięci? - java, performance, scala, memory

Na wiele sposobów rozwiązałem prosty problem na CodeEval, którego specyfikację można znaleźć tutaj (tylko kilka linii).

Stworzyłem 3 działające wersje (jedną z nich w Scali) i nie rozumiem różnicy w wydajności dla mojej ostatniej wersji Java, która, jak się spodziewałem, będzie najlepsza pod względem czasu i pamięci.

Porównałem to również z kodem znalezionym na Github. Oto statystyki wydajności zwrócone przez CodeEval:

Statystyki

. Wersja 1 to wersja znaleziona na Github . Wersja 2 to moje rozwiązanie Scala:

object Main extends App {
val p = Pattern.compile("\d+")
scala.io.Source.fromFile(args(0)).getLines
.filter(!_.isEmpty)
.map(line => {
val dists = new TreeSet[Int]
val m     = p.matcher(line)
while (m.find) dists += m.group.toInt

val list  = dists.toList
list.zip(0 +: list).map { case (x,y) => x - y }.mkString(",")
})
.foreach(println)
}

. Wersja 3 to moje rozwiązanie Java, które spodziewałem się być najlepszym:

public class Main {
public static void main(String[] args) throws IOException {
Pattern        p    = Pattern.compile("\d+");
File           file = new File(args[0]);
BufferedReader br   = new BufferedReader(new FileReader(file));

String line;
while ((line = br.readLine()) != null) {
Set<Integer> dists = new TreeSet<Integer>();
Matcher      m     = p.matcher(line);
while (m.find()) dists.add(Integer.parseInt(m.group()));

Iterator<Integer> it   = dists.iterator();
int               prev = 0;
StringBuilder     sb   = new StringBuilder();
while (it.hasNext()) {
int curr = it.next();
sb.append(curr - prev);
sb.append(it.hasNext() ? "," : "");
prev = curr;
}
System.out.println(sb);
}
br.close();
}
}
  • Wersja 4 jest taka sama jak wersja 3, z tym że nie używam StringBuilder aby wydrukować wyjście i zrobić coś podobnego w wersji 1

Oto jak zinterpretowałem te wyniki:

  • wersja 1 jest zbyt wolna z powodu zbyt dużej liczby System.out.print połączenia. Ponadto za pomocą split na bardzo dużych liniach (tak jest w przeprowadzanych testach) zużywa dużo pamięci.

  • wersja 2 wydaje się również powolna, ale wynika to głównie z „narzutu” związanego z uruchomieniem kodu Scala na CodeEval, nawet bardzo wydajny kod działa na nim powoli

  • wersja 2 wykorzystuje niepotrzebną pamięć do zbudowania listyz zestawu, co również zajmuje trochę czasu, ale nie powinno być zbyt duże. Bardziej wydajne pisanie Scali prawdopodobnie chciałoby pisać w Javie, więc wolałem elegancję od wydajności

  • moim zdaniem wersja 3 nie powinna zużywać tyle pamięci. Zastosowanie StringBuilder ma taki sam wpływ na pamięć jak dzwonienie mkString w wersji 2

  • wersja 4 potwierdza połączenia z System.out.println spowalniają program

Czy ktoś widzi wyjaśnienie tych wyników?

Odpowiedzi:

3 dla odpowiedzi № 1

Przeprowadziłem kilka testów.

Istnieje podstawa dla każdego rodzaju języka. Piszę w java i javascript. Dla javascript tutaj są moje wyniki testu:

losowe wyzwanie

  • Rev 1: Domyślnie pusta płyta kotła dla JS z komunikatem na standardowe wyjście
  • Rev 2: To samo bez odczytu pliku
  • Rev 3: Tylko wiadomość na standardowe wyjście

Widać, że bez względu na wszystko, będzieczas działania co najmniej 200 ms i zużycie pamięci około 5 megabajtów. Ta linia bazowa zależy również od obciążenia serwerów! Był czas, gdy znaczniki kodu były mocno przeciążone, przez co niemożliwe było uruchomienie czegokolwiek w maksymalnym czasie (10s).

Sprawdź to, zupełnie inne wyzwanie niż poprzednie: Losowe zdjęcie 2.

  • Rev4: Moje rozwiązanie
  • Rev5: Ten sam kod przesłany ponownie teraz. Zdobyłem 8000 punktów rankingowych. :RE

Wniosek: nie martwiłbym się zbytnio zużyciem procesora i pamięci oraz rangą. To oczywiście nie jest wiarygodne.


2 dla odpowiedzi nr 2

Twoje rozwiązanie scala działa powoli, nie z powodu „narzutu na CodeEval”, ale dlatego, że budujesz niezmienny TreeSet, dodając do niego elementy jeden po drugim. Zastąpienie go czymś takim

val regex = """d+""".r // in the beginning, instead of your Pattern.compile
...
.map { line =>
val dists = regex.findAllIn(line).map(_.toInt).toIndexedSeq.sorted
...

Powinieneś golić około 30-40% rabatu na czas realizacji.

To samo podejście (budowanie listy, a następnie sortowanie) prawdopodobnie pomoże w wykorzystaniu pamięci w „wersji 3” (zestawy Java są real świnie pamięci). Dobrym pomysłem jest również nadanie początkowej wielkości twojej liście podczas jej trwania (w przeciwnym razie wzrośnie o 50% za każdym razem, gdy skończy się pojemność, co jest marnotrawstwem zarówno pod względem pamięci, jak i wydajności). 600 brzmi jak dobra liczba, ponieważ jest to górna granica liczby miast z opisu problemu.

Ponieważ znamy górną granicę, jeszcze szybszym i szczuplejszym podejściem jest zlikwidowanie list i liczb całkowitych w pudełku i po prostu int dists[] = new int[600];.

Jeśli chcesz się naprawdę zachwycić, to teżskorzystaj z zakresu „długości trasy”, który jest wymieniony w opisie. Na przykład zamiast wrzucania liczb całkowitych do tablicy i sortowania (lub utrzymywania zestawu drzew), utwórz tablicę 20 000 bitów (lub nawet 20 000 bajtów dla prędkości) i ustaw te, które widzisz na wejściu podczas czytania ... Byłoby to zarówno szybsze, jak i bardziej wydajne pod względem pamięci, niż jakiekolwiek z twoich rozwiązań.


1 dla odpowiedzi nr 3

Próbowałem rozwiązać to pytanie i doszedłem do wniosku, że nie potrzebujesz nazw miast, a jedynie odległości w posortowanej tablicy.

Dzięki temu zapewnia znacznie lepszy czas działania wynoszący 738 ms i pamięć 4513792.

Chociaż może to nie pomóc w ulepszeniu twojego kodu, wydaje się, że jest to lepszy sposób na podejście do pytania. Wszelkie sugestie dotyczące dalszego ulepszania kodu są mile widziane.

import java.io.*;
import java.util.*;

public class Main {
public static void main (String[] args) throws IOException {
File file = new File(args[0]);
BufferedReader buffer = new BufferedReader(new FileReader(file));
String line;
while ((line = buffer.readLine()) != null) {
line = line.trim();

String out = new Main().getDistances(line);

System.out.println(out);
}
}

public String getDistances(String s){

//split the string
String[] arr = s.split(";");

//create an array to hold the distances as integers
int[] distances = new int[arr.length];

for(int i=0; i<arr.length; i++){
//find the index of , - get the characters after that - convert to integer - add to distances array
distances[i] = Integer.parseInt(arr[i].substring(arr[i].lastIndexOf(",")+1));
}

//sort the array
Arrays.sort(distances);

String output = "";
output += distances[0]; //append the distance to the closest city to the string

for(int i=0; i<arr.length-1; i++){

//get distance between current element(city) and next
int distance_between = distances[i+1] - distances[i];

//append the distance to the string
output += "," + distance_between;
}


return output;
}
}