SPOJ spore zużycie pamięci

SPOJ spore zużycie pamięci
GR
  • Rejestracja:prawie 13 lat
  • Ostatnio:dzień
  • Postów:94
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:
Kopiuj
 
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.

edytowany 3x, ostatnio: grzzpo
ŁF
Moderator
  • Rejestracja:ponad 22 lata
  • Ostatnio:dzień
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ąć.


edytowany 1x, ostatnio: ŁF
GR
  • Rejestracja:prawie 13 lat
  • Ostatnio:dzień
  • Postów:94
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>).

edytowany 1x, ostatnio: grzzpo
Shalom
  • Rejestracja:około 21 lat
  • Ostatnio:prawie 3 lata
  • Lokalizacja:Space: the final frontier
  • Postów:26433
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()


"Nie brookliński most, ale przemienić w jasny, nowy dzień najsmutniejszą noc - to jest dopiero coś!"
edytowany 1x, ostatnio: Shalom
GR
  • Rejestracja:prawie 13 lat
  • Ostatnio:dzień
  • Postów:94
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:
Kopiuj
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:
Kopiuj
System.out.println("To, co chcę wypisać");

Zużycie pamięci takie samo...

edytowany 3x, ostatnio: grzzpo
Shalom
  • Rejestracja:około 21 lat
  • Ostatnio:prawie 3 lata
  • Lokalizacja:Space: the final frontier
  • Postów:26433
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.


"Nie brookliński most, ale przemienić w jasny, nowy dzień najsmutniejszą noc - to jest dopiero coś!"
GR
  • Rejestracja:prawie 13 lat
  • Ostatnio:dzień
  • Postów:94
0
Kopiuj
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);
	}

}
ŁF
Moderator
  • Rejestracja:ponad 22 lata
  • Ostatnio:dzień
0

A wyrzuć jeszcze tego BufferedReadera.


GR
A jak go zastąpię? Wtedy chyba muszę wczytywać znak po znaku albo skorzystać ze Scannera, a to drugie zajmuje sporo czasu.
Shalom
BufferedReader ma ograniczony bufor, raczej nie łyknie tyle pamięci ;)
GR
  • Rejestracja:prawie 13 lat
  • Ostatnio:dzień
  • Postów:94
0

Co do BufferedReadera...

Zmieniłem

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

na:

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

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

edytowany 1x, ostatnio: grzzpo
datdata
  • Rejestracja:prawie 11 lat
  • Ostatnio:około 7 lat
  • Postów:957
1

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


"A human being should be able to change a diaper, plan an invasion, butcher a hog, conn a ship, design a building, write a sonnet, balance accounts, build a wall, set a bone, comfort the dying, take orders, give orders, cooperate, act alone, solve equations, analyze a new problem, pitch manure, program a computer, cook a tasty meal, fight efficiently, die gallantly. Specialization is for insects." Robert Heinlein.
ŁF
Profiler może będzie bardziej odpowiedni.
datdata
No czymkolwiek. Debugger na pewno ma w IDE i wie jak działa, a w przypadku jednoplikowego programiku z debuggera można już się dowiedzieć gdzie cholerstwo idzie. Ale fakt, profiler lepszy.
GR
Próbuję... mam tylko adres zmiennej (Buffera).
Shalom
  • Rejestracja:około 21 lat
  • Ostatnio:prawie 3 lata
  • Lokalizacja:Space: the final frontier
  • Postów:26433
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

"Nie brookliński most, ale przemienić w jasny, nowy dzień najsmutniejszą noc - to jest dopiero coś!"
GR
Problem: http://bit.ly/1ySH8CW Tylko + i - albo liczba int.
GR
  • Rejestracja:prawie 13 lat
  • Ostatnio:dzień
  • Postów:94
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ć...

GThoro
  • Rejestracja:ponad 10 lat
  • Ostatnio:ponad 6 lat
  • Postów:98
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.

Shalom
Generalnie nie, chyba że ustawisz takie -Xms ;]
GR
  • Rejestracja:prawie 13 lat
  • Ostatnio:dzień
  • Postów:94
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.

