Czas działania programu

Question

Cześć,

napisałem program z dynamiczną tablicą, do której przypisują się losowe liczby w zakresie od 1-1000. Następnie dana tablica jest sortowana metodą bąbelkową oraz wyświetlana jest posortowana tablica. Rozwiązałem ten problem metodą ze wskaźnikami oraz bez wskaźników, a także zmierzyłem czas działania poszczególnych metod. W teorii, metoda z wskaźnikami powinna być szybsza, a w moim przypadku, jest odwrotnie. Proszę o opinię czy jest taka sytuacja możliwa oraz czy coś źle zrobiłem. Z góry dziękuję.

#include <iostream>
#include <time.h>
#include <cstdlib>

using namespace std;


int fp(int *t, int ile);
void sort(int *t, int ile);
void swap(int *t, int ile);

clock_t start, stop;
double czaswsk, czasbwsk;

int main()
{
    int n;
    cout << "Ile liczb: ";
    cin >> n;
    srand(time(NULL));
    int *tab;
    tab=new int[n];
    int *wsk;
    wsk=tab;
    for (int i=0; i<n;i++)
    {
        wsk[i]=(rand()%1000)+1;
    }


start=clock();

    sort(tab,n);
    fp(tab,n);
    delete[]tab;
    cout << endl;


stop=clock();

czaswsk=((double)(stop-start)/CLOCKS_PER_SEC);


    tab=new int[n];


    for (int i=0; i<n;i++)
        {
            tab[i]=(rand()%1000)+1;
        }

    start=clock();
    int tempo;
    for(int i=0;i<n-1;i++)
    {
        for (int j=0;j<n-1-i;j++)
        {
            if(tab[j]>tab[j+1])
            {
                tempo=tab[j];
                tab[j]=tab[j+1];
                tab[j+1]=tempo;
            }
        }
    }
    for (int i=0;i<n;i++)
    {
        cout << tab[i] << " ";
    }
    delete[]tab;
    cout << endl;


    stop=clock();
    czasbwsk=((double)(stop-start)/CLOCKS_PER_SEC);
    cout << "Czas bez wskaznika: " << czasbwsk << "s\n";
    cout << "Czas z wskaznikiem: " << czaswsk << "s";
    return 0;
}

void swap(int *xp, int *yp)
{
    int temp=*xp;
    *xp=*yp;
    *yp=temp;

}

void sort(int *t, int ile)
{
    for (int i=0;i<ile-1;i++)
    {
        for(int j=0; j<ile-1-i;j++)
        {
            if(t[j]>t[j+1])
            {
                swap(t[j],t[j+1]);
            }
        }
    }
}

int fp(int *t, int ile)
{
    for(int i=0;i<ile;i++)
    {
        cout << t[i] << " ";
    }
    return 0;
}

 

Comments

A jakim cudem to się skompilowało - swap przyjmuje dwa wskaźniki a wołane jest z dwoma int-ami  (linia 97)?.

---

@Oscar kompilator użył standardowego std::swap. Normalnie powinien zostać dołączony nagłówek <algorithm>(do C++11), lub <utility>(od C++11), ale w zależności od implementacji standardu inne nagłówki mogą też je includować.

---

A dlaczego użył innego? I dlaczego nie ma konfliktu nazw?

---

Magia przeciążania.
Funkcja swap zdefiniowana w pliku main.cpp nie jest używana w programie. Zamiast tego program używa szablonu std::swap z biblioteki standardowej (Dlatego, że autor użył using namespace std).

---

Tak myślałem, że chodzi o przeciążanie. Ale nie spotkałem się z czymś takim jak przeciążanie własnej funkcji z funkcją z bilblioteki std.

Answer 1

Pierwszy błąd jaki widzę, poważny błąd!..... Operujesz na różnych tablicach liczb, powinieneś wylosować jedną tablicę liczb, a później ją sklonować / skopiować i pracować na tych samych danych w dwóch met. sort.

Użyj też dużych tablic, z dużą liczbą elementów.

Użyj instrukcji do skopiowania tab1 do tab2:

std::copy(std::begin(tab1), std::end(tab1), std::begin(tab2));

Tu masz lepszy. dokładniejszy sposób na pomiar czasu:

https://www.geeksforgeeks.org/measure-execution-time-function-cpp/

