Днес на задачката Островландия възникнаха някои въпроси свързани с четенето от файл на Java. На мен принципно този език ми е доста чужд, но няма как да не забележа, че Scanner-ът е *адски* бавен. На вас всички това разбира се ви е пределно ясно, но тъй като той е по-лесен за ползване, често го предпочитате пред BufferedReader-а. Да видим обаче за колко време се изпълнява въпросната задача на spoj0:
- C++ (stdio) ~ 1.1 sec.
- C++ (iostream) ~ 2.2 sec.
- Java (BufferedReader) ~ 3.4 sec.
- Java (Scanner) ~ 21 sec.
Дори и да направим отделна задача за Java, на която да сложим различен time limit от този на C++, пак състезателите, написали входа с BufferedReader, ще са няколко *пъти* напред. Това примерно ще им позволи да напишат решение, което е да кажем log(N) пъти по-бавно и пак да accept-нат. Точно тук нещата стават кофти и поради тази причина ще помоля всички фенове на Scanner-а да се въздържат от него в задачи с голям вход. Разбира се, ако основната част от времето, в което работи вашата задача, се заема от самото решение, а не от четенето на входа (както е в повечето случай) - тогава няма проблем да си ползвате Scanner-а. Но да знаете, че вече официално, ако една задача ви дава time limit заради Scanner-а, нямате опрадвание. Това важи в пълна сила и за състезанието.
Приемаме всякакви аргументирани оплаквания.
Бтв, за Scanner-а: относно употребата му задачите. Тъй като в повечето случай входа е коректен и се знае колко точно числя ще се четата, няма нужда да се ползва метода hasNext(). Той прави същото нещо като readNext(). Един вид всичко се чете два пъти, щото май не кешират прочетеното. Въпреки това този спорен дизайн на Scanner-а е правилен за целите на сънската библиотеката, но нека не влизаме в идеологични спорове.
Много ми е любопитно дали този резултат е с hasNext() или без?
Много ми е любопитно дали този резултат е с hasNext() или без?
Резултата е без hasNext със Scanner конструиран върху BufferedReader, което е по интересното.
Zdraveite,
(parvo se izvinqvam za latinicata, no tuk vav fmi neshto ne mi se otdade da kacha phonetic, a na drugoto ne moga :) ).
Edin hubav urok pri pisaneto na rekursiq, e che steka e ogranichen (i tova ne e sluchaino :)). Pri linux ogranichenieto e 8 MB, a pri windows xp e 1 MB (za drugi versii nqmam nabludeniq, no edva li e mnogo poveche :)). Pri pisaneto na DFS sas izpolvaneto na rekursiq, trqbva da se vnimava mnogo :). Ako v edin i sasht moment sme zadalbali mnogo v rekursiqta, tova oznachava che se pazqt mnogo v steka. Za vsqko izvikvane na funkciq se pazi pamet za parametrite, za sastoqnieto na lokalnite promenlivi, adress za vrashtane i pole za rezultat.
T.e. ako daden po-hubav test, kadeto maksimalniq ostrov e golqm (naprime ako napalnim tablica 1000 x 1000 s edinici, toi shte e 1 000 000). Avtorovoto reshenie shte poluchi stack overflow na gorespomenatatite operacionni sistemi :). Edin nachin da se opravi e da se izpolzva ne rekursiq, a stek, koito polzva pamet ot heap. Vtori e da se uvelichi maksimalniq razmer na steka, za koeto mai sa neobhodimi solidni prava i ako ne se nastroi ot grading sistemata nqma kak da stane. Tretiq nachin e da se napishe BFS.
Zatova vnimavaite s pisaneto na golemi rekursii :).
Pozdravi,
Presley
(parvo se izvinqvam za latinicata, no tuk vav fmi neshto ne mi se otdade da kacha phonetic, a na drugoto ne moga :) ).
Edin hubav urok pri pisaneto na rekursiq, e che steka e ogranichen (i tova ne e sluchaino :)). Pri linux ogranichenieto e 8 MB, a pri windows xp e 1 MB (za drugi versii nqmam nabludeniq, no edva li e mnogo poveche :)). Pri pisaneto na DFS sas izpolvaneto na rekursiq, trqbva da se vnimava mnogo :). Ako v edin i sasht moment sme zadalbali mnogo v rekursiqta, tova oznachava che se pazqt mnogo v steka. Za vsqko izvikvane na funkciq se pazi pamet za parametrite, za sastoqnieto na lokalnite promenlivi, adress za vrashtane i pole za rezultat.
T.e. ako daden po-hubav test, kadeto maksimalniq ostrov e golqm (naprime ako napalnim tablica 1000 x 1000 s edinici, toi shte e 1 000 000). Avtorovoto reshenie shte poluchi stack overflow na gorespomenatatite operacionni sistemi :). Edin nachin da se opravi e da se izpolzva ne rekursiq, a stek, koito polzva pamet ot heap. Vtori e da se uvelichi maksimalniq razmer na steka, za koeto mai sa neobhodimi solidni prava i ako ne se nastroi ot grading sistemata nqma kak da stane. Tretiq nachin e da se napishe BFS.
Zatova vnimavaite s pisaneto na golemi rekursii :).
Pozdravi,
Presley
Така, задачата съм я давал аз и напълно приемам забележката. Наситина като я пишех "ей така" си измислих ограниченията, а това, както стана ясно, не е много хубаво (-: В случая решението минава, защото най-големият остров е малко над 500 върха (тестовете са генерирани random).
Още едно ограничение не е в ред - това на задачата за търговския пътник. За тези, които все още я пишат - нека знаят, че графът в (псевдо)тежките тестове далеч не е пълен (мисля, че е с n*(n-1)/8 ребра) и като цяло няма нужда от динамично оптимиране. Ограничението трябваше да е даже и под 15, а не 20 върха.
Ще гледам да не се повтаря...
Още едно ограничение не е в ред - това на задачата за търговския пътник. За тези, които все още я пишат - нека знаят, че графът в (псевдо)тежките тестове далеч не е пълен (мисля, че е с n*(n-1)/8 ребра) и като цяло няма нужда от динамично оптимиране. Ограничението трябваше да е даже и под 15, а не 20 върха.
Ще гледам да не се повтаря...
@ Presley, steka po princip w C++ moje da si go naprawi6 kolkoto si iska6 kato zadade6 na linker-a razmera. Stawa po sledniq na4in pone pod Win XP ( za Linux ne sym probwal, za6toto ne nqmam) e taka : #pragma comment(linker, "/STACK:16777216"), taka 6te e 16 MB.
Ina4e i az se izvinqwam za latinicata, ama i az nqmam kirilica.
Ina4e i az se izvinqwam za latinicata, ama i az nqmam kirilica.
A бе той се задава ама на spoj0 не компилираш ти. Както и да е ... разбрахме се, че тук съм крив.
Сега една молба към джаварите - ще може ли на moodle да качвате решението така, че като го paste-я в spoj0 и да върви. Това значи да няма package и public класът да се казва program. Това много ще ме улесни, защото когато имам 20 решения за проверка хич не ми се занимава да разархивирам архиви или да преименувам имена на класове и понякога конструктори. Благодаря!
Сега една молба към джаварите - ще може ли на moodle да качвате решението така, че като го paste-я в spoj0 и да върви. Това значи да няма package и public класът да се казва program. Това много ще ме улесни, защото когато имам 20 решения за проверка хич не ми се занимава да разархивирам архиви или да преименувам имена на класове и понякога конструктори. Благодаря!
Относно последната задача за домашно - Президент - едно и също решение го пуснах в spoj0, като входа първия път се четеше с BufferedReader ( BufferedReader r = new BufferedReader(new InputStreamReader(System.in, "US-ASCII")); line = r.readLine(); parts = line.split(" "); N = Integer.parseInt(parts[0]); ), а втория път със Scanner. С BufferedReader ми дава re, а със Scanner - ok. Възножно е в тестовете да има повече интервали от обявените в условието - "разделени с по един интервал" или както се беше оказало на състезанието някой редове да завършват с табулация.
Като претърсих входния файл за съседни два интервала или табулация не намерих.
Да, права си. Още като ти видях коментара в spoj0 прерових файла. Оправих го, затова Тонито не е намерил неточности. Би трябвало вече всичко да е наред. Извиняваме се за неудобството.