Sentinal Value Optimization

This is a discussion on Sentinal Value Optimization within the C++ Programming forums, part of the General Programming Boards category; This is an excerpt from Code Complete by Steve McConnell. Chapter 29 Code Tuning Techniques pg 702. The example confuses ...

  1. #1
    Registered User
    Join Date
    Jul 2003
    Posts
    450

    Sentinal Value Optimization

    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.

  2. #2
    Registered User
    Join Date
    Sep 2003
    Posts
    135
    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].

  3. #3
    Magically delicious LuckY's Avatar
    Join Date
    Oct 2001
    Posts
    856
    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?

  4. #4
    Registered User
    Join Date
    Sep 2003
    Posts
    135
    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."

  5. #5
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,600
    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;
    }
    Code:
    if( numeric_limits< byte >::digits != bits_per_byte )
        error( "program requires bits_per_byte-bit bytes" );
    24bbs.cpp

  6. #6
    Registered User
    Join Date
    Jul 2003
    Posts
    450
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Turn Off Optimization?
    By danlee58 in forum C Programming
    Replies: 6
    Last Post: 12-10-2008, 02:52 AM
  2. need reading material for c++ database optimization
    By elninio in forum C++ Programming
    Replies: 0
    Last Post: 07-24-2008, 11:32 PM
  3. optimization flags
    By markucd in forum C++ Programming
    Replies: 4
    Last Post: 06-30-2006, 09:08 AM
  4. Optimization settings
    By Roaring_Tiger in forum C Programming
    Replies: 4
    Last Post: 02-23-2005, 01:53 AM
  5. Optimization stuff
    By jverkoey in forum C++ Programming
    Replies: 2
    Last Post: 05-26-2004, 06:02 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21