Comments

Kod miał służyć tylko w celu poglądowym, dlatego nie skupiałem się nad tym, aby program pracował na tych samych danych. Dopiero się uczę i sprawdzam jak wszystko działa, niemniej poprawiłem kod, aby pracować na tych samych danych i nie tworzyć dwa razy tabeli, tlyko skopiować. Zadeklarowałem drugą tabelę zaraz po stworzeniu pierwszej i skopiowałem zawartość nieposortowaną. Nie wiem skąd wyskakuje coś takiego. 

Ile liczb: 20
37 112 159 281 419 437 502 534 559 564 577 577 602 664 683 845 920 925 947 982
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7280576 40117392
Czas bez wskaznika: 0.006s
Czas z wskaznikiem: 0.008s
Process returned 0 (0x0)   execution time : 2.240 s
Press any key to continue.

Fragment kodu:

int n;
    cout << "Ile liczb: ";
    cin >> n;
    srand(time(NULL));
    int *tab1;
    tab1=new int[n];
    int *wsk;
    wsk=tab1;
    for (int i=0; i<n;i++)
    {
        wsk[i]=(rand()%1000)+1;
    }

    int* tab;
    tab=new int[n];
    copy(tab1, tab1,tab);

    start=clock();
    sort(tab1,n);
    fp(tab1,n);
    delete[]tab1;
    cout << endl;

 

Mam też drugie pytanie, gdyż zanim kod uzyskał postać jaką wysłałem powyżej, skopiowałem tab1 po jej usunięciu. O dziwo wartości były poprawnie skopiowane, natomiast nie rozumiem do końca w jaki sposób, gdyż pamięć ta została zwolniona i chyba nie ma do niej dostępu już później, czy coś źle rozumiem? Wynik nie był idealny, ale było widać, że wartości są skopiowane. Kod wcześniejszy:

int n;
    cout << "Ile liczb: ";
    cin >> n;
    srand(time(NULL));
    int *tab1;
    tab1=new int[n];
    int *wsk;
    wsk=tab1;
    for (int i=0; i<n;i++)
    {
        wsk[i]=(rand()%1000)+1;
    }


    start=clock();
    sort(tab1,n);
    fp(tab1,n);
    delete[]tab1;
    cout << endl;

    int* tab;
    tab=new int[n];
    copy(tab1, tab1,tab);

którego wynikiem było:

Ile liczb: 20
23 165 215 219 222 222 249 349 552 566 576 590 683 717 757 791 856 888 918 998
0 0 222 222 249 349 552 566 576 590 683 717 757 791 856 888 918 998 15931328 40838288
Czas bez wskaznika: 0.008s
Czas z wskaznikiem: 0.008s
Process returned 0 (0x0)   execution time : 1.713 s
Press any key to continue.

Nie rozumiem w takim razie skąd dwa zera na poczatku oraz liczby na końcu. 

 

P.s - jeśli chodzi o dokładniejszy sposób pomiaru czasu, dopiero do tego zajrzę. 
 

---

copy(tab1, tab1,tab);

Całego kodu nie sprawdzałem, ale widzę, że już tu nie dokładnie przepisałeś.

Nie możesz się odwoływać do skasowanych czy zwolnionych zmiennych (niby czasem się da, ale nie można tak robić, prowadzi to do różnych katastrofalnych w skutkach błędów)

---

No właśnie na początku po prostu skopiowałem i zamieniłem odpowiednio nazwy tabel i wyskakiwał wtedy błąd. "no matching function for call to 'begin(int*&)' ". Zadziałało dopiero po użyciu zapisu takiego, jak ten w kodzie.

 

Jeśli chodzi o kopiowanie tablicy po jej usunięciu, to tego właśnie dotyczy moje pytanie. Skąd bardziej poprawny rezultat kopiowania usuniętej tablicy niż po skopiowaniu przed usunięciem? No i nadal pozostaje kwestia dlaczego te wartości skopiowane nie są w pełni zgodne z oryginałem.

---

Jak chcesz pracować na danych na zwolnionej pamięci, to to prowadzi do UB (Undefined Behavior):

Undefined behavior is awesome - ub.pdf

https://cpp.mimuw.edu.pl/files/ub.pdf

Undefined behavior - cppreference.com
https://en.cppreference.com/w/cpp/language/ub