Shalom
  • Rejestracja:około 21 lat
  • Ostatnio:prawie 3 lata
  • Lokalizacja:Space: the final frontier
  • Postów:26433
0

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


"Nie brookliński most, ale przemienić w jasny, nowy dzień najsmutniejszą noc - to jest dopiero coś!"
TO
  • Rejestracja:około 17 lat
  • Ostatnio:ponad 8 lat
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.

Shalom
  • Rejestracja:około 21 lat
  • Ostatnio:prawie 3 lata
  • Lokalizacja:Space: the final frontier
  • Postów:26433
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ń.


"Nie brookliński most, ale przemienić w jasny, nowy dzień najsmutniejszą noc - to jest dopiero coś!"
GR
  • Rejestracja:prawie 13 lat
  • Ostatnio:dzień
  • Postów:94
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.

edytowany 3x, ostatnio: grzzpo
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ęć.

TO
  • Rejestracja:około 17 lat
  • Ostatnio:ponad 8 lat
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

Kliknij, aby dodać treść...

Pomoc 1.18.8

Typografia

Edytor obsługuje składnie Markdown, w której pojedynczy akcent *kursywa* oraz _kursywa_ to pochylenie. Z kolei podwójny akcent **pogrubienie** oraz __pogrubienie__ to pogrubienie. Dodanie znaczników ~~strike~~ to przekreślenie.

Możesz dodać formatowanie komendami , , oraz .

Ponieważ dekoracja podkreślenia jest przeznaczona na linki, markdown nie zawiera specjalnej składni dla podkreślenia. Dlatego by dodać podkreślenie, użyj <u>underline</u>.

Komendy formatujące reagują na skróty klawiszowe: Ctrl+B, Ctrl+I, Ctrl+U oraz Ctrl+S.

Linki

By dodać link w edytorze użyj komendy lub użyj składni [title](link). URL umieszczony w linku lub nawet URL umieszczony bezpośrednio w tekście będzie aktywny i klikalny.

Jeżeli chcesz, możesz samodzielnie dodać link: <a href="link">title</a>.

Wewnętrzne odnośniki

Możesz umieścić odnośnik do wewnętrznej podstrony, używając następującej składni: [[Delphi/Kompendium]] lub [[Delphi/Kompendium|kliknij, aby przejść do kompendium]]. Odnośniki mogą prowadzić do Forum 4programmers.net lub np. do Kompendium.

Wspomnienia użytkowników

By wspomnieć użytkownika forum, wpisz w formularzu znak @. Zobaczysz okienko samouzupełniające nazwy użytkowników. Samouzupełnienie dobierze odpowiedni format wspomnienia, zależnie od tego czy w nazwie użytkownika znajduje się spacja.

Znaczniki HTML

Dozwolone jest używanie niektórych znaczników HTML: <a>, <b>, <i>, <kbd>, <del>, <strong>, <dfn>, <pre>, <blockquote>, <hr/>, <sub>, <sup> oraz <img/>.

Skróty klawiszowe

Dodaj kombinację klawiszy komendą notacji klawiszy lub skrótem klawiszowym Alt+K.

Reprezentuj kombinacje klawiszowe używając taga <kbd>. Oddziel od siebie klawisze znakiem plus, np <kbd>Alt+Tab</kbd>.

Indeks górny oraz dolny

Przykład: wpisując H<sub>2</sub>O i m<sup>2</sup> otrzymasz: H2O i m2.

Składnia Tex

By precyzyjnie wyrazić działanie matematyczne, użyj składni Tex.

<tex>arcctg(x) = argtan(\frac{1}{x}) = arcsin(\frac{1}{\sqrt{1+x^2}})</tex>

Kod źródłowy

Krótkie fragmenty kodu

Wszelkie jednolinijkowe instrukcje języka programowania powinny być zawarte pomiędzy obróconymi apostrofami: `kod instrukcji` lub ``console.log(`string`);``.

Kod wielolinijkowy

