Софтуерно Инженерство
Loading...
milenmilen avatar milenmilen 0 Точки

JA1-Task-4-Roxettes

Не знам дали е прието да си поставяме кода тук, ако не е прието обещавам да не правя повече така. Та идеята ми е къде може да се оптимизира кода по-долу защото judge гърми та трещи от 6-ти тест нататък за време и на последния за памет.

#include <iostream>
#include <vector>
#include <sstream>

using namespace std;

int main() {
    string dnaSequence {};
    vector<short int> dnas;
    unsigned short int pos;
    cin >> dnaSequence;
    unsigned int length = dnaSequence.length();
    if (length > 15) {
        string currDna{};
        for (int i = 0; i <= length; i++) {
            if (i % 5 == 0 && i > 0) {
                short int x = stoul(currDna, nullptr, 16);
                dnas.push_back(x);
                currDna = {};
            }
            currDna = currDna + dnaSequence[i];
        }
        unsigned int numDna = (length - 1)/5;
        for (int i = 0; i < numDna; i++) {
            bool isUnique{true};
            for (int j = 0; j < numDna; j++) {
                if (i != j && dnas[i] == dnas[j]) {
                    isUnique = false;
                    break;
                }
            }
            if (isUnique == true) {
                pos = i;
                break;
            }
        }
        for (int i = pos * 5; i <= pos * 5 + 4; i++) {
            cout << dnaSequence[i];
        }
    }
    else if (dnaSequence.length() == 6){
        cout << dnaSequence << endl;
    }
    return 0;
}

Тагове:
0
C++ Fundamentals
georgi.stef.georgiev avatar georgi.stef.georgiev 921 Точки

Здравей,

Принципно не е прието (няколко други колеги също го направиха, днес ще предупредя изрично на лекцията), защото другите могат да го копират - не е болка за умиране, но предпочитам да не го правите. По-добра идея е да опишеш горе-долу какво правиш или да дадеш част от код, който те съмнява (в твоя случай няма как, защото мислиш за цялата програма).

Проверката за това дали нещо е уникално е твърде бавна (ще направиш общо N * N проверки - за всеки елемент ще провериш всички останали). Тоест като цяло подходът ти към решението не е правилен, колкото и да оптимизираш части от него, трудно ще стигнеш до пълни точки по този начин (един колега го е постигнал, защото съм забравил да сложа ограничението за памет, но тъй като вече е изкарал точки ще оставя ограничението така - неговото решение е силно оптимизирано и ползва неща от по-нататък в курса, но пак не е най-бързия вариант).

Днес в началото на лекцията ще дам подсказка за тази задача, както бях обещал миналия път да направя ако видя, че никой не е хванал правилния път за решение (защото може да се каже, че се ползва нещо, което не сме учили, или поне не сме му обръщали внимание на свойствата).

Поздрави,

Жоро

0
fantom4e avatar fantom4e 24 Точки

Здравей Георги.
В предишния курс задачата ме изяде, тогава не успях да взема 100те точки точно поради 2та мегабайта ограничение.В момента си мисля, ако използвам двумерен масив от чарове в които една Роксет ДНК ще бъде 5бита, ще ми позволи ли да се вмъкна  във времето и 2MB памет?

0
28/11/2017 23:39:28
georgi.stef.georgiev avatar georgi.stef.georgiev 921 Точки

Здравей,

В паметта може и да се вмъкнеш (както е настроена сега за 16 МБ, вместо 2-та които пише в условието), но във времето почти със сигурност няма да се вмъкнеш само с масив - търсенето ще ти отнема твърде много време. set би бил по-добър вариант (търсенето е много по-бързо).

При всички положения това, което обясних на лекцията, е доста по-бързо и ефикасно от всички други подходи, които се мъчат да пазят самите елементи.

Поздрави,

Жоро

0
MartinBG avatar MartinBG 1169 Точки

Задачата наистина е много добра! :)

 

В предишното издание на курса успях да се вмъкна в изискването за памет като ползвах bitset (това решение може да се приложи за произволен брой уникални ентрита), но правилното решение е друго (hint - побитови операции).

0
milenmilen avatar milenmilen 0 Точки

Жоро, направих нещата както даде hint на 3-тата лекция, но пак гърми за памет на последния 10-ти тест. Ако имаш време и желание може да погледнеш тук. Аз не се сещам какво още може да оптимизирам на тоя код от 13 реда реална програма.

0
MartinBG avatar MartinBG 1169 Точки

Четеш всички входни данни наведнъж и при голям входен поток минаваш лимита за памет.

Лесно (и неоптимално) решение на този проблем е да четеш символ по символ от конзолата. По-смислено решение е да използваш буфер с фиксиран от теб размер, който се вписва в лимитите за памет и ускорява изпълнението на програмата (по-малко заявки към конзолата).

0
29/11/2017 22:58:21
georgi.stef.georgiev avatar georgi.stef.georgiev 921 Точки

Да, Мартин правилно е отбелязал, че няма смисъл да четеш целия string в паметта, и чак след това да го обработваш. На теб във всеки един момент от задачата ти трябва само текущото "число"/dna, не ти трябва да си пазиш в паметта всички. Тоест за тази задача работи да си имаш char xorred[5] за "резултата", който xor-ваш, и още един char current[5], в който четеш с по един cin всеки елемент.

Разбира се да четеш много пъти по 1 елемент е по-бавно отколкото веднъж да прочетеш толкова на брой елементи. Затова Мартин предлага да четеш колкото памет ти е разрешено в judge в един масив/стринг и след това да обработиш това парче, след това пак да прочетеш толкова и т.н. - това ще е още по-бързо, но за текущите ограничения варианта с 5-те cin-а на всяка итерация също върши работа.

Поздрави,

Жоро

0
milenmilen avatar milenmilen 0 Точки

Жоро, Мартине благодаря, преборих ги до 100/100. Без вашите hints нямаше как да се усетя, все пак съм само на един Cpp basics към момента.

0
kolioi avatar kolioi 592 Точки

Аз си поиграх малко с тая задачка и тествах различни неща. Успях да направя няколко работещи решения, които се вместват в ограничението за 2MB памет. Най-доброто е това

JA1-Task-4-Roxettes

Постига се когато се чете само по един символ. Ако се четат няколко символа едновременно, времето за изпълнение е малко по-голямо.

0
MartinBG avatar MartinBG 1169 Точки

@kolioi 

Ето моето най-бързо решение (link expires in 2 weeks) от предишното издание на курса (наблягам на "най-бързо", защото кодът не от най-лесно разбираемите, въпреки че е само 30-на реда):

Memory: 1.85 MB 
Time: 0.103 s

BTW eдин колега беше успял да смъкне времето до 0.062 с още микрооптимизации и по-голям буфер.

0
kolioi avatar kolioi 592 Точки

Ами аз забравих да кажа, че моят код е оптимизиран за памет. Цялата програмка е само 5-6 реда и имам само тези променливи

char ch, result[DNA_LENGTH + 1] { 0 };
size_t currIndex = 0;

Ако я оптимизирам за бързина, естествено трябва да чета по-голям буфер, т.е. да намаля входно-изходните операции. Което ще стане за сметка на паметта. Ако ми остане време тия дни, ще си поиграя още малко.

0
kolioi avatar kolioi 592 Точки

@MartinBG

Оптимизирах малко кода за бързина и успях да я докарам до тук

JA1-Task-4-Roxettes

С една забележка: кода ми е на С. Анси си. Голямо значение има размера на буфера и предполагам, че може да се оптимизира още, но не ми се занимава повече. Ще пусна малко код (поне 2-3 разични решения) след като мине срока.

0