[10. * Array Manipulator] Ако може някой да ми помогне да си я оправя?
Здравейте, това е кода -> http://pastebin.com/spirDzyx дава 87 в джъдж и само два грешни теста. Ако някой вижда грешката, която аз не ще съм му признателен.
Окей, вече официално изчерпах всякакви идеи. Пробвах 3 варианта за прочит на input даннте:
1. Всичко да се записва на един списък от списъци "task" --> task[0] да държи числата от масива, а task[1] до task.Count - операциите и аргументите им (напр. task[1][0] = "add", task[1][1] и task[1][2] са двата аргумента). При този вариант успях да смъкна паметта до 17.07 MB.
2. Числата от масива да се изведат в отделен списък, а командите да останат разбити в списък от списъци. Най-бавният вариант, зае около 18 MB памет.
3. Числата от масива да се изведат в отделен списък, а при всеки input line с нова команда информацията да се записва в един и същи списък тип string (и да се избегне ползването на голям брой списъци). Надявах се това да върне резултат под 17 MB, но уви - Judge каза 17.5 MB.
Вече не знам какво друго бих могъл да променя, за да олекотя решението. В дефинициите на отделните операции съм направил всичко по силите си да избегна използването на Delete (с последващо преиндексиране на елементите на масива).
Ето пълния код на програмата (вариант 3), ако някой има идеи кое ангажира толкова ресурси, моля да ме светне:
http://pastebin.com/bXHmYtxQ
Здравей! Разгледах твоя код и ето как мисля че може да се оптимизира:
Вместо да използваш Лист List<string> task за да прочетеш входа на командата можеш да използваш масив от стингове string[] task. Така ще бъде заделена по-малко памет за входа. Забелязах че използваш index два пъти, можеш да си го инициализираш само един път в началото на switch-case-а. За addMany командата използваш отново лист, може да се използва пак масив, защото дължината е ясна, а можеш и да работиш направо върху input-а във for-цикъла. За sumPairs пак можеш да работиш върху входния лист с числата вместо да създаваш нов и така ще се избегне голяма част от функционалното програмиране. Като цяло, забелязах че на много места употребяваш допълнителни методи които ти заемат повече памет. Бих ти препоръчал да си направиш собствени методи. Както каза и Наков повече писане(по-голям обем на кода), заема по-малко ресурси. Ето моето решение http://pastebin.com/LaVNitsb в Judge заема 16.88MB Това е с което мога да помогна. Успех!
Здравей,
По погрешка качих малко по-стара работна версия на кода, където нарочно бях инициализирал index променливата два пъти - исках да проверя дали това може да се прави ако се използват "{ }" скоби в тялото на всеки case. Това със сигурност не е е проблем, защото в последвалата версия изцяло премахнах подобни променливи, както и проверката дали 0 < index < input.Count, но това, уви, не намали количеството заделена памет.
Относно използването на списъци вместо масиви - правя го съвсем тенденциозно, защото искам да свикна с функционалността им. Във видеото от лекцията Наков уверяваше, че разликата в заемания ресурс е не повече от 5% (а в случая аз трябва да смъкна цял MB за да достигна memory target-а). Ако видя, че се доближавам до него - разбира се, и това ще направя. За sumPairs отначало работих точно с входния масив и резултатът не беше с нищо по-добър. Нарочно въведох допълнителен списък, за да избегна използването на RemoveAt() метода, който гълта повече памет (при всяко отстраняване на елемент следва преиндексиране), и това определено беше подобрение в сравнение с предходния submission в Judge-а.
Не разбирам частта за допълнителните методи - да не би да е нещо, което е било дискутирано на място (или съм пропуснал от видеото)? Примерно от кода, който си качил, с какво RemovesElement е по-добър от директното извикване на numbers.RemoveAt(index)? Нали в тялото си извиква точно този метод? Нещо не разбирам идеята... Също така, кодът, който annsta е качила по-горе не използва никакви собствени методи и когато го тествах мина с нещо от типа на 16.6-16.7MB! Той всъщност изглежда доста близък до това, което аз съм направил в моята програма (изключвайки частта с проверката дали input = "print") и все още не мога да разбера защо дава такава разлика!
Здравей отново. Поиграх си малко с твоя код и го сравних с този на annsta и стигнах до заключение че листовете ти заемат много ресурси, където можеш ако използваш масиви вместо листове заеманата памет пада драстично до 16,95MB.Тъй като всяка клетка от списъка съдържа указател към следващата клетка, то всеки елемент заема повече памет, отколкото би заемала клетката в масив. Когато информацията във всяка клетка е относително много, това не е проблем, но ако просто пазим по един
int, то ние ще се нуждаем от поне двойно повече памет. Нашата имплементация ще е двусвързан списък, тоест ще имаме и още един указател към предходния елемент в списъка, което прави нещата дори по-зле в това отношение. Например във версията която си качил смених List<string> task със string[] task , и List<int> shifted със int[] shifted, и там където използваш List<int> tempList за sumPairs го направих без допълнителен лист, а директно работиш върху входния лист с числа. След промените го тествах в Judge и ми даде този резултат. Прав си че в моя случай RemovesElement извиква в тялото си numbers.RemoveAt(index), но това с изнасянето в метод го правя за да се тренирам :-).Наистина - само смяната на списъка от команди с масив от такива докара паметта почти до желаното ниво!
Аз все си мислех, че 5% разлика в ефективността на двете се отнася до ресурса, който ползват те, а не целия ресурс, който се заделя за програмата (т.е. крайната промяна няма да е от порядъка на 0.5-1MB, а по-скоро 0.05-0.10). Затова си държах списъка от команди, чудейки се каква по-голяма промяна трябва да се извърши за да се свали цял MB памет. Но както казват - "Една патка мислила, мислила..." :))
Благодаря ти много, че ме светна за това! Ще гледам в бъдеще да не си правя предположения, базирани на нещо, което съм чул някъде, а да тествам всичко от първа ръка :)