Dodaj fragment kodu komendą . Fragmenty kodu zajmujące całą lub więcej linijek powinny być umieszczone w wielolinijkowym fragmencie kodu. Znaczniki ``` lub ~~~ umożliwiają kolorowanie różnych języków programowania. Możemy nadać nazwę języka programowania używając auto-uzupełnienia, kod został pokolorowany używając konkretnych ustawień kolorowania składni:

```javascript
document.write('Hello World');
```

Możesz zaznaczyć również już wklejony kod w edytorze, i użyć komendy  by zamienić go w kod. Użyj kombinacji Ctrl+`, by dodać fragment kodu bez oznaczników języka.

Tabelki

Dodaj przykładową tabelkę używając komendy . Przykładowa tabelka składa się z dwóch kolumn, nagłówka i jednego wiersza.

Wygeneruj tabelkę na podstawie szablonu. Oddziel komórki separatorem ; lub |, a następnie zaznacz szablonu.

nazwisko;dziedzina;odkrycie
Pitagoras;mathematics;Pythagorean Theorem
Albert Einstein;physics;General Relativity
Marie Curie, Pierre Curie;chemistry;Radium, Polonium

Użyj komendy by zamienić zaznaczony szablon na tabelkę Markdown.

Lista uporządkowana i nieuporządkowana

Możliwe jest tworzenie listy numerowanych oraz wypunktowanych. Wystarczy, że pierwszym znakiem linii będzie * lub - dla listy nieuporządkowanej oraz 1. dla listy uporządkowanej.

Użyj komendy by dodać listę uporządkowaną.

1. Lista numerowana
2. Lista numerowana

Użyj komendy by dodać listę nieuporządkowaną.

* Lista wypunktowana
* Lista wypunktowana
** Lista wypunktowana (drugi poziom)

Składnia Markdown

Edytor obsługuje składnię Markdown, która składa się ze znaków specjalnych. Dostępne komendy, jak formatowanie , dodanie tabelki lub fragmentu kodu są w pewnym sensie świadome otaczającej jej składni, i postarają się unikać uszkodzenia jej.

Dla przykładu, używając tylko dostępnych komend, nie możemy dodać formatowania pogrubienia do kodu wielolinijkowego, albo dodać listy do tabelki - mogłoby to doprowadzić do uszkodzenia składni.

W pewnych odosobnionych przypadkach brak nowej linii przed elementami markdown również mógłby uszkodzić składnie, dlatego edytor dodaje brakujące nowe linie. Dla przykładu, dodanie formatowania pochylenia zaraz po tabelce, mogłoby zostać błędne zinterpretowane, więc edytor doda oddzielającą nową linię pomiędzy tabelką, a pochyleniem.

Skróty klawiszowe

Skróty formatujące, kiedy w edytorze znajduje się pojedynczy kursor, wstawiają sformatowany tekst przykładowy. Jeśli w edytorze znajduje się zaznaczenie (słowo, linijka, paragraf), wtedy zaznaczenie zostaje sformatowane.

  • Ctrl+B - dodaj pogrubienie lub pogrub zaznaczenie
  • Ctrl+I - dodaj pochylenie lub pochyl zaznaczenie
  • Ctrl+U - dodaj podkreślenie lub podkreśl zaznaczenie
  • Ctrl+S - dodaj przekreślenie lub przekreśl zaznaczenie

Notacja Klawiszy

  • Alt+K - dodaj notację klawiszy

Fragment kodu bez oznacznika

  • Alt+C - dodaj pusty fragment kodu

Skróty operujące na kodzie i linijkach:

  • Alt+L - zaznaczenie całej linii
  • Alt+, Alt+ - przeniesienie linijki w której znajduje się kursor w górę/dół.
  • Tab/⌘+] - dodaj wcięcie (wcięcie w prawo)
  • Shit+Tab/⌘+[ - usunięcie wcięcia (wycięcie w lewo)

Dodawanie postów:

  • Ctrl+Enter - dodaj post
  • ⌘+Enter - dodaj post (MacOS)