timewise: 1 test in loop = 2 tests in loop? surely not.

Dev Shed Forums Sponsor:

February 2nd, 2003, 09:59 AM

balance

Join Date: Dec 2002

Posts: 296

Time spent in forums: < 1 sec
Reputation Power: 6

timewise: 1 test in loop = 2 tests in loop? surely not.

one of the exercises from the k&r book asks you to redo this function with only one test inside the while loop rather than two (at the price of more tests outside):

Code:

/* binsearch: find x in v[0] <= v[1] <= .... <= v[n-1] */
int binsearch(int x, int v[], int n)
{
	int high, low, 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 */
}

so i did this:

Code:

/* binsearch: find x in v[0] <= v[1] <= .... <= v[n-1] */
int binsearch(int x, int v[], int n)
{
	int high, low, mid;
	
	low=0;
	high=n-1;
	while(low<=high) {
		mid=(low+high) /2;
		if(x<v[mid])
			high=mid-1;
		else 
			low=mid+1;
	}
	
	if(x==v[mid])					/* match found */
		return mid;
	else if(x==v[mid-1])				/* ditto */
		return mid-1;
	else
		return -1;				/* no match found */
}

this works completely fine - returns exactly the same results as the original and i've only got one test inside the loop, so that's cool. but time-wise, it's almost identicle to the first. the reasoning for the question is obviously to get you to notice the time difference of having one or two tests within a loop, as they ask you to time both versions and compare the results. but it's actually shown me that there's no real difference at all.

is my version of the function not done so well? is there a better way to do that (bearing in mind this q is only on chapter 3 (out of 8), so it shouldn't be a too advanced solution), or does having two tests as opposed to one test in a loop not make much difference? is that the point?

to time/test it i simply called that function 6000000 times. then i do the same to the other version of the function using exactly the same settings/parameters.

here's three sample timings of each version of the function:

original function (2 tests in loop): 397 and 405 and 398
my version (1 test in loop): 410 and 414 and 421

so my 'faster' one actually seems to take a bit longer!

i know timing isn't an exact science, but if you've got a significantly faster piece of code, you can tell. and i can tell that my version is not significantly faster than the original.

February 4th, 2003, 06:19 AM

tony825

Contributing User

Join Date: Jan 2003

Location: Greece

Posts: 63

Time spent in forums: < 1 sec
Reputation Power: 6

since noone has replied, im gonna give a try!(...)

Quote:

else if(x==v[mid-1]) /* ditto */
return mid-1;

im not so sure if this check is needed.

so when 'trying' to return -1 you have a "unneeded" check 6000000 times. thats a lot of time.

the rest is ok.

February 4th, 2003, 12:13 PM

balance

Join Date: Dec 2002

Posts: 296

Time spent in forums: < 1 sec
Reputation Power: 6

Quote:

since noone has replied, im gonna give a try!(...)

thanks v. much

Quote:

im not so sure if this check is needed.

it doesn't always work (depending which number i'm searching for) without that check. sometimes, when the loop is exited, the found number is at position mid-1 and other times with it at just mid, depending on where the number is positioned in the array - if it happens to be above or below the midpoint, i think.

but that check is outside the while loop - so shouldn't make too much difference as the tests outside the while loop only get run once per function call.

Quote:

the rest is ok.

yeah but what's puzzling me is the fact that i've reduced the number of tests inside the while loop, therefore reducing the total number of tests per function call by quite a few, but it hasn't made it any quicker.

and reducing the test in the loop in order to make it quicker seemed to be the motivation behind the question.

i know there's more tests outside the while loop than the original, but they only get run once for each time the function gets called where-as the tests inside the while loop get called more times (depending on how large the array being searched is)

one thing i didn't mention is how many elements there are in the array being searched, the v[] array. there's 1900 elements in that array. with that many elements in the array, using the particular number i'm searching for, the while loop gets run 11 times per function call - with the new version that is.

i can't see why the new version takes the same time (or is even slightly slower) as the original that has 2 tests in the while loop rather than one. you would have thought that reducing the number of tests would speed it up, but there you go - it hasn't. it doesn't matter - i'm being pretty pedantic - it's just something that's puzzling me.

February 6th, 2003, 10:42 AM

3dfxMM

Contributing User

Join Date: Aug 2002

Posts: 266

Time spent in forums: 3 Days 21 h 4 m 53 sec
Reputation Power: 13

You have reduced the number of tests that exist inside the loop, but depending on the data you may not have reduced by a significant amount the number of tests that are executed.

February 6th, 2003, 12:39 PM

balance

Join Date: Dec 2002

Posts: 296

Time spent in forums: < 1 sec
Reputation Power: 6

so it's a case of how many tests are actually made in the actual run, rather than simply how many tests are contained within the code. yup, that makes complete sense, and seems very obvious now. thanks

Thread Tools	Search this Thread
Email this Page	Search this Thread: Advanced Search
Display Modes	Rate This Thread
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode	Rate This Thread: