Thread: measure run time?

  1. #1
    Registered User
    Join Date
    Jul 2009
    Location
    Croatia
    Posts
    272

    measure run time?

    Our binary search makes two tests inside the loop, when one would suffice (at the price of more tests outside). Write a version with only one test inside the loop and measure the difference in run-time.

    Function before:
    Code:
    int binsearch(int x, int v[], int n) {
        int low, mid, high;
        
        low = 0;
        high = n - 1;
        while ( low <= high ) {
            mid = (low+high) / 2;
            if ( x < v[mid] )
                high = mid - 1;
            else if ( x > v[mid] )
                low = mid + 1;
            else
                return mid;
        }
        return -1;
    }


    Function after:
    Code:
    int binsearch(int x, int v[], int n)
    {
        int low, high, mid;
        
        low = 0;
        high = n - 1;
        while(low<=high)
        {
           
           mid = (low+high)/2;
           
           if(x > v[mid])
           low = mid + 1;
           
           else high = mid - 1;
           
        }
        return (x == v[mid]) ? mid : -1;
    }

    What does measuring run time means and how am i supposed to measure it?

    K&R didnt cover any clock() functions up to this point, so is there any alternative?

  2. #2
    Learning C. JOZZY& Wakko's Avatar
    Join Date
    Nov 2009
    Posts
    59
    Quote Originally Posted by Tool View Post
    What does measuring run time means and how am i supposed to measure it?

    K&R didnt cover any clock() functions up to this point, so is there any alternative?
    Far as I understand it "Run-Time" is the period in which the program is executed.

    Run time (computing) - Wikipedia, the free encyclopedia

    If you ask me to measure the different "Run-Times" I would presume they mean the difference in time of execution of the program.

    I did not read them (yet) but I guess these 2 links could give you some more insight and info.

    Using clock() to measure run time - C / C++ answers
    Runtime Memory Measurement - eLinux.org

  3. #3
    Registered User
    Join Date
    Jul 2009
    Location
    Croatia
    Posts
    272
    I tried using the clock functions described in Using clock() to measure run time - C / C++ answers. But the problem is it always lists 0.0000000. And if i add a statement like while(++a < 3000000) before it ends it will produce diffrent values all the time.

    Any way to go around this?

  4. #4
    DESTINY BEN10's Avatar
    Join Date
    Jul 2008
    Location
    in front of my computer
    Posts
    804
    Quote Originally Posted by Tool View Post
    I tried using the clock functions described in Using clock() to measure run time - C / C++ answers. But the problem is it always lists 0.0000000. And if i add a statement like while(++a < 3000000) before it ends it will produce diffrent values all the time.

    Any way to go around this?
    The code is getting executed so fast that the time is always coming out to be 0.000000.
    HOPE YOU UNDERSTAND.......

    By associating with wise people you will become wise yourself
    It's fine to celebrate success but it is more important to heed the lessons of failure
    We've got to put a lot of money into changing behavior


    PC specifications- 512MB RAM, Windows XP sp3, 2.79 GHz pentium D.
    IDE- Microsoft Visual Studio 2008 Express Edition

  5. #5
    Registered User
    Join Date
    Jul 2009
    Location
    Croatia
    Posts
    272
    So no way i can ever measure time diffrence between them? Not on my PC anyway.

    This is the code im using:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    #include <time.h>
    
    int binsearch(int x, int v[], int n)
    {
        int low, high, mid;
        
        low = 0;
        high = n - 1;
        while(low<=high)
        {
           
           mid = (low+high)/2;
           
           if(x > v[mid])
           low = mid + 1;
           
           else high = mid - 1;
           
        }
        return (x == v[low]) ? mid : -1;
    }
    
    int main(int argc, char *argv[])
    {
         clock_t start, stop;
         double t = 0.0;
         
         assert((start = clock())!=-1);
         
         
         int array[7] = { 1, 3, 5, 7, 9, 11, 13 };
         printf("%d", binsearch(13, array, 6));
         
         stop = clock();
         t = (double) (stop-start)/CLOCKS_PER_SEC;
         printf("Run time: %f\n", t);
         
         
      system("PAUSE");	
      return 0;
    }

  6. #6
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    Sorting 7 numbers won't give you any measurable time.

    One common way to do it is to loop it, say, a few million times, and measure the total run time, then divide by a few million. Make sure the compiler doesn't optimize the loop away, though.

  7. #7
    Registered User
    Join Date
    Jul 2009
    Location
    Croatia
    Posts
    272
    Loop what exactly? In main? Can u show a bit of code?

  8. #8
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    Code:
    start = clock();
    int i;
    for (i = 0; i < 100000; ++i) {
         binsearch(13, array, 6);
    }
    stop = clock();
    t = (double) (stop-start)/CLOCKS_PER_SEC/100000;

  9. #9
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    You can approach it in two ways. One is use the OS tools to get the runtime stats or plug in calls to the time() functions to do it for you. On *nix systems, invoke the executable thro' timex, as in
    Code:
    timex <exe_name>

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    In that second function, "else high = mid - 1;" isn't technically correct. It should be just "else high = mid;" because x may still equal v[mid].

    cyberfish:
    I would not test the speed of these functions by repeatedly searching for the same value. For example if you were searching for 7 then the first function would clearly win, but when searching for anything other than 3, 7, 11, or any item not present in the array at all, the second one will win.
    I would speed test it on random numbers equally distributed in the range 0-14. Then you'll know which is faster overall.
    You're also passing in the wrong value for n. It should be sizeof(array) i.e. Seven, not Six, so it wont find 13 anyway because of this, in the code you posted.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  11. #11
    Registered User
    Join Date
    Jul 2009
    Location
    Croatia
    Posts
    272
    What about this code. Can anyone explain the bolded statements:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <ctype.h>
    #include <time.h>
    #define MAX_ELEMENT 20000
    
    int binsearch(int x, int v[], int n) {
        int low, mid, high;
        
        low = 0;
        high = n - 1;
        while ( low <= high ) {
            mid = (low+high) / 2;
            if ( x < v[mid] )
                high = mid - 1;
            else if ( x > v[mid] )
                low = mid + 1;
            else
                return mid;
        }
        return -1;
    }
    
    int binsearch2(int x, int v[], int n) {
        int low, high, mid;
        
        low = 0;
        high = n - 1;
        mid = (low+high) / 2;
        while ( low <= high && x != v[mid] ) {
            if ( x < v[mid] )
                high = mid - 1;
            else
                low = mid + 1;
            mid = (low+high) / 2;
        }
        if ( x == v[mid] )
            return mid;
        else
            return -1;
    }
    
    
    int main(int argc, char *argv[])
    { 
         
         int testdata[MAX_ELEMENT];
         
         clock_t time_taken;
         
         int i, index;
         for ( i = 0; i < MAX_ELEMENT; ++i )
            testdata[i] = i;
            
         int n = 2500;
         
         /* 100 000 iterations for binsearch */
         for ( i = 0, time_taken = clock();  i < 100000; ++i ) 
         {
            index = binsearch(n, testdata, MAX_ELEMENT);
         }
         
         time_taken = clock() - time_taken;
         
         if ( index < 0 )
            printf("Element %d not found.\n", n);
         else
            printf("Element %d found at index %d.\n", n, index);
        
        
         printf("binsearch() took %lu clocks (%lu seconds)\n",
               (unsigned long) time_taken,
               (unsigned long) time_taken / CLOCKS_PER_SEC);
         
         
         /* 100 000 iterations for binsearch2 */
         
         for ( i = 0; i < 100000; ++i ) 
         {
            index = binsearch(n, testdata, MAX_ELEMENT);
         }
        
         time_taken = clock() - time_taken;
         if ( index < 0 )
            printf("Element %d not found.\n", n);
         else
            printf("Element %d found at index %d.\n", n, index);
        
        
         printf("binsearch() took %lu clocks (%lu seconds)\n",
               (unsigned long) time_taken,
               (unsigned long) time_taken / CLOCKS_PER_SEC);     
         
         
         
      system("PAUSE");	
      return 0;
    }
    How exactly does clock_t works? What sort of a variable is that?

    What is stored into time_taken exactly?

    How does clock() function works? It counds processor ticks after each statements?
    Last edited by Tool; 12-18-2009 at 04:08 PM.

  12. #12
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by Tool View Post
    What about this code. Can anyone explain the bolded statements:

    clock() returns the number of cpu ticks that have occurred since the start of your program.

    clock_t start, stop;

    start = clock(); //our starting point

    ///some code in here, we want to time

    stop = clock(); //our stopping point

    elapsed_time = (stop - start) / CLK_TCK //or CLOCKS_PER_SEC, or whatever the name of your compilers macro is which gives the number of clock sweeps per sec.

    time_taken = clock() - time_taken;

    is just another way of measuring elapsed time . It saves a line of code, but loses a small bit of clarity, in doing so. Nothing special at all about it.

    clock_t is an unsigned long on my system.

    It's silly to keep looking for a few numbers, over and over. What you want is a large (huge!) number of values, which are all unique, and then time your search through that large search space, several times. Each time, you'll search for a different number. Numerical data are preferred, otherwise the string handling and comparing uses up a lot of cpu cycles, lessening the comparison of just the searches, themselves.
    Last edited by Adak; 12-18-2009 at 07:30 PM.

  13. #13
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    You didn't listen. I told you that "high = mid - 1;" should just be "high = mid;" in binsearch2 (it's correct as-is in the first function). Are you assuming that it doesn't matter? Would you like to know how your code actually does not work because of this?

    What on earth have you put this part in the loop for:
    Code:
     && x != v[mid]
    Do you not see how that means you're again doing two tests inside the loop. You were specifically asked to reduce it to one test in the loop, so why have you gone backwards?

    You also didn't read what I posted for cyberfish. You're searching for the same number (2500) one-hundred-thousand times, for both loops! You should perform searches for all the different items that are in the array, not just one. Do you not understand how what you have would give you a biased result?
    Did you not understand how in the previous example searching for 7 would make one method appear faster than the other when typically it's actually the other way around?

    Of course there's no point in timing something that doesn't even work correctly yet.
    Last edited by iMalc; 12-18-2009 at 08:10 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  14. #14
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    Of course. I answered his question too literally (he wanted the measure the time the call with those parameters would take).

  15. #15
    Registered User
    Join Date
    Jul 2009
    Location
    Croatia
    Posts
    272
    You didn't listen. I told you that "high = mid - 1;" should just be "high = mid;" in binsearch2 (it's correct as-is in the first function). Are you assuming that it doesn't matter? Would you like to know how your code actually does not work because of this?

    What on earth have you put this part in the loop for:
    Yes i know, this wasnt my code, i took it from a site with solutions to this exercise.


    You should perform searches for all the different items that are in the array, not just one.
    Is this what u mean:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #define MAX_SIZE 5000
    #define ITERATIONS 10000
    
    int binsearch(int x, int v[], int n) 
    {
        int low = 0;
        int high = n - 1; 
        int mid;
        
        while(low<=high)
        {
           mid = (low + high)/2;
           
           if(x > v[mid])
           low = mid + 1;
           
           else if(x < v[mid])
           high = mid - 1;
           
           else return mid; /* else if (x == v [mid]) return mid; */
        }
        return -1;
    }
    
    int binsearch2(int x, int v[], int n)
    {
      int low, high, mid;
    
      low = 0;
      high = n;
      while (low < high) {
        mid = (low + high) / 2;
        if (v[mid] < x)
          low = mid + 1;
        else
          high = mid;
      }
      if (high == n || v[high] != x)
        return -1;
      else
        return high;
    }
    
    int main(int argc, char *argv[])
    { 
        
        int i;
        int testdata[MAX_SIZE];
        for ( i = 0; i < MAX_SIZE; ++i )
            testdata[i] = i;
        
        printf("%d\n", binsearch(3, testdata, MAX_SIZE));
        
        int n = 0, x;
        
        clock_t start, end;
        start = clock();
        for ( i = 0;  i < ITERATIONS; ++i ) 
        {
            for(x = 0; x < MAX_SIZE; x++)
            {
                binsearch(x, testdata, MAX_SIZE);
            }
        }
        end = clock();
        
        printf("\nTime taken in seconds: %.30f\n", ((double)(end - start))/CLOCKS_PER_SEC);
         
         
         
        getchar();	
        return 0;
    }
    Do you not understand how what you have would give you a biased result?
    Did you not understand how in the previous example searching for 7 would make one method appear faster than the other when typically it's actually the other way around?
    Overall, binsearch2 is faster.
    Last edited by Tool; 12-19-2009 at 02:48 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. time measure (net and gross) with pthreads under linux
    By mynickmynick in forum Linux Programming
    Replies: 12
    Last Post: 12-01-2008, 07:39 AM
  2. Measure time
    By anirban in forum C Programming
    Replies: 5
    Last Post: 06-12-2008, 03:53 AM
  3. Read and set\change system time
    By Hexxx in forum C++ Programming
    Replies: 9
    Last Post: 01-02-2006, 07:11 AM
  4. I apologize. Good bye.
    By doubleanti in forum A Brief History of Cprogramming.com
    Replies: 14
    Last Post: 05-03-2002, 06:51 PM
  5. time class
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 12-11-2001, 10:12 PM