Zliczanie czasu procesora podczas sortowania

Otóż napisałem program "sortowanie przez wybieranie" Wygląda tak:

#include <windows.h>
#include <stdio.h>
#include <time.h>


const int N = 100;

int main()
{
  int Tab[N], i, j, min, x;
  long start, stop;
  start = 0;
  stop = 0;
  printf("Sortowanie przez wybor\n");
  printf("\n");


 srand((unsigned)time(NULL));

  for(i = 0; i < N; i++) Tab[i] = rand() % 100;



/*
  for(i = 0; i < N; i++) printf("%d ",Tab[i]);
    printf("\n");
*/

start = timeGetTime();
  for(j = 0; j < N - 1; j++)
  {
    min = j;
    for(i = j + 1; i < N; i++)
      if(Tab[i] < Tab[min]) min = i;
        x = Tab[min];
        Tab[min]= Tab[j];
        Tab[j]= x;
  }
stop = timeGetTime();

printf("Czas wykonywania sortowania wynosi: %li  \n\n",stop - start);
/*
  printf("Tablica po sortowaniu:\n\n");
  for(i = 0; i < N; i++) printf("%d ",Tab[i]);
*/
  return 0;
}
 

Do zliczania czasu użyłem timeGetTime lecz tablicy poniżej tysiąca wyświetla zero natomiast powyżej 1000000 wyrzuca mi program. Działa tylko w zakresie 1000-100000.

Jak temu zaradzić?

Nie tworzyć tablicy na stosie plus podzielić na funkcje.

Co to niby da?

Na Windowsie stos jest często ograniczony do 1 MB, a 1000000 32-bitowych intów to 3.5 razy tyle.

Jak zrobic zeby tablica nie tworzyla się na stosie?

Mamy XXI wiek, a Ty wciąż nie wiesz, co to Google.

Poszukaj hasła: alokacja na stercie.

A co z małymi wartosciami? Ponizej 1000

Też alokuj na stercie.
Głowna zasada programowania: nie kombinuj pod górkę.

Poniżej tysiąca wyrzuca zero, bo dokładność zegara jest zbyt niska. Musisz wybrać bardziej precyzyjną metodę odliczania czasu lub wykonać sortowanie wielokrotnie, a potem przeskalować wynik.

Udało mi sie to zrobić inie wyrzuca już programu gdy rozmiar jest powyżej 1000000 lecz dla wartosci ponizej 1000 czas dalej wynosi zero. Mógłby ktoś jeszcze doradzić?

#include <windows.h>
#include <stdio.h>
#include <time.h>


const int N = 100;

int main()
{
  int i, j, min, x, *Tab;
  float start, stop;
  start = 0;
  stop = 0;
  printf("Sortowanie przez wybor\n");
  printf("\n");

  Tab =(int*) calloc(N, sizeof(int) );

  srand((unsigned)time(NULL));

    for(i = 0; i < N; i++) Tab[i] = rand() % 100;

 /* for(i = 0; i < N; i++) printf("%d ",Tab[i]);
    printf("\n");

 */
start = timeGetTime();

  for(j = 0; j < N - 1; j++)
  {
    min = j;
    for(i = j + 1; i < N; i++)
      if(Tab[i] < Tab[min]) min = i;
        x = Tab[min];
        Tab[min]= Tab[j];
        Tab[j]= x;
  }
stop = timeGetTime();

printf("Czas wykonywania sortowania wynosi: %li ms ",stop - start);

 /* printf("Tablica po sortowaniu:\n\n");
  for(i = 0; i < N; i++) printf("%d ",Tab[i]);
*/free(Tab);
  return 0;
}
 

Nie zauważyłem postu. Znasz może tą bardziej precyzyjną metode? Z góry dziękuje

Na przykład rdtsc.
Ale oczywiście tyle stron w internecie przeszukałeś i nic nie było.

Tu jest metoda działająca tylko na Windowsie: https://support.microsoft.com/en-us/kb/815668

Ale ja bym po prostu odpalił więcej iteracji sortowania. Im dłużej trwa mierzona operacja, tym większa dokładność pomiaru, bo przy krótkich operacjach na wynik może mocno zaważyć przełączanie kontekstu (tzn przełączanie na inny wątek, przerzucanie programu na inny rdzeń i setki innych operacji, które wielozadaniowy system robi bez pytania się programów o zgodę).

Dziękuje za pomoc. Jeszcze jedno pytanie. Jak dla 100 000 000 czas sortowania jest za długi to można odpalić dla miliona i po prostu otrzymany wynik czasu pomnożyć przez sto? To będzie adekwatne do 100 000 000?

Nim wiecej razy odaplisz tym masz dokladniejszy wynik. Z arytmetyki pierwszoklasisty wynika ze czas jednego uruchomienia wynosi:
czas_calkowity / liczba_odpalen

z arytmetyki nowego programisty dokladnosc to:
rozdzielczosc_zegara / liczba_odpalen

rozdzielczosc zegara na windowsie to najczesciej okolo 30 milisekund.

Pomiary (przy porownywaniu) najczesciej maja sens tylko i wylacznie na dokladnie jednym komputerze ktory w momencie uruchomienia ma podobne obciazenie procesora, dysku i pamieci (i innych czynnikow ktore moga wplynac na pomiar). Bardzo rzadko jestes w stanie odtwarzalnie policzyc czasy, chyba ze jestes w stanie policzyc instrukcje procesora. (a i nawet to nie jest zawsze dobre)

Mały Szczur:
W ogólności: nie będzie. W niewielkiej ilości przypadków może tak być, ale program który czasem podaje poprawny wynik, a czasem nie, jest do d*py.

Chodzi o to że mam napisane kilka programów sortujących i z każdego z nich musze dostarczyć czas wykonania dla różnych tablic od 100 do 100 000 000. No ale dla 100 000 000 zajmie to mnóstwo czasu więc nie wiem jak to zrobić. Czy po prostu napisać że czas wykonania jest zbyt długi?

Tak. Jeżeli czas wykonania jest zbyt długi (limit ustalony wg własnego widzimisię) to przerywasz wykonanie i wypisujesz, że sortowanie trwało dłużej niż X sekund i zostało przerwane.

Dziękuje za pomoc, miłego dnia