Професионална програма
Loading...
damyan94 avatar damyan94 8 Точки

Задача Лекции

Здравейте! Моля за съдействие по задача 5 от домашното за тема 5. Смятам, че успях да я реша правилно, но отговорът в Judge е малко странен:

 

The process executing your submission for this test may not have received the output successfully. Please try to submit again the same solution. If the result does not change, then search the error in the submission itself.

 

Съответно пробвах да кача файловете неколкократно. Само на някои тестове дава грешка и резултатът е 40 %, но колкото и да го мъча и да го тествам с измислени от мен данни, винаги дава коректен резултат. Каква може да е причината? Ето и кода:

 

Lecture.h

#pragma once

#include "Resource.h"
#include "ResourceType.h"

namespace SoftUni
{
    class Lecture
    {
    private:
        std::vector<Resource> _resources;

    public:
        std::vector<Resource>* getResources() { return &_resources; }
        std::vector<Resource>::iterator begin() { return _resources.begin(); }
        std::vector<Resource>::iterator end() { return _resources.end(); }
        int operator[] (ResourceType resourceType);

    };

    // Main - line 27
    Lecture& operator<< (Lecture& lecture, Resource& resource)
    {
        bool ok = 1;
        for (int i = 0; i < (*lecture.getResources()).size(); i++)
        {
            if ((*lecture.getResources())[i].getId() == resource.getId())
            {
                (*lecture.getResources())[i] = resource;
                ok = 0;
            }
        }
        if (ok == 1)
            (*lecture.getResources()).push_back(resource);

        //sort po metoda na mehur4eto
        Lecture tempLecture;
        (*tempLecture.getResources()).push_back(resource);
        for (int i = 0; i < (*lecture.getResources()).size() - 1; i++)
        {
            for (int j = 0; j < (*lecture.getResources()).size() - i - 1; j++)
            {
                if ((*lecture.getResources())[j].getId() > (*lecture.getResources())[j + 1].getId())
                {
                    (*tempLecture.getResources())[0] = (*lecture.getResources())[j];
                    (*lecture.getResources())[j] = (*lecture.getResources())[j + 1];
                    (*lecture.getResources())[j + 1] = (*tempLecture.getResources())[0];
                }
            }
        }

        return lecture;
    }

    // Main - line 39
    std::vector<ResourceType>* operator<< (std::vector<ResourceType>& resourceType, Lecture& lecture)
    {
        bool ok = 0;
        ResourceType resType[3] = { PRESENTATION, DEMO, VIDEO };
        for (int i = 0; i < 3; i++)
        {
            ok = 0;
            for (int j = 1; j < (*lecture.getResources()).size(); j++)
            {
                if ((*lecture.getResources())[j].getType() == resType[i])
                {
                    ok = 1;
                }
            }
            if (ok == 1)
                resourceType.push_back(resType[i]);
        }

        return &resourceType;
    }

    // Main - line 42
    int Lecture::operator[] (ResourceType resourceType)
    {
        int count = 0;
        for (int i = 0; i < (*getResources()).size(); i++)
            if ((*getResources())[i].getType() == resourceType)
                count++;

        return count;
    }
}

 

Resource.h

#pragma once
#include "ResourceType.h"

namespace SoftUni
{
	class Resource
	{
	private:
		int _id;
		ResourceType _type;
		std::string _link;

	public:
		int getId() { return _id; }
		ResourceType getType() const { return _type; }
		friend std::istream& operator>>(std::istream& in, Resource& resource);
		friend std::ostream& operator<<(std::ostream& out, const Resource& resource);
		bool operator<(const Resource& resource) const { return _id > resource._id ? false : true; }
	};

	std::istream& operator>>(std::istream& in, Resource& resource)
	{
		std::string type;
		in >> resource._id >> type >> resource._link;

		if (type == "Presentation")
			resource._type = PRESENTATION;
		else if (type == "Demo")
			resource._type = DEMO;
		else if (type == "Video")
			resource._type = VIDEO;
		else if (type == "[unknown]")

			return in;
	}

	std::ostream& operator<<(std::ostream& out, const Resource& resource)
	{
		out << resource._id << ' ' << resource._type << ' ' << resource._link;
		return out;
	}
}

 

Тагове:
0
C++ OOP
j.petrov_90 avatar j.petrov_90 313 Точки

Привет, отново колега,

Успях да разгледам по-подробно решението ти.
Като цяло си я преборил задачата.

Единствената грешка, която успях да намеря е, че когато добавяш нов ресурс в метода ти:

std::vector<ResourceType>* operator<< (std::vector<ResourceType>& resourceType, Lecture& lecture)

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

До тук с необходимата критика.
От тук насам следва advanced градивна критика. Пак повтарям, че критиката е градивна, а нямам за цел "да те насоля" :)

Решението, което си избрал с вектори е едновременно неподходящо и крайно бавно.
1) Ти сортираш контейнера си на всяко добавяне на нов ресурс. Това е доста неефективно.
Отделно - метода на мехурчето е един от бавните алгоритми за сортиране (O(N^2)).
Стандартната библиотека ти предоставя готов std::sort() алгоритъм, който има гарантирана O(N*logN) сложност.

2) Можеш да помислиш да ползваш структурата от данни std::set, както колегата Илиян е предложил.
Тя ще се справи със ситуацията с логаритчична сложност. За спарвка - при сортирането с std::sort ще бъде N*logN.
Отделно set-а авточатично би ти решил проблемите с дубликатите отново за логаритчимна сложност.

3) Методът ти:

int Lecture::operator[] (ResourceType resourceType)

отново е неефективен, защото всеки път итерираш около всички елементи.
Ако видиш извикнавено му в main функцията ще видиш, че се вика в range based for loop.
Значи ефективно за всеки елемент ти отново обикаляш всички елементи.
Това си е квадратична сложност, което си е скъпичко.
Опитай в задачата да имаш още един контейнер, с който просто броиш кой ресурс колко пъти го има.
Товата просто проверявай какво има в този контейнер в същия този operator[].

4) Избрал си да върнеш ресурсите по пойнтър тук:

std::vector<ResourceType>* operator<< (std::vector<ResourceType>& resourceType, Lecture& lecture)

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

5) Поздравления, че си успял да имплементираш задачата с public operator<<.
Съгласи сe обаче, че щеше да е доста по-четимо (да не говорим колко по-бързо), ако просто беше написал friend на същия този operator<<.

Забележи в твоята имплементация колко много пъти ненужно се извиква "getResources()"

Поздрави,
Живко

1