Професионална програма
Loading...
+ Нов въпрос
kostadink2001 avatar kostadink2001 7 Точки

C++ Advanced - 10_01.MaxSumArray. Time limit на 10-ти тест в Judge

Здравейте,

Judge ми дава Time limit на последния тест на задачата, опитах се освен с copy-swap идеомата да имплементирам и другия начин за копи асайнмент оператор, който Жоро е показвал, но пак не ми минава последния тест. Въпросът ми е, къде кодът не е достатъчно оптимизан?

Линк към Array.h

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

Тагове:
1
C++ Programming 12/11/2018 14:52:26
georgi.stef.georgiev avatar georgi.stef.georgiev 921 Точки
Best Answer

Здравей,

Виждам друг, по-сериозен проблем в задачата ти, performance-ът може би е свързан с него индиректно. Иначе може би да вдигна time limit-а на тази задача, тя не е толкова оптимизационна и judge е различно натоварен и понякога се влачи безсмислено по някои задачи.

Относно проблема: в copy assignment operator-а, приемаш грешно параметъра. Замисли се какво се случва - получаваш референция и swap-ваш нейните данни с тези на текущия обект. Тоест операцията a = b не само ще направи a да вземе стойността на b, ами ще направи b да вземе стойността на a - това е грешно, не искаме да се случва.

Предвид, че ползваме copy & swap идиомата, искаме да получим параметъра като копие, тоест без референция. Така вземаме временно копие, което ще се унищожи на края на функцията, в което пращаме старите данни на текущия обект, и от което вземаме копие на нещото стоящо отдясно на знака равно.

Най-вероятно объркването идва от това, че съм ви казвал, че е добро правило винаги да приемате обекти като константна референция, и ти си опитал така да го подадеш, обаче ти е дало грешка заради swap-а, и ти си махнал константността. Тоест компилаторът ти е показал, че не отиваш в правилна посока, обаче ти си заобиколил грешката, вместо да решиш проблема. Ако държиш да приемеш константна референция, това е ок, просто вътре във функцията направи един Array обект, който инициализираш (copy construct-ваш) със стойността на референцията. Първият вариант е по-добър (директно да получиш копие като параметър), но и този не е грешен.

Сега относно performance-а - най-вероятно това решение, приемащо референция, изпуска възможността за едни оптимизации, които компилаторът прави (в определени ситуации), които работят само когато подаваш копия, а не референции. Това би обяснило защо други колеги нямат time limit на последния тест, а ти имаш. Все пак компилаторът трябва да се съобрази с това, че ти модифицираш нещото стоящо отдясно на знака равно и не може да ги направи тези оптимизации. А ти не искаш да го правиш това най-вероятно, но скелетът и тестовете на тази задача са такива, че това не е проблем, защото дясната стойност реално не се ползва след като е присвоена (щеше да е проблем ако в задачата пазихме ппримерно всички масиви, които някога сме считали за максимални, но после сме ги заместили с други).

Пробвай да махнеш референцията и кажи дали се е оправило.

Поздрави,

Жоро

1
kostadink2001 avatar kostadink2001 7 Точки

Здрасти Жоро,

Това с референцията го бях изпуснал и бях забравил да изтрия амперсанта.Вече copy assignment operator-а не приема обекта по референция, а като копие, качих кода в Judge и ми даде 80/100, като и на 7-ми и на 10-ти тест ми даде Time limit, а не само на 10-ти както беше с референцията.

0
georgi.stef.georgiev avatar georgi.stef.georgiev 921 Точки

Ок, значи общо взето Judge се влачи, ще бутна time limit-а и ще пусна решенията за ретест

0
kostadink2001 avatar kostadink2001 7 Точки

Добре, мерси много!

0
MartinBG avatar MartinBG 4432 Точки

И аз много се измъчих с тази задача, докато я прекарам в Judge, като пробвах всякакви оптимизации и микро-оптимизации, за които се сетих. Нищо не помогна и в крайна сметка се заинатих и събмитвах едно и също решение докато мине, но ме е срам да кажа колко опита ми отне това blush

1
12/11/2018 16:09:52
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.