Okay so here is the starter code utilising the clock() function:
Code:#include <stdio.h> #include <time.h> /* binary search algorithm */ int binsearch(int x, int v[], int n); int main() { int myarray[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; clock_t start = clock(); /* start clock */ printf("%d\n", binsearch(3, myarray, 10)); clock_t finish = clock(); /* stop clock */ printf("It took %d seconds to execute the binary search.\n", (finish - start) / CLOCKS_PER_SEC); printf("It took %d clock cycles per second to execute the binary search.\n", (finish - start)); return 0; } 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]) high = mid + 1; else if (x > v[mid]) low = mid + 1; else /* found match */ return mid; } return -1; /* No Match */ }
I'm having two problems though:
1) I get the following error in relation to printing of the time:
2) The binary search hangs with inputs of 4 and 6 for the key value 'x'. Strange considering the code has not yet been modified from the book :?Code:"format '%d' expects type 'int', but argument 2 has type 'clock_t"
Any ideas?
Thanks as always
BIOS
Last edited by BIOS; 09-13-2011 at 10:36 AM.
printf doesn't have a format specifier for clock_t variables. You either have to cast, or convert to a struct tm and use strftime, then printf that result.
Books are not infallible. Look at the following two lines:2) The binary search hangs with inputs of 4 and 6 for the key value 'x'. Strange considering the code has not yet been modified from the book :?
Why are they both the same? high should be adjusted to mid - 1, moving it below the previous value of mid, which was too big.Code:high = mid + 1; low = mid + 1;
Last edited by anduril462; 09-13-2011 at 10:50 AM.
Yeah but it's dirt cheep. A loop is essentially two instructions: increment and branch. Both are cheep for a loop, particularly a large one. Compare that to a function call which involves pushing all the arguments on the stack, adjusting the stack pointer twice, and two jumps.
It is too clear and so it is hard to see.
A dunce once searched for fire with a lighted lantern.
Had he known what fire was,
He could have cooked his rice much sooner.
There's two distinct parts to calling printf with extra args. The first is what you pass in. You passed in a clock_t. It's probably just an int under the hood (but you don't know unless you rip your implementation apart), nor should you care. You told it to pass in a clock_t, so the compiler generated code to pass a clock_t to printf. Now, the guts of printf don't know what you passed it, they just have to trust your extra params match the % specifiers in the format string. You said %d, so printf assumes an int is next. But if it tries to take 8 bytes for that int, and you only gave it 4 for a clock_t, you'll end up with garbage. Like I said, in this case, an int and a clock_t are probably the same size, so you're getting away with it, but technically it's wrong, and might not work everywhere.
Last edited by anduril462; 09-13-2011 at 11:25 AM.
You can also time the entire process from the shell with time, for example:
$ time ./a.out
And on OS X you have mach_absolute_time(), and of course Instruments which has a time profiler among other things.
Last edited by Subsonics; 09-13-2011 at 11:27 AM.
Okay cool. So I just got lucky in this case :P Will make sure to read up on the library Thanks
Should the number of clock cycles per second change even if the input is the same between executions?
What CPU do you have? The core i archtecture CPUs from intel can vary the clock based on work load. But runtime will vary from time to time, depending on what else is going on, if the process is still in memory and/or cache. Absolute runtime also depends on what machine you are running on, it's probably more interesting to look at relative time, what it is that takes time and so on.
I've got core i5's. Could you elaborate a bit more on relative time?
My point was that it's probably more interesting to look for what it is that takes time, and wether a change to the code gives an improved performance relative to the old time.
Gotcha. Thanks for the pointers
Relative time may be more precise for measuring improvements, but it won't provide the benchmark to tell you if the code needs improvement in the first place.
It is too clear and so it is hard to see.
A dunce once searched for fire with a lighted lantern.
Had he known what fire was,
He could have cooked his rice much sooner.
Wouldn't the indication of that be that you experience some kind of problem? Unless you are talking about some realtime process with a deadline. Otherwise it seems like a moving target.