Loading...
Hawckc avatar Hawckc 1 Точки

Data-Structure Fundamentals Retake Exam 08.2021 Task Olympics

Здравейте,

Някой има ли решение на тази задача, което да има пълен брой точки на performance тестовете, защото няма и примерно решение, което да погледна. Дори като съм пускал решението в Judge, съм изкарвал различен брой точки с едно и също решение.

0
Open Courses
MartinBG avatar MartinBG 4803 Точки

В Judge има две "състезания" с тази задача: Java и C#

Глеадйки резултатите от изпита и упражненията по Java, няма нито едино решение, което да вземе 100/100 (до 91).

За C# има по един резултат 100/100 на изпита и на упражненията.

Следва да се отбележи, че дори и решението на Lazii, за което предполагам, че референтното, не е взело 100 точки на Java.

Предполагам, че за този изпит се е случило това, което се случва открай време с този курс - задачите се пишат на C# и в последния момент се адаптират за Java, при което се случва едно от следните неща:

1. Решение, при което се използва неоптимална за проблема структура взема 100 точки, защото не са сложили достатъчно стриктни ограничения

2. Колкото и да се оптимизира дадено решение, не успява да вземе 100 точки, защото ограниченията са сложени "наизуст", без да има референтно решение

3. Има проблеми със скелета, тестовете и качеството на кода, защото е "преписан" от C# решението

 

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

1
11/05/2022 18:26:02
Hawckc avatar Hawckc 1 Точки

Ето линк към архив https://drive.google.com/drive/folders/1kQekc0aNEVRjJL2U808jXOwouIffwnVU?usp=sharing

Благодаря предварително

0
11/05/2022 22:34:58
MartinBG avatar MartinBG 4803 Точки

Прегледах скелета за Java и открих няколко грешки в тестовете.

OlympicsImplCorrectnessTest.java - в два от тестовете липсва assert, т.е. тестът винаги минава локално, но в Judge единият от тях фейлва (явно е оправен в движение)

  • contains_should_return_true_with_valid_data()
  • contains_should_return_false_with_invalid_data()

OlympicsImplCorrectnessTest.java - тук проблемите са повече 

  • тестовете, които проверяват за използвана памет имат проверка и за минимална памет ( > 100), но начинът по който я отчитат не е надежден, защото свободната памет се промня динамично заради Garabage Collectora-a и е напълно възможно свободната памет след като сме създали 1000000 обекта де е дори повече, отколкото е била преди това. Възможните варианти за заобикаляне на този проблем (произволно фейлване на такъв тест) са или да се махне проверката за долна граница (най-добре), или да се форсне garabage collection-a преди всеки тест (в setUp() се добавя Runtime.getRuntime().gc())
  • много тестове имат сетнат timeout, например @Test(timeout = 500), въпреки че теста трябва да провери скоростта на конкретна операция (вътре в метода се засича времето ѝ с System.currentTimeMillis()). Проблемът е, че в някои методи се създават 1_000_000 тестови обекта още преди да бъдат използвани от тестваната система, а времето за създаването им отнема от цялото време за метода (примерно 500 мс) и това води до random fail на някои от тези тестове. За избягване на този проблем не трябва да има таймаут на метода или тестовите данни трябва да бъдат създадени преди това
  • решение само с 2 HashMap-а и използването на Stream API за отделните методи взема 91/100 точки, а ако се оправят горните проблеми в тестовете най-вероятно ще вземе и 100/100, т.е. тестовете не налагат използването на комбинация от различни контейнери за да се постигне оптимално бързодействие

 

Edit:

 

В това видео се опитват да решат проблема с тази задача и се вижда, че тест №14 e addCompetitor_1_000_000_competitors_memory_usage(), но кодът му се различава от този в скелета: липсва timeout, създават се 500_000 competitors проверката за памет е от 50 до 120MB. Решението най-вероятно ще мине, ако се премахне долната граница за паметта в assert-а.

0
12/05/2022 18:17:40
Hawckc avatar Hawckc 1 Точки

Много благодаря за изчерпателният отговор. Аз също забелязах проблеми като това, че даден тест, който тества дадена функционалност, която зависи от друга такава, трябва да мине за по-малко време от колкото теста за функционалността, която използва. Не съм сигурен дали викането на Garbage Collector би работило, защото до колкото знам извикването му само препоръчва на виртуалната машина да изчискти heap. Друг проблем е, че до колкото знам в курса не се преподават хеш таблици, а изглежда, че дори решението с тях не минава тестовете за performance. Поне ако някой има подобрен проблем, с тази задача, вече може да намери обяснение във форума.

1
13/05/2022 14:46:37
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.