/ / Warum verbraucht mein Code so viel Speicher? - Java, Performance, Scala, Erinnerung

Wodurch verbraucht mein Code so viel Speicher? - Java, Performance, Scala, Erinnerung

Ich habe auf verschiedene Weise ein einfaches Problem in CodeEval gelöst, dessen Spezifikation gefunden werden kann Hier (nur ein paar Zeilen lang).

Ich habe 3 Arbeitsversionen erstellt (eine davon in Scala) und verstehe den Leistungsunterschied für meine letzte Java-Version nicht, von der ich erwartet hatte, dass sie die beste Zeit und Speicher ist.

Ich habe dies auch mit einem Code verglichen, der auf gefunden wurde Github. Hier sind die von CodeEval zurückgegebenen Leistungsstatistiken:

Statistiken

. Version 1 ist die auf Github gefundene Version . Version 2 ist meine Scala-Lösung:

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)
}

. Version 3 ist meine Java-Lösung, von der ich erwartet habe, dass sie die beste ist:

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();
}
}
  • Version 4 ist die gleiche wie Version 3, außer dass ich keine verwende StringBuilder um die Ausgabe zu drucken und wie in Version 1 zu tun

So habe ich diese Ergebnisse interpretiert:

  • Version 1 ist wegen der zu hohen Anzahl von zu langsam System.out.print Anrufe. Darüber hinaus mit split Bei sehr großen Zeilen (das ist bei den durchgeführten Tests der Fall) wird viel Speicher benötigt.

  • Version 2 scheint auch langsam zu sein, aber es liegt hauptsächlich an einem "Overhead" beim Ausführen von Scala-Code auf CodeEval, selbst sehr effizienter Code, der langsam darauf ausgeführt wird

  • Version 2 verwendet unnötigen Speicher, um eine Liste zu erstellenaus dem Set, das auch einige Zeit in Anspruch nimmt, aber nicht zu bedeutend sein sollte. Effizienteres Schreiben von Scala würde es wahrscheinlich gerne in Java schreiben, daher habe ich Eleganz der Leistung vorgezogen

  • Version 3 sollte meiner Meinung nach nicht so viel Speicher verwenden. Die Verwendung von a StringBuilder hat die gleichen Auswirkungen auf den Speicher wie das Aufrufen mkString in Version 2

  • Version 4 beweist die Aufrufe an System.out.println verlangsamen das Programm

Sieht jemand eine Erklärung für diese Ergebnisse?

Antworten:

3 für die Antwort № 1

Ich habe einige Tests durchgeführt.

Für jede Art von Sprache gibt es eine Grundlinie. Ich codiere in Java und Javascript. Für Javascript hier sind meine Testergebnisse:

zufällige Herausforderung

  • Rev 1: Standardmäßig leeres Boilerplate für JS mit einer Meldung an die Standardausgabe
  • Rev 2: Gleiches ohne Lesen von Dateien
  • Rev 3: Nur eine Nachricht an die Standardausgabe

Sie können sehen, egal was passiert, es wird an seinmindestens 200 ms Laufzeit und ca. 5 Megabyte Speicherauslastung. Diese Basislinie hängt auch von der Auslastung der Server ab! Es gab eine Zeit, in der Codeevals stark überlastet waren, so dass es unmöglich war, innerhalb der maximalen Zeit (10s) etwas auszuführen.

Probieren Sie es aus, eine völlig andere Herausforderung als die vorherige: Zufälliges Bild 2.

  • Rev4: Meine Lösung
  • Rev5: Der gleiche Code wurde jetzt erneut übermittelt. Erzielte 8000 weitere Ranglistenpunkte. : D.

Fazit: Ich würde mir keine Sorgen um die CPU- und Speicherauslastung und den Rang machen. Es ist eindeutig nicht zuverlässig.


2 für die Antwort № 2

Ihre Scala-Lösung ist langsam, nicht wegen "Overhead auf CodeEval", sondern weil Sie eine unveränderliche Lösung erstellen TreeSetHinzufügen von Elementen nacheinander. Ersetzen Sie es durch so etwas wie

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

Sollte etwa 30-40% Ihrer Ausführungszeit sparen.

Der gleiche Ansatz (Liste erstellen, dann sortieren) wird wahrscheinlich Ihre Speicherauslastung in "Version 3" verbessern (Java-Sets sind echt Gedächtnisschweine). Es ist auch eine gute Idee, Ihrer Liste eine Anfangsgröße zu geben, während Sie gerade dabei sind (andernfalls wächst sie jedes Mal um 50%, wenn die Kapazität ausgeht, was sowohl für den Speicher als auch für die Leistung verschwenderisch ist). 600 klingt wie a gute Anzahl, da dies die Obergrenze für die Anzahl der Städte aus der Problembeschreibung ist.

Jetzt, da wir die obere Grenze kennen, besteht ein noch schnellerer und schlankerer Ansatz darin, Listen und Boxed Integeres zu beseitigen und dies einfach zu tun int dists[] = new int[600];.

Wenn Sie wirklich schick werden wollten, würden Sie auchVerwenden Sie den in der Beschreibung genannten Bereich "Routenlänge". Erstellen Sie beispielsweise ein Array mit 20.000 Bits (oder sogar 20 KByte für die Geschwindigkeit), anstatt Ints in ein Array zu werfen und zu sortieren (oder einen Baumsatz zu behalten). und legen Sie diejenigen fest, die Sie beim Lesen in der Eingabe sehen ... Das wäre sowohl schneller als auch speichereffizienter als jede Ihrer Lösungen.


1 für die Antwort № 3

Ich habe versucht, diese Frage zu lösen, und festgestellt, dass Sie nicht die Namen der Städte benötigen, sondern nur die Entfernungen in einem sortierten Array.

Es hat eine viel bessere Laufzeit von 738 ms und einen Speicher von 4513792.

Obwohl dies möglicherweise nicht zur Verbesserung Ihres Codes beiträgt, scheint es eine bessere Möglichkeit zu sein, sich der Frage zu nähern. Vorschläge zur weiteren Verbesserung des Codes sind willkommen.

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;
}
}