Praca domowa - odc.13 rekurencja, silnia i pętla for

Question

Witajcie koledzy!

Szukałem ale nie znalazłem - temu zwracam się o pomoc do Was!

O ile część problemów sam rozwiązałem lub wygooglowałem o tyle z jednym problemem nie mogę sobie poradzić, mianowicie z czasem.

Coś widać robię źle, że nie mierzy mi dobrze czasu, pomożecie?

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

using namespace std;

clock_t start1, stop1;
clock_t start2, stop2;
double czas1;
double czas2;
int ile;


long double silnia1(int n)
{
    if (n==0) return 1;
    else return n*silnia1(n-1);
}


int main()
{
    long double silnia2=1;

    cout << "Z ilu wyliczyc silnie: ";
    cin >> ile;

    if (ile<0) cout<<"Nie ma silni z liczb ujemnych!!"<<endl;
    else
    {
        start1 = clock();
        cout << "Rekurencja: " << silnia1(ile) << endl;
        stop1 = clock();
        czas1 = (double)(stop1-start1) / CLOCKS_PER_SEC;
        cout <<"Czas obliczen (Rekurencja): " << czas1 << " sekund" << endl;

        start2 = clock();
        for(int i=1; i<=ile; i++)
        {
            silnia2*=i;
        }
        stop2 = clock();
        czas2 = (double)(stop2-start2) / CLOCKS_PER_SEC;
        cout << "Iteracja: " << silnia2 << endl;
        cout <<"Czas obliczen (Iteracja): " << czas2 << " sekund" << endl;
    };

    return 0;
}

 

Comments

Co to znaczy, że nie mierzy Ci dobrze czasu?

---

Inna sprawa, że użycie clock do mierzenia czasu jest słabym pomysłem: http://en.cppreference.com/w/cpp/chrono/c/clock

---

Tak - prawie cały czas mi 0 sekund pokazuje

---

Po prostu dzieje się to tak błyskawicznie, że nie zajmuje prawie w ogóle czasu. Dodaj do tego jeszcze słabą dokładność clock() i masz odpowiedź.

Answer 1

Dla wartości 30 będziesz mieć zauważalną (tak mi się wydaje) różnicę przy użyciu clock'a. Jednak to co robisz jest złe i błędne. Nie ma sensu liczenia silni na liczbach zmiennoprzecinkowych - tracisz na nich dokładność więc wyniki są błędne. Dodaj sobie na początku maina:

cout << fixed;

Porównaj sobie z poprawnymi wartościami dla zakresów 20-30: link
Do tego czas rekurencji mierzysz razem z wypisywaniem wartości, a iteracje bez tego. Jak to mówi mój kolego - bez sęsu. Zawyżasz czasy rekurencji. Powinieneś mierzyć czas tylko wykonania samego algorytmu, bo wypisywanie w konsoli jest wolne. Jeżeli rozwiązanie z clock podaje wartość 0 to wykonaj daną funkcję kilka razy, lub zrób to tak jak się robi w dzisiejszych czasach (z użyciem chrono) żeby uzyskać większą dokładność.

Answer 2

template<typename Func, typename... TT>
void check_time(const string& message, Func func, TT&& ...tt) {
    using namespace chrono;
    cout << message << endl;
    auto start_time = high_resolution_clock::now();

    func(std::forward<TT>(tt)...);

    auto end_time = high_resolution_clock::now();
    cout << "Wykonanie zajęło: " 
        << duration_cast<microseconds>(end_time - start_time).count()
        << " us.\n";
}

Można tak. A jak będzie za mała rozdzielczość, argument powtórzeń dodasz sam.