/ / O que está fazendo meu código usar tanta memória? - java, desempenho, scala, memória

O que está fazendo meu código usar tanta memória? - java, desempenho, scala, memória

Resolvi de várias maneiras um problema simples no CodeEval, cuja especificação pode ser encontrada Aqui (apenas algumas linhas).

Eu fiz três versões de trabalho (uma delas no Scala) e não entendo a diferença de desempenho da minha última versão do Java, que eu esperava ser a melhor hora e a melhor memória.

Eu também comparei isso com um código encontrado em Github. Aqui estão as estatísticas de desempenho retornadas pelo CodeEval:

Estatísticas

. Versão 1 é a versão encontrada no Github . A versão 2 é minha solução 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)
}

. A versão 3 é minha solução Java que eu esperava ser a melhor:

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();
}
}
  • A versão 4 é igual à versão 3, exceto que eu não uso um StringBuilder para imprimir a saída e fazer como na versão 1

Aqui está como eu interpretei esses resultados:

  • A versão 1 é muito lenta devido ao número muito alto de System.out.print chamadas. Além disso, usando split em linhas muito grandes (esse é o caso nos testes realizados) usa muita memória.

  • a versão 2 parece lenta também, mas é principalmente por causa de uma "sobrecarga" na execução do código Scala no CodeEval, mesmo o código muito eficiente executado lentamente nele

  • versão 2 usa memória desnecessária para criar uma listado conjunto, o que também leva algum tempo, mas não deve ser muito significativo. Escrever Scala mais eficiente provavelmente gostaria de escrevê-lo em Java, por isso preferi elegância ao desempenho

  • versão 3 não deve usar tanta memória na minha opinião. O uso de um StringBuilder tem o mesmo impacto na memória que a chamada mkString na versão 2

  • versão 4 comprova as chamadas para System.out.println estão desacelerando o programa

Alguém vê uma explicação para esses resultados?

Respostas:

3 para resposta № 1

Eu conduzi alguns testes.

Existe uma linha de base para todos os tipos de idioma. Eu codifico em java e javascript. Para javascript, aqui estão os resultados dos meus testes:

desafio aleatório

  • Rev 1: boilerplate vazio padrão para JS com uma mensagem para a saída padrão
  • Rev 2: Mesmo sem leitura de arquivo
  • Rev 3: Apenas uma mensagem para a saída padrão

Você pode ver que, não importa o que aconteça, haverámenos tempo de execução de 200 ms e cerca de 5 megas de uso de memória. Essa linha de base também depende da carga dos servidores! Houve um tempo em que codeevals estava sobrecarregado, impossibilitando a execução de qualquer coisa dentro do tempo máximo (10s).

Veja isso, um desafio totalmente diferente do anterior: Foto aleatória 2.

  • Rev4: Minha solução
  • Rev5: O mesmo código enviado novamente agora. Marcou 8000 pontos a mais no ranking. : D

Conclusão: Eu não me preocuparia muito com o uso e a classificação da CPU e da memória. Claramente não é confiável.


2 para resposta № 2

Sua solução scala é lenta, não por causa da "sobrecarga no CodeEval", mas porque você está construindo um imutável TreeSet, adicionando elementos um a um. Substituindo-o por algo como

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

Deve economizar cerca de 30 a 40% do seu tempo de execução.

A mesma abordagem (criar uma lista e classificar) provavelmente ajudará a utilização da memória na "versão 3" (os conjuntos java são real porcos de memória). Também é uma boa idéia dar à sua lista um tamanho inicial enquanto você estiver nela (caso contrário, ela aumentará 50% toda vez que ficar sem capacidade, o que é um desperdício de memória e desempenho). bom número, já que esse é o limite superior para o número de cidades da descrição do problema.

Agora, como conhecemos o limite superior, uma abordagem ainda mais rápida e mais fina é acabar com listas e números inteiros em caixa e simplesmente int dists[] = new int[600];.

Se você quisesse ser realmente chique, você tambémuse o intervalo de "tamanho da rota" mencionado na descrição. Por exemplo, em vez de inserir entradas em uma matriz e classificar (ou manter um conjunto de árvores), crie uma matriz de 20.000 bits (ou até 20K bytes para velocidade) e defina aqueles que você vê na entrada ao ler ... Isso seria mais rápido e mais eficiente em termos de memória do que qualquer uma das suas soluções.


1 para resposta № 3

Tentei resolver esta questão e concluí que você não precisa dos nomes das cidades, apenas das distâncias em uma matriz classificada.

Tem um tempo de execução muito melhor de 738ms e uma memória de 4513792 com isso.

Embora isso possa não ajudar a melhorar seu código, parece ser uma maneira melhor de abordar a questão. Quaisquer sugestões para melhorar ainda mais o código são bem-vindas.

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