• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Co można przyśpieszyć w tym czymś?

VPS Starter Arubacloud
0 głosów
610 wizyt
pytanie zadane 28 września 2017 w C i C++ przez jankustosz1 Nałogowiec (35,880 p.)
edycja 28 września 2017 przez jankustosz1

Takie mam zadnie:

https://szkopul.edu.pl/c/oboz10-14grupa2/p/akc/

niby bardzo proste a połowy testów mi nie zalicza - limit czasu:

#include <iostream>
#include <map>
using namespace std;

map<int, int>mapa;

void LoadujCzasteczki()
{
    int count;
    cin>> count;
    for(int i = 0; i< count; i++)
    {
        int id;
        cin >> id;
        mapa[id]++;
    }
}
void WypiszWyniki()
{
    int count;
    cin>> count;
    for(int i = 0; i< count; i++)
    {
        int pytanie;
        cin >> pytanie;
        cout << mapa[pytanie] << '\n';
    }
}

int main()
{
    ios::sync_with_stdio(0);

    LoadujCzasteczki();
    WypiszWyniki();
    return 0;
}

więc zrobiłem to co pisało żeby zrobić czyli wyszukiwanie binarne

#include <iostream>
#include <vector>
#include <map>
using namespace std;

struct Czasteczka
{
public:
    int rodzaj;
    int count;
    Czasteczka(int rodzaj, int count)
    {
        this->rodzaj =rodzaj;
        this->count = count;
    }
};

vector<Czasteczka> tab;

void LoadujCzasteczki()
{
    int count;
    cin>> count;
    int poprzedniNr = -1000000001;
    for(int i = 0; i< count; i++)
    {
        int id;
        cin >> id;
        if(poprzedniNr == id)
            tab[tab.size()-1].count++;
        else
        {
            poprzedniNr = id;
            tab.push_back(Czasteczka(id, 1));
        }
    }
}

int GetCount(int wartosc, int odileSzukac = -1, int doileSzukac = -1)
{
    if(odileSzukac == -1)
        odileSzukac = 0;
    if(doileSzukac == -1)
        doileSzukac = tab.size()-1;

    while(true)
    {
        int polowa = (doileSzukac - odileSzukac + 1) / 2;
        if(tab[polowa].rodzaj == wartosc)
            return tab[polowa].count;
        else if(doileSzukac == odileSzukac) /// jezeli nie jest to ta wartosc to zwarca 0
            return 0;
        else
        {
            if(tab[polowa].rodzaj < wartosc)
            {
                odileSzukac = polowa+1;
            }
            else
            {
                doileSzukac = polowa -1;
            }
        }
    }

}

void WypiszWyniki()
{
    int count;
    cin>> count;
    for(int i = 0; i< count; i++)
    {
        int pytanie;
        cin >> pytanie;
        cout << GetCount(pytanie) << '\n';
    }
}
int main()
{
    ios::sync_with_stdio(0);

    LoadujCzasteczki();
    WypiszWyniki();
    return 0;
}

i jest jeszcze wolniej - żadnego testu nie przechodzi :(

1 odpowiedź

0 głosów
odpowiedź 28 września 2017 przez adrian17 Ekspert (344,100 p.)

Pierwszy kod: trudno powiedzieć, na co tam narzekają przypadki testowe. Być może niektóre próbują dużo wyszukiwać liczbę rzeczy których w ogóle nie było w wejściu? W takim przypadku mapa[pytanie] jest potencjalnie wolne; spróbuj użyć zamiast tego mapa.find(pytanie).

(przy okazji, to też przypadek w którym widać wpływ innej struktury danych; użycie std::unordered_map (hashtable) zamiast std::map (drzewo wyszukiwania binarnego) w skrajnych przypadkach daje mi 5x przyśpieszenie)

więc zrobiłem to co pisało żeby zrobić czyli wyszukiwanie binarne

std::map to jest drzewo wyszukiwania binarnego.

i jest jeszcze wolniej - żadnego testu nie przechodzi :(

Chyba/pewnie masz jakiegoś buga. Nie testowałeś kodu na własnym komputerze?

komentarz 28 września 2017 przez jankustosz1 Nałogowiec (35,880 p.)
testowałem, u mnie działa, tam też błędów nie robi ale jest za wolne.

std::unordered_map jest w c++ 11 z tego co pamiętam a oni go nie obsługują
1
komentarz 28 września 2017 przez adrian17 Ekspert (344,100 p.)

testowałem, u mnie działa, tam też błędów nie robi ale jest za wolne

To za mało testowałeś. Przykładowe wejście które się zacina:

5
1 2 3 4 5
1
4

z tego co pamiętam a oni go nie obsługują

Jest 2017. Jeśli "konkurs" celujący w pisanie wydajnego kodu nie pozwala na używanie standardowych w tym momencie narzędzi do pisania wydajnego i czytelnego kodu, to można by powiedzieć że nie chcą żebyś się nauczył porządnie programowania.

komentarz 28 września 2017 przez jankustosz1 Nałogowiec (35,880 p.)

Zrobiłem żeby było z tą metodą find w ten sposób:

void WypiszWyniki()
{
    int count;
    cin>> count;
    for(int i = 0; i< count; i++)
    {
        int pytanie;
        cin >> pytanie;
        map<int,int>::iterator it = mapa.find(pytanie);
        if(it != mapa.end())
            cout << it->second << '\n';
        else
            cout << "0\n";
    }
}

Nic się nie zmieniło dalej "Przekroczenie limitu czasu"

komentarz 28 września 2017 przez jankustosz1 Nałogowiec (35,880 p.)
wydaje mi się że jakiegoś, buga mają, albo źle dobrane te limity bo to jest niemożliwe, żeby 0 pkt dawało. Choć jak wchodzę w rankingi to prawie wszyscy tam po 100 pkt mają, więc musiało kiedyś to dobrze działać
komentarz 28 września 2017 przez adrian17 Ekspert (344,100 p.)
Na moje oko to tutaj już 90% czasu jest spędzone w IO... spróbuj jeszcze może pokombinować z użyciem scanf/printf zamiast cin/cout.
komentarz 29 września 2017 przez j23 Mędrzec (194,920 p.)
edycja 29 września 2017 przez j23

Ja bym tu mapy nie używał, bo dodawanie elementów do niej zabiera czas. Wiedząc, że zbiór jest posortowany, wystarczy użyć vectora, funkcję lower_bound i upper_bound (lub 2w1 - equal_range).

komentarz 29 września 2017 przez adrian17 Ekspert (344,100 p.)
Więcej czasu spędzisz w wyciąganiu szukanych wartości, niż dodawaniu elementów do std::map. (a potencjalnie najwięcej na IO, patrz wyżej)

Podobne pytania

–1 głos
1 odpowiedź 262 wizyt
–3 głosów
1 odpowiedź 109 wizyt
pytanie zadane 3 maja 2017 w HTML i CSS przez Vorex444 Dyskutant (9,610 p.)
0 głosów
0 odpowiedzi 41 wizyt
pytanie zadane 10 marca w Algorytmy przez Dani Obywatel (1,420 p.)

92,452 zapytań

141,262 odpowiedzi

319,085 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...