Какво кара кода ми да използва толкова много памет? - java, изпълнение, скала, памет

Реших по различни начини прост проблем на CodeEval, коя спецификация може да бъде намерена тук (дължина само няколко реда).

Направих 3 работещи версии (една от тях в Scala) и не разбирам разликата в изпълненията за последната си версия на Java, която очаквах да е най-подходящото време и памет.

Аз също сравних това с код, открит на Github, Ето статистическите данни за ефективността, върнати от CodeEval:

, Версия 1 е версията, открита в Github , Версия 2 е моето решение 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)
}

, Версия 3 е моето решение за Java, което очаквах да е най-доброто:

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

• Версия 4 е същата като версия 3, с изключение на това, че не използвам StringBuilder да отпечатате изхода и да направите както във версия 1

Ето как тълкувах тези резултати:

• версия 1 е твърде бавна поради твърде големия брой на System.out.print призовава. Освен това, използвайки split на много големи линии (такъв е случаят при извършените тестове) използва много памет.

• версия 2 също изглежда бавна, но това е главно поради "режийни разходи" при пускане на Scala код на CodeEval, дори много ефективен код работи бавно върху него

• версия 2 използва ненужна памет за съставяне на списъкот снимачната площадка, което също отнема известно време, но не трябва да бъде твърде значимо. Писането на по-ефективна Scala вероятно би искало да го напишете на Java, така че предпочитах елегантността пред изпълнението

• версия 3 не трябва да използва толкова много памет според мен. Използването на a StringBuilder оказва същото въздействие върху паметта като обаждането mkString във версия 2

• версия 4 доказва обажданията към System.out.println забавят програмата

Някой вижда ли обяснение на тези резултати?

Отговори:

3 за отговор № 1

Проведох някои тестове.

Има основна линия за всеки тип език. Кодирам в java и javascript. За JavaScript тук са моите резултати от теста:

• Rev 1: По подразбиране празен котел за JS с съобщение към стандартния изход
• Rev 2: Същото без четене на файл
• Rev 3: Просто съобщение до стандартния изход

Можете да видите, че без значение какво ще имапоне 200 ms време на изпълнение и около 5 мега използване на паметта. Тази базова линия зависи и от натоварването на сървърите! Имаше време, когато кодевалите бяха силно претоварени, като по този начин направи невъзможно да стартирате нищо в рамките на максималното време (10 секунди).

Вижте това, съвсем различно предизвикателство от предишното:

• Rev4: Моето решение
• Rev5: Същият код, изпратен отново отново. Набра 8000 повече точки за класиране. :Д

Заключение: Не бих се тревожил много за използването на процесора и паметта и ранга. Явно не е надежден.

---

2 за отговор № 2

Вашето решение за скала е бавно, не заради "режийни разходи за CodeEval", а защото изграждате неизменна TreeSet, добавяйки елементи един към друг. Заменяйки го с нещо подобно

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

Трябва да се обръсне около 30-40% от времето за изпълнение.

Същият подход (съставяне на списък и сортиране) вероятно ще помогне на използването на паметта във "версия 3" (java комплекти са реален паметници). Също така е добра идея да дадете на списъка си първоначален размер, докато сте в него (в противен случай той ще нарасне с 50% всеки път, когато изчерпи капацитета си, което е разточително както в паметта, така и в производителността). 600 звучи като добър номер, тъй като това е горната граница за броя на градовете от описанието на проблема.

Сега, тъй като знаем горната граница, още по-бързият и по-тънък подход е да премахнем списъците и кутиите Integeres и просто да направим int dists[] = new int[600];.

Ако искате да станете наистина фантазирани, вие също бихте искалиизползвайте диапазона "дължина на маршрута", който е споменат в описанието. Например, вместо да хвърляте ints в масив и да сортирате (или запазвате набор от дървета), направете масив от 20 000 бита (или дори 20K байта за скорост) , и задайте тези, които виждате във входа, докато го четете ... Това би било едновременно по-бързо и по-ефективно в паметта от всяко ваше решение.

---

1 за отговор № 3

Опитах се да реша този въпрос и реших, че нямате нужда от имената на градовете, а само разстоянията в подреден масив.

Той има много по-добро изпълнение от 738ms и памет от 4513792 с това.

Въпреки че това може да не помогне да подобрите своя код, изглежда като по-добър начин да подходите към въпроса. Всички предложения за допълнително подобряване на кода са добре дошли.

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

---