Loading...
damyan94 avatar damyan94 9 Точки

Наследяване - задача 5

Здравейте, при качване на решението на тази задача в Judge ми дава грешка само на последния тест - просрочено време. Пробвах по може би аматьорски начин да установя къде има забавяне чрез тест с голям набор от входни данни, точки на прекъсване и закоментиране на част от кода. По този начин успях да установя, че най-проблемно е прехвърлянето на имената на служителите в паметта, както е посочено и в кода по-долу.

 

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

 

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

#ifndef SERIALIZE_H_
#define SERIALIZE_H_

#include <string>
#include <sstream>

byte* serializeToMemory(std::string inputString, size_t& bytesWritten)
{
    bytesWritten = 0;
    std::istringstream is(inputString);
    Company company;
    std::vector<Company> companies;
    unsigned char numCompanies = 0; // this variable was changed to type int for the purposes of testing with many companies

    // read string to vector of companies
    while (is >> company)
    {
        companies.push_back(company);
        numCompanies++;
    }

    // calculate size in bytes of the vector of companies
    int companiesSizeInBytes = 0;
    for (int i = 0; i < numCompanies; i++)
    {
        companiesSizeInBytes += sizeof(unsigned char);
        companiesSizeInBytes += companies[i].getName().size() + 1;
        companiesSizeInBytes += companies[i].getEmployees().size() * 2;
    }

    bytesWritten += sizeof(numCompanies); // for the number of companies
    bytesWritten += companiesSizeInBytes; // for the companies themselves
    bytesWritten += numCompanies; // for the number of employees after the name of each company

    byte* bytes = new byte[bytesWritten];
    bytes[0] = numCompanies;

    int j = 1;
    for (int i = 0; i < numCompanies; i++) // total 37ms from test with ~3300 companies
    {
        // write company ID
        bytes[j] = companies[i].getId();
        j ++;

        // write company name 5ms
        std::string companyName = companies[i].getName();
        for (int k = 0; k < companyName.size(); k++)
        {
            bytes[j] = companyName[k];
            j++;
        }

        // write 0
        bytes[j] = '\0';
        j++;

        unsigned char numEmployees = companies[i].getEmployees().size();
        bytes[j] = numEmployees;
        j++;

        //THIS IS THE SLOW PART OF THE PROGRAM

        for (int k = 0; k < numEmployees; k++)
        {
            // this was the first version i tried, it took only for this 'for' cycle alone 25 ms
            /*bytes[j] = companies[i].getEmployees()[k].first;
            j++;
            bytes[j] = companies[i].getEmployees()[k].second;
            j++;*/
            
            // after this change the total time for the cycle was 12ms, that is 13ms faster or almost 35%
            std::pair<char, char> pair = companies[i].getEmployees()[k];
            bytes[j] = pair.first;
            j++;
            bytes[j] = pair.second;
            j++;
        }
    }

    return bytes;
}

#endif // !SERIALIZE_H_

 

Тагове:
1
C++ OOP
zzerro avatar zzerro 16 Точки

Защо правиш (повтаряш) отделен цикъл, за да пресметнеш "calculate size in bytes of the vector of companies"? Можеш да направиш тези сметки още при въвеждането в тялото на while.

Аз се полакомих да използвам функциите на вектор и после да прехвърля всичко в масив и гледам, че ми  дава 100:

#ifndef SERIALIZE_H
#define SERIALIZE_H

byte* serializeToMemory(std::string s, size_t &bytesWritten)
{
	std::vector<byte> vB;

	byte companies = 0;
	vB.push_back(companies); //reserve position to calibrate later

	std::istringstream iss(s);
	Company company;

	while (iss >> company)
	{
		vB.push_back((byte)company.getId());

		for (auto chN : company.getName())
			vB.push_back((byte)chN);

		vB.push_back(0);

		vB.push_back((byte)company.getEmployees().size());

		for (auto empl : company.getEmployees())
		{
			vB.push_back((byte)empl.first);
			vB.push_back((byte)empl.second);
		}

		++companies;
	}

	vB[0] = companies; //calibrate number of companies

	bytesWritten = vB.size();
	byte* arrB = new byte[bytesWritten];

	for (size_t i = 0; i < bytesWritten; i++)
		arrB[i] = vB[i];

	return arrB;
}

#endif //SERIALIZE_H

 

1
26/08/2021 13:34:59
ditchev avatar ditchev 36 Точки

Здравей, Дамян,

проблема ти възниква от 10-тия ред отдолу нагоре, по-точно:

std::pair<char, char> pair = companies[i].getEmployees()[k];

При всеки отделен служител се вика функцията getEmployees(), която копира по value

std::vector<std::pair<char, char> > employees

и го връща като анонимен вектор. От него се извличат инициалите на 1 (един) служител и ... целия доставен вектор се затрива :((

И за следващия служител пак, и за по-следващия пак, и пак, и пак ... :)))

Това не е безплатно :))

А при повече служители (предполагам, че в последния тест те са над 4-5000) това боли ... :)))

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