[c++]Przyśpieszenie programu

Question

Witam, pisałem ostatnio program, który jest rozwiązaniem pewnego zadania z pewnego serwisu. To jest jednak mniej ważne. Chodzi o to, że na serwisie automatyczna "sprawdzarka" powiedziała, że program przekracza limit czasowy. Czy jest jakiś sposób na przyśpieszenie tego kodu? Spróbowałem nawet na tę okazję nauczyć się wskaźników, ale nic nie dały. Może źle ich użyłem? To mój kod ...

#include <iostream>

using namespace std;

unsigned long ile;
unsigned long tempOdleglosc = 1000000;

int main()
{
    cin >> ile;

    unsigned long *koralik = new unsigned long [ile];
    unsigned long *k_index_2 = koralik;
    unsigned long *k_index_3 = koralik;

    for(unsigned long i = 0; i < ile; i++){
        cin >> *koralik;

        k_index_2 = k_index_3;

        if(i > 0){

            for(unsigned long z = 0; z < i; z++){
                unsigned long odleglosc = i - (z+1);
                if(odleglosc < tempOdleglosc){
                    if(*k_index_2 == *koralik){
                        if(odleglosc < tempOdleglosc){
                            tempOdleglosc = odleglosc;
                        }
                    }
                }
                k_index_2++;
            }
        }
        koralik++;
    }

    cout << tempOdleglosc << endl;

    return 0;
}

a zadanie polega na tym, że :
Mamy n koralików ustawionych w pewnej kolejności, wśród których każdy ma określony kolor. Teraz należy powiedzieć w jakiej minimalnej odległości są dwa koraliki tego samego koloru, gdzie odległosć między dwoma koralikami jest rozumiana jako liczba koralików, które znajdują się między nimi. Można bezpiecznie założyć, że zawsze istnieją przynajmniej dwa koraliki tego samego koloru. Pierwsza liczba jaką pobieram to N czyli ta ilość koralików(maks. 10 do potęgi 5), a potem pobieram w pętli koraliki. Każdy koralik ma kolor który ma być w programie określony cyfrą (maks 10 do potęgi 9). Muszę podać najmniejszą możliwą odległość takich samych koralików.

Z góry dziękuję za fatygę :)

Answer 1

Zdecydowanie musisz zmiejszyć złożoność algorytmu. Obecnie masz n^2, co jest jedną z gorszych złóżoności jeśli masz limit. Ja bym zrobił to tak:

Po pierwsze zadeklarowałbym obiekt klasy map. Używając jednej pętli for przejechałbym po całej tablicy i używał metody find. Jeśli by znalazło obiekt to czytam index, pod którym wystąpił dany kolor i od aktualnego indexu odjął tamten co by było ich odległością, a jeśli by nie znalazło to bym dorzucił do obiektu nowy kolor i index, pod którym się znajduje. To rozwiązanie gwarantuje złożoność rzędu nlogn co już jet wynikiem chyba najoptymalniejszym w tym zadaniu. Osobiście inttego sposobu nie widzę na uproszczenie.

Jeżeli nie wiesz co to jest klasa map to jest to standardowa klasa kontenerowa, w której przechowujesz dwa odpowiadające sobie elementy np kolor i index, pod którym występuje ten kolor.

#include <map>

map<unsigned long, unsigned long> _map;
//cały program

//pętla for

map<unsigned long, unsigned long>::iterator it = _map.find(color);
if (it == _map.end())
{
	_map.insert(make_pair(color, i));
}
else
{
    if(i-it->second -1 < odleglosc)
    {
        odleglosc = i-it->second-1;
    }
}

 

Comments

Ze złożonością zgadzam się jak najbardziej, aczkolwiek nie wiem czy osoba (która nauczyła się dopiero wskaźników ) programująca proste programiki dla sędziego internetowego jest obeznana z STL, może na początek po prostu "struct" a w celach dydaktycznych wystarczy.

Pozdrawiam

---

dziękuję, mam jeszcze problem z jednym elementem programu ale z wykorzystaniem stl program działa 10 razy szybciej. Musiałem się przy okazji nauczyć obsługi stl...

Answer 2

Najczęstszą przyczyną przekraczania czasu wykonania zadania jest po prostu: "Nieoptymalny algorytm" :). W tak małych aplikacjach zastosowanie wskaźników nie przyśpieszy znacznie programu.  

Prosty przykład do zastanowienia: czy zastosowanie wskaźników w algorytmie sortowania BubbleSort zbliży nas do szybkości sortowania przez QS dla odpowiednio dużego n ? (Korzystając z przykładu Pana Mirosława na YT)

Czasem warto wziąć czystą kartkę i długopis, zaplanować algorytm i dopiero potem przejść do kompilatora. A nóż po kilku próbach się okaże, że nasz poprzedni algorytm był do przysłowiowej "bani" ?

 

Pozdrawiam

Piotrek