/ / Qu'est-ce qui fait que mon code utilise autant de mémoire? - java, performance, scala, mémoire

Qu'est-ce qui fait que mon code utilise autant de mémoire? - java, performance, scala, mémoire

J'ai résolu de diverses manières un problème simple sur CodeEval, quelle spécification peut être trouvée ici (seulement quelques lignes).

J'ai fait 3 versions de travail (dont une en Scala) et je ne comprends pas la différence de performances pour ma dernière version Java que je pensais être la meilleure en termes de temps et de mémoire.

J'ai également comparé cela à un code trouvé sur Github. Voici les statistiques de performances renvoyées par CodeEval:

Statistiques

. La version 1 est la version trouvée sur Github . La version 2 est ma solution 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)
}

. La version 3 est ma solution Java que je m'attendais à être la meilleure:

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();
}
}
  • La version 4 est la même que la version 3 sauf que je n'utilise pas de StringBuilder pour imprimer la sortie et faire comme dans la version 1

Voici comment j'ai interprété ces résultats:

  • la version 1 est trop lente en raison du nombre trop élevé de System.out.print appels. De plus, en utilisant split sur de très grandes lignes (c'est le cas dans les tests effectués) utilise beaucoup de mémoire.

  • la version 2 semble lente aussi mais c'est principalement à cause d'un "overhead" sur l'exécution du code Scala sur CodeEval, même du code très efficace qui s'exécute lentement dessus

  • la version 2 utilise de la mémoire inutile pour construire une listede l'ensemble, ce qui prend également un certain temps mais ne devrait pas être trop important. Écrire un Scala plus efficace voudrait probablement l'écrire en Java, j'ai donc préféré l'élégance à la performance

  • la version 3 ne devrait pas utiliser autant de mémoire à mon avis. L'utilisation d'un StringBuilder a le même impact sur la mémoire que l'appel mkString dans la version 2

  • la version 4 prouve les appels à System.out.println ralentissent le programme

Quelqu'un voit-il une explication à ces résultats?

Réponses:

3 pour la réponse № 1

J'ai effectué quelques tests.

Il existe une base de référence pour chaque type de langue. Je code en java et javascript. Pour javascript voici mes résultats de test:

défi aléatoire

  • Rev 1: passe-partout vide par défaut pour JS avec un message vers la sortie standard
  • Rev 2: Même sans lecture de fichier
  • Rev 3: juste un message à la sortie standard

Vous pouvez voir que peu importe quoi, il y auraau moins 200 ms d'exécution et environ 5 Mo d'utilisation de la mémoire. Cette base dépend également de la charge des serveurs! Il fut un temps où les codesevals étaient lourdement surchargés, rendant ainsi impossible d'exécuter quoi que ce soit dans le délai maximum (10s).

Découvrez ceci, un défi totalement différent du précédent: Pic aléatoire 2.

  • Rev4: Ma solution
  • Rev5: Le même code soumis à nouveau maintenant. A marqué 8000 points de classement supplémentaires. :RÉ

Conclusion: je ne m'inquiéterais pas trop de l'utilisation et du classement du processeur et de la mémoire. Ce n'est clairement pas fiable.


2 pour la réponse № 2

Votre solution scala est lente, non pas à cause des "frais généraux sur CodeEval", mais parce que vous construisez un immuable TreeSet, en y ajoutant des éléments un par un. Le remplacer par quelque chose comme

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

Devrait raser environ 30-40% sur votre temps d'exécution.

La même approche (construire une liste, puis trier) aidera probablement votre utilisation de la mémoire dans la "version 3" (les ensembles java sont réal porcs de mémoire). C'est également une bonne idée de donner à votre liste une taille initiale pendant que vous y êtes (sinon, elle augmentera de 50% à chaque fois qu'elle sera à court de capacité, ce qui gaspille de la mémoire et des performances). bon nombre, car c'est la limite supérieure du nombre de villes de la description du problème.

Maintenant, puisque nous connaissons la limite supérieure, une approche encore plus rapide et plus mince consiste à supprimer les listes et les nombres entiers encadrés, int dists[] = new int[600];.

Si vous vouliez vraiment devenir chic, vous "d égalementutiliser la plage de "longueur de route" mentionnée dans la description. Par exemple, au lieu de jeter des ints dans un tableau et de trier (ou de conserver un arbre), créez un tableau de 20 000 bits (ou même 20 000 octets pour la vitesse) , et définissez ceux que vous voyez en entrée pendant que vous le lisez ... Ce serait à la fois plus rapide et plus efficace en mémoire que n'importe laquelle de vos solutions.


1 pour la réponse № 3

J'ai essayé de résoudre cette question et j'ai pensé que vous n'avez pas besoin des noms des villes, juste des distances dans un tableau trié.

Il a une bien meilleure exécution de 738 ms et une mémoire de 4513792 avec cela.

Bien que cela ne puisse pas aider à améliorer votre morceau de code, cela semble être une meilleure façon d'aborder la question. Toutes suggestions pour améliorer le code sont les bienvenues.

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