Tidskomplexitet

Hej,

Jag försöker mäta tidskomplexiteten för olika sorteringsalgoritmer, men jag vet inte hur jag ska skriva ett bra program som mäter de olika tiderna. Jag vill testa en algoritm ex, selectionssort, optimera koden, testa igen för att se om jag får bättre resultat osv. Någon som kan hjälpa mig att komma igång med att skriva ett testprogram?

Hälsningar
Johnny

Man kan matematiskt få fram tidskomplexiteten. Därvid bör det gå alldeles utmärkt att göra ett program som analyserar algoritmens kod och på det sättet får fram värdena. Fast det är nog inte så trivialt ;)

Är det i runtime så är det väl bara att ta tiden från att algoritmen exekverar till att den terminerar.

Du vill mäta hur lång tid det tar? Kolla in clock-funktionen, så att du inte mäter tid som processen inte rullar:
http://www.cplusplus.com/ref/ctime/clock.html

I bash finns det även en fiffig funktion som mäter hur lång tid det tar att köra ett visst program, time. I stället för att köra programmet med t.ex. ./thehack arg1 arg2 skriver du i stället time ./thehack arg1 arg2.

Hej PeW,

Jag ska tillägga at jag är ingen van C-programmerare. Hur menar du att jag ska få fram runtime?

/Johnny

Proton skrev:

Hej PeW,

Jag ska tillägga at jag är ingen van C-programmerare. Hur menar du att jag ska få fram runtime?

/Johnny

Se spangos svar :)

Men ifall det är något du ska sen exempelvis skriva en rapport om, så bör du nog även härleda dina resultat matematiskt. Sök på "ordo time complexity" så kan du kanske hitta en del matnyttigt i ämnet.

Tack för ert svar allihopa, jag ska kolla upp dem nu. Men det verkar ju lovande! =)

/Johnny

Hej på er!

Nu har jag gjort följande vilket borde fungera som jag tänkt..

int main ()
{
  float start, stop;
  start = clock();

  //sorteringsalgoritmen
  
  stop = clock();
  printf("\nSorteringen tog %06.03f tidsenheter.\n",(float)((float)(stop-start)/CLOCKS_PER_SEC));
  return 0;
}

Borde fungera finfint, testresultaten verkar stämma, men har jag missat något?

/Johnny

Problemet är väl att du inte får det särskilt exakt eftersom processchemaläggaren i operativsystemet troligen byter till nån annan process någon eller flera ggr nånstans mellan start och stop. Ju fler andra processer du har igång desto större o-exakthet. För att köra det någorlunda oantastat behöver du låsa den process som exekvererar "testet" mellan start och stop. Ett annat sätt kan vara att ge den exekverande processen max prioritet för att komma så nära ett exakt svar som möjligt.

Om det inte är väldigt hemliga algoritmer kan du väl skriva dem här?

För tillfället läser jag "Algoritmer och datastrukturer" där vi till stor del räknar på olika algoritmers tidskomplexitet.
Det vore fin övning om inte annat :)

Hej,

Nä det är inte hemliga, jag går en kurs där man ska optimera färdigskrivna sorteringsalgortimer i C, dvs vi har fått kod men ska hitta möjligheter att optimera den. Vi har fått algoritmerna bubble-sort och selectionssort. Vill du ha den icke optimerade koden?

Hälsningar
Johnny

PeW skrev:

Problemet är väl att du inte får det särskilt exakt eftersom processchemaläggaren i operativsystemet troligen byter till nån annan process någon eller flera ggr nånstans mellan start och stop. Ju fler andra processer du har igång desto större o-exakthet. För att köra det någorlunda oantastat behöver du låsa den process som exekvererar "testet" mellan start och stop. Ett annat sätt kan vara att ge den exekverande processen max prioritet för att komma så nära ett exakt svar som möjligt.

Har du tid att förklara hur antingen eller den andra metoden kan genomföras?

Hälsningar
Johnny

Den andra är enkel och förmodligen tillräcklig, (förutsätter att du kör windows):

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

