#1
  1. No Profile Picture
    .
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2002
    Posts
    296
    Rep Power
    13

    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.
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2003
    Location
    Greece
    Posts
    63
    Rep Power
    12
    since noone has replied, im gonna give a try!(...) :)

    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.
  4. #3
  5. No Profile Picture
    .
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2002
    Posts
    296
    Rep Power
    13
    since noone has replied, im gonna give a try!(...)
    :) thanks v. much

    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.

    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.
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2002
    Posts
    272
    Rep Power
    19
    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.
  8. #5
  9. No Profile Picture
    .
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2002
    Posts
    296
    Rep Power
    13
    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

IMN logo majestic logo threadwatch logo seochat tools logo