SPOJ spore zużycie pamięci

0

Witam!
Do implementacji pewnego prostego zadania ze SPOJa użyłem tylko:

  1. 3 zmiennych typu Integer
  2. tablicy o 10 elementach typu Integer.
    Wczytywanie danych odbywa się tak:
 
public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		while (in.ready()) {
			String inputString = in.readLine();
			if (inputString.charAt(0) == '+') {
				//tu wykonuję alg.
			}
			else if (inputString.charAt(0) == '-') {
				//tu też...
			}
		}
		out.flush();
		out.close();
		System.exit(0);
	}

Nie chcę wrzucać całego zadania, bo to gotowe i poprawne rozw.

Załączam obrazek z najszybszymi rozwiązaniami tego zadania.

Skąd może się brać tak duże zużycie pamięci... aż 1398MB?
Pozdrawiam.

0

Ja tu widzę też definicje:

  • BufferedReader in
  • PrintWriter out
  • w pętli String inputString.
    Poczytaj jak działa BufferedReader, bo choć nie znam dobrze javy, to dam głowę, że to tutaj leży problem.

Ponadto jeśli wykonujesz rekurencyjnie metodę zawierającą w zmiennych lokalnych te zmienne i tablice, to stos mógł tak napuchnąć.

0
ŁF napisał(a):

Ja tu widzę też definicje:

  • BufferedReader in
  • PrintWriter out
  • w pętli String inputString.

Tak, tak. Zapomniałem dopisać.

ŁF napisał(a):

Ponadto jeśli wykonujesz rekurencyjnie metodę zawierającą w zmiennych lokalnych te zmienne i tablice, to stos mógł tak napuchnąć.

Mógłbyś rozwinąć? Mój stos ma maksymalnie 10 elementów (więcej nie, bo to własna implementacja a nie Stack<Integer>).

0

Problem leży w twoim Printerze. Nie pokazałeś tego fragmentu ale głowę daje że zapisujesz tam całe wyjście a potem wypisujesz je na raz ;] Ewentualnie zadanie nie definiuje jak długa może być jedna linia i zabija cię readLine()

0

Nie, problem nie leży w Printerze.
Fakt, w pierwszym rozwiązaniu dopiero na końcu wszystko wypisywałem.

Przetestowałem 2 inne rozwiązania:

  • z PrintWriterem:
out.println("To, co chcę wypisać");
out.flush();

Czyli flush zawsze bezprośrednio pod println.
Zużycie pamięci takie samo.

  • bez PrintWritera (wykomentarzowana deklaracja itd.)... zamiast tego:
System.out.println("To, co chcę wypisać");

Zużycie pamięci takie samo...

0

No to podaj łaskawie treść zadania albo kod twojego algorytmu. Albo oba. W tym co podałeś tylko readLine() może łykać nieograniczoną ilość pamięci.

0
import java.io.*;


public class Main {
	
	static int current = -1; 
	static int[] stack = new int[10];
	
	static boolean push (int t) {
		if (current < 9) {
			stack[++current] = t;
			return true;
		}
		return false;
	}
	
	static int pop () {
		if (current > -1)
			return stack[current--];
		return -1;
	}
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		//PrintWriter out = new PrintWriter(System.out);
		while (in.ready()) {
			String inputString = in.readLine();
			if (inputString.charAt(0) == '+') {
				int toPush = Integer.parseInt(in.readLine());
				if (push(toPush)) {
					//out.println(":)");
					//out.flush();
					System.out.println(":)");
				} else {
					//out.println(":(");
					//out.flush();
					System.out.println(":(");
				}
			}
			else if (inputString.charAt(0) == '-') {
				int numberPopped;
				if ((numberPopped = pop()) != -1) {
					//out.println(numberPopped);
					//out.flush();
					System.out.println(numberPopped);
				}
				else {
					//out.println(":(");
					//out.flush();
					System.out.println(":(");
				}	
			}
		}
		//out.close();
		System.exit(0);
	}

}
0

A wyrzuć jeszcze tego BufferedReadera.

0

Co do BufferedReadera...

Zmieniłem

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

na:

BufferedReader in = new BufferedReader(new InputStreamReader(System.in), 1);

Rozwiązanie dalej poprawne, a pamięć bez zmian...

1

Zapnij się debuggerem i zobacz co Ci tyle zjada, bo bez tego błądzimy jak grajkowie na obcej ziemi.

0
  1. System.exit(0); srsly? o_O
  2. Jaka jest treść zadania? Co może być w tych liniach na wejściu? Tylko +, -, albo liczba int? Bo w tym kodzie tak na oko nie ma gdzie znikać pamięć oprócz readLine
0
datdata napisał(a):

Zapnij się debuggerem i zobacz co Ci tyle zjada, bo bez tego błądzimy jak grajkowie na obcej ziemi.

Powiedz proszę, mnej więcej jak to zrobić...

1

Java tak nie ma, że nieważne co to proces javaw sobie zeżre tyle ile ma domyślnie na heap ustawiony? Jak gadam farmazony to mnie zignorujcie, wnioskuję to tylko po tym, że cokolwiek od javy bym nie odpalił to mi zjada tak z 1,2GB, poza jednym wyjątkiem, gdzie heap przestawiam na 3-4GB.

0

Wygląda na to, że to zużycie pamięci jest tak ustawione przez serwer. Prawie wszędzie mam to 1398 MB, a czasem niewiele więcej.

0

Jest to możliwe, jeśli nie chcieli ryzykować że alokacje / GC będą zaburzać czasy działania algorytmu.

0

Tyle że inne rozwiązania tego problemu w javie używają ok 177M.
Ale skoro próbujemy to porównywać to warto by wiedzieć co ta liczba dokładnie oznacza.

0

Ale rozwiązania innych ludzi, czy rozwiązania innych zestawów testowych? Bo jeśli chodzi o inne zestawy to bardzo możliwe że ten jeden zestaw jest duży i autorzy zadania uznali że ktoś może próbować łyknąć całe wejście a dopiero potem prowadzić obliczenia. Stąd też ustalili minimalny heap bardzo wysoko, żeby oceniać tylko efektywność obliczeń.

0

Rozwiązania innych ludzi. Nie da się wykonać do większości zadań pojedyńczych testów... jedynie wszystkie na raz. Mam wrażenie, że ta wartość jest ustalana z góry przez system i co jakiś czas zmieniana...
Zużycie pamięci dla rozwiązań innych prostych zadań często wygląda tak: przykład dla chyba najprostszego zadania .
Powtarza się tam kilka wartości: 1398, 217, 177 MB. Ewentualnie do tego +1 lub 2 MB.

1
grzzpo napisał(a):

Rozwiązania innych ludzi. Nie da się wykonać do większości zadań pojedyńczych testów... jedynie wszystkie na raz. Mam wrażenie, że ta wartość jest ustalana z góry przez system i co jakiś czas zmieniana...
Zużycie pamięci dla rozwiązań innych prostych zadań często wygląda tak: przykład dla chyba najprostszego zadania .
Powtarza się tam kilka wartości: 1398, 217, 177 MB. Ewentualnie do tego +1 lub 2 MB.

tak ta wartosc pojawia sie dla ustalonych bibliotek i rodzaju kodu, nic tam sie nie dzieje przypadkiem. Bez strachu o pamięć.

0

Ta pamięć jest dziwnie liczna
Rozwiązanie problemu test tym sposobem http://dansesacrale.wordpress.com/2010/09/12/how-to-spoj-test-using-jar-file/ zajmuje wg spoj 1398MB

1 użytkowników online, w tym zalogowanych: 0, gości: 1