int main ()
{
  float start, stop;
  SetPriorityClass( GetCurrentProcess(), REALTIME_PRIORITY_CLASS );
  SetThreadPriority( GetCurrentThread(), THREAD_PRIORITY_TIME_CRITICAL );
  start = clock();
  //sorteringsalgoritmen
  
  stop = clock();
  printf("\nSorteringen tog %06.03f tidsenheter.\n",(float)((float)(stop-start)/CLOCKS_PER_SEC));
  return 0;
}

PeW skrev:

Den andra är enkel och förmodligen tillräcklig, (förutsätter att du kör windows):

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

int main ()
{
  float start, stop;
  SetPriorityClass( GetCurrentProcess(), REALTIME_PRIORITY_CLASS );
  SetThreadPriority( GetCurrentThread(), THREAD_PRIORITY_TIME_CRITICAL );
  start = clock();
  //sorteringsalgoritmen
  
  stop = clock();
  printf("\nSorteringen tog %06.03f tidsenheter.\n",(float)((float)(stop-start)/CLOCKS_PER_SEC));
  return 0;
}

Grymt! Tack! Jag har mycket att lära märker jag!

Hälsningar
Johnny

PeW skrev:

Problemet är väl att du inte får det särskilt exakt eftersom processchemaläggaren i operativsystemet troligen byter till nån annan process någon eller flera ggr nånstans mellan start och stop. Ju fler andra processer du har igång desto större o-exakthet.

Nope, faktiskt inte :)
clock() ska enbart mäta (eller snarare approximera) den tid som faktiskt använts av processorn. http://www.opengroup.org/onlinepubs/007908799/xsh/clock.html

spango skrev:

Nope, faktiskt inte
clock() ska enbart mäta (eller snarare approximera) den tid som faktiskt använts av processorn.

Jaaaaha, där ser man, jag kolla på sidan och det står som du säger:

The clock() function returns the implementation's best approximation to the processor time used by the process since the beginning of an implementation-dependent time related only to the process invocation.

Tack för klargörandet!

Hälsningar
Johnny

spango skrev:

PeW skrev:

Problemet är väl att du inte får det särskilt exakt eftersom processchemaläggaren i operativsystemet troligen byter till nån annan process någon eller flera ggr nånstans mellan start och stop. Ju fler andra processer du har igång desto större o-exakthet.

Nope, faktiskt inte :)
clock() ska enbart mäta (eller snarare approximera) den tid som faktiskt använts av processorn. http://www.opengroup.org/onlinepubs/007908799/xsh/clock.html

Jovisst. Men cpu:n delas ju av flera andra processer som schemaläggaren genom att avbryta tilldelar körtid, eller hur? Även om det är en approximation så är den inte särskilt exakt. Med följande kod blir det (när jag testar den) relativt stora avvikelser beroende på hur många andra processer som är igång samtidigt:

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

int main(int argc, char **argv)
{
    float start, stop;
    int i;

	start = clock();

    //jobbig loop
    for(i=0;i<1000000000;i++);

    stop = clock();
	

  printf("\nSorteringen tog %06.03f tidsenheter.\n",(float)((float)(stop-start)/CLOCKS_PER_SEC));
  return 0;
	return 0;
}

Men om man höjer prioriteten på tråden som föreslagits blir resultatet (ivf för mig på en gammal 2.4GHz XP-burk), betydligt jämnare.

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

int main(int argc, char **argv)
{
    float start, stop;
	int i;
	
     SetPriorityClass( GetCurrentProcess(), REALTIME_PRIORITY_CLASS );
    SetThreadPriority( GetCurrentThread(), THREAD_PRIORITY_TIME_CRITICAL );

	start = clock();
    //samma jobbiga loop
    for(i=0;i<1000000000;i++);

    stop = clock();
	

  printf("\nSorteringen tog %06.03f tidsenheter.\n",(float)((float)(stop-start)/CLOCKS_PER_SEC));
  return 0;
	return 0;
}

Allt hänger väl på hur exakt man vill att det ska vara. Men om man som det verkar, är ute efter att göra optimeringar i kodsnuttar borde man nog sträva efter ett så tillförlitligt resultat som möjligt? Talar vi millisekunder eller mikrosekunder?

Ska man vara riktigt äckligt exakt behöver man stänga av alla avbrott för att låsa processen och mäta exakt hur många klocktick processorn använt. Vilket i sin tur ger vid handen att det är nog smartare att optimera "matematiskt" genom vanlig algoritmanalys istället :)