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?

Quote:

---

Originally Posted by Tool

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

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?

Quote:

---

Originally Posted by Tool

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.

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;
}

---

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.

Loop what exactly? In main? Can u show a bit of code?

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;

---

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>

---

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.

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?

Quote:

---

Originally Posted by Tool

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.

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.

Of course. I answered his question too literally (he wanted the measure the time the call with those parameters would take).

Quote:

---

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.

Quote:

---

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;
}

---

Quote:

---

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.