Undefined Behavior in C and C++ - GeeksforGeeks
https://www.geeksforgeeks.org/undefined-behavior-c-cpp/
 

Co do kopiowania tablic - zobacz poniższy komentarz od @Great.

---

@reaktywny std::begin/std::end nie może pracować na wskaźnikach do tablic dynamicznych, ale nadal poprawne będą inne metody:

copy(tab1, tab1 + n, tab2); 
copy_n(tab1, n, tab2); 

---

Dzięki za poprawienie, edytowałem swój wpis.

Answer 2

Dlaczego uważasz, że powinno być odwrotnie?
Wersja "ze wskaźnikami" to tak na prawdę wersja z wywoływaniem funkcji. Wywołanie funkcji powoduje dodatkowy narzut w programie (przesunięcie wskaźnika stosu, wrzucenie zmiennych, wywołanie kodu, odwinięcie stosu).

Comments

Nie wiem do kogo to pytanie, ale czy wywołanie funkcji z bublioteki std. nie powoduje podobnego narzutu?

---

Wywołanie jakiejkolwiek funkcji powoduje narzut.
Efekt ten możesz zniwelować przekazując do kompilatora flagi kompilacji.
Wtedy wywołanie szablonu std::swap powinno się skompilować do takiej samej postaci jak twój ręczny swap (w liniach 60-62) bez użycia instrukcji skoku/wywołania.

---

Dobrze wiedzieć.

---

@tangarr, W teorii chyba wskaźniki przyspieszają działanie programu, a że dopiero sprawdzam jak to wszystko działa, to stąd ten program - żeby właśnie zobaczyć to funkcjonowanie. 

Z tego też względu, że się dopiero uczę i rozeznaję, chciałbym dopytać o pojęcia, których nie rozumiem, to znaczy co to flaga kompilacji? Co znaczy odiwnięcie stosu, oraz na o co chodzi z tym stosem? Wiem, co to jest stos i jakie ma działanie, ale ine rozumiem o co chodzi dokładnie z stosem, który jak myślę funkjconuje w "tle". Byłbym wdzięczny za pomoc w zrozumieniu mi tego. Bardzo zależy mi na zrozumieniu co się dzieje za tymi komendami i poleceniami. Gdy wpisuje w internecie stos i podobne hasła, nie znajduje satysfakcjonujących mnie odpowiedzi. Pozdrawiam! 

 

P.s - poprawiłem swoją funkcję swap, faktycznie przeoczyłem kilka rzeczy, natomiast skorzystałem z rady i po prostu wykorzystałem funkcję swap wbudowaną.

---

Wskaźniki i referencje nie przyspieszają programu. Służą do wskazywania jakiegoś obszaru w pamięci. Użycie wskaźników/referencji jako parametrów funkcji pozwala uniknąć kopiowania tych obiektów (co może spowolnić wykonanie programu).

Jeżeli nie wiesz czym są flagi kompilacji to znaczy, że używasz zintegrowanego środowiska programistycznego i nie masz żadnego kontaktu z kompilatorem. Jak naciskasz przycisk zbuduj twoje IDE uruchamia kompilator i przekazuje do niego różne parametry (flagi kompilacji). Prawdopodobnie zauważyłeś że możesz budować programy w dwóch wersjach: debug oraz release. Wersja debug jest programem kompilowanym bez żadnych optymalizacji. Taki kod jest wolniejszy, ale bardzo łatwo jest śledzić jego wykonanie przy pomocy debuggera. Wersja release jest programem kompilowanym z włączonymi flagami optymalizacyjnymi. Kompilator potrafi wykonać wiele sztuczek, żeby przyspieszyć wykonanie programu.

Stos jest fragmentem pamięci programu odpowiedzialnym za sterowanie wykonaniem programu. Podczas uruchamiania funkcji tworzona jest nowa ramka na stosie zawierająca: argumenty przekazane do funkcji, zmienne lokalne funkcji oraz adres powrotu (adres w pamięci programu do którego program ma wrócić po wykonaniu funkcji). Po zakończeniu funkcji ta ramka jest zdejmowana ze stosu i program wraca do miejsca w programie w którym był przed skokiem do funkcji. Lepszy opis tej struktury znajdziesz na różnych wykładach w internecie.