Sentinal Value Optimization

**curlious** · 11-03-2003

This is an excerpt from Code Complete by Steve McConnell. Chapter 29 Code Tuning Techniques pg 702. The example confuses me and I do not understand how it works. The example is a search routine that checks both wether a value is found and whether it it has run out of values. In this example I do not understand what determines if the value is found.

Code:

/* set sentinel value, perserving the original value */
InitialValue = Item[ ElementCount ];
Item[ ElementCount ] = TestValue;

i=0;
while ( Item[ i ] != TestValue)
    {
    i++;
    }

/* restore the value displaced by the sentinel */
Item[ ElementCount ] = InitialValue;

If the test value is found in the Item array the loop exits but no boolean is set to indicate success. Perhaps the code is incomplete or missing somthing I am a bit confused.

**Omnius** · 11-03-2003

If I understand correctly, the value you're testing for will always be found, as it has been placed in the array at Item[ElementCount], which is at the end of the array (beyond the range of values you're searching).

If the value you're testing for exists prior to this in the array, then it will be found at a location other than Item[ElementCount]. The way to determine whether the array contained the value you're searching for is to check the value of i when the search has completed. If i equals ElementCount, the value was not in the array. If i is not equal to ElementCount, the value is in the array at location Item[i].

**LuckY** · 11-03-2003

Code:

/* (it is odd to me that he is using ElementCount and not ElementCount-1 as ElementCount sounds like it would be one after the last element of the array) */
InitialValue = Item[ ElementCount ];// remember the last item in the array
Item[ ElementCount ] = TestValue;// set the last item to TestValue

i=0;// start the index at the beginning of the array
while ( Item[ i ] != TestValue)// determine if this item of the array is not equal to TestValue
    {// if it is not equal we enter the loop, if it is equal the loop terminates
    i++;// increment the index
    }

Item[ ElementCount ] = InitialValue;// reset the last element to what it was before we changed it

Is this the code in its entirety? To be quite honest it doesn't make complete sense; I mean I don't understand the point to the snippet. It is not determining anything nor changing anything. What did the author say he was demonstrating here?

**Omnius** · 11-03-2003

The explanation is provided by the author in this sentence:

"If the first element you find is the one you stuck at the end, you know that the value you're looking for isn't really there."

**Sebastiani** · 11-03-2003

Another common approach is something like this:

Code:

template <class type> 
type * find(type value, type array[], int length)
{
    for(int i = 0; i < length; ++i)
       if(array[i] == value)
        return &array[i];
  
 return NULL;
}

**curlious** · 11-03-2003

Thanks for the input. I am almost finished reading the book but fully utilizing the information may take months. Today is my second day of reading and I am nearly finished no skimming and with comprehension, but utilization and memorization will take a while. It is an excellent book and I appreciate your comments.

ps I don't think memorizing everything he writes would help your programming until you fully utilized what you learn, but incorperating his suggestions (incrementaly) as your programming skills increase (and responsibility) seems to be the way to go. (at least for me).

lol what a horrible sentence

Thread: Sentinal Value Optimization

Thread Tools

Search Thread

Display

Sentinal Value Optimization

Similar Threads

Turn Off Optimization?

need reading material for c++ database optimization

optimization flags

Optimization settings

Optimization stuff