Sentinel value

Not to be confused with sentinel node.

In computer programming, a sentinel value (also referred to as a flag value, trip value, rogue value, signal value, or dummy data)[1] is a special value in the context of an algorithm which uses its presence as a condition of termination, typically in a loop or recursive algorithm.

The sentinel value is a form of in-band data that makes it possible to detect the end of the data when no out-of-band data (such as an explicit size indication) is provided. The value should be selected in such a way that it is guaranteed to be distinct from all legal data values, since otherwise the presence of such values would prematurely signal the end of the data (the semipredicate problem). A sentinel value is sometimes known as an "Elephant in Cairo", due to a joke where this is used as a physical sentinel. In safe languages, most uses of sentinel values could be replaced with option types, which enforce explicit handling of the exceptional case.

Examples

Some examples of common sentinel values and their uses:

Variants

A related practice, used in slightly different circumstances, is to place some specific value at the end of the data, in order to avoid the need for an explicit test for termination in some processing loop, because the value will trigger termination by the tests already present for other reasons. Unlike the above uses, this is not how the data is naturally stored or processed, but is instead an optimization, compared to the straightforward algorithm that checks for termination. This is typically used in searching.[2][3]

For instance, when searching for a particular value in an unsorted list, every element will be compared against this value, with the loop terminating when equality is found; however to deal with the case that the value should be absent, one must also test after each step for having completed the search unsuccessfully. By appending the value searched for to the end of the list, an unsuccessful search is no longer possible, and no explicit termination test is required in the inner loop; afterwards one must still decide whether a true match was found, but this test needs to be performed only once rather than at each iteration.[4] Knuth calls the value so placed at the end of the data a dummy value rather than a sentinel.

Examples

Array

For example, if searching for a value in an array in C, a straightforward implementation is as follows; note the use of a negative number (invalid index) to solve the semipredicate problem of returning "no result":

// Returns index of value, -1 for no result
int find(int* a, int l, int v)
{
  int i;
  for (i = 0; i < l; i++)
    if (a[i] == v)
      return i;
  return -1; // -1 means "no result"
}

However, this does two tests at each iteration of the loop: whether the value has been found, and then whether the end of the array has been reached. This latter test is what is avoided by using a sentinel value. Assuming the array can be extended by one element (without memory allocation or cleanup; this is more realistic for a linked list, as below), this can be rewritten as:

int find(int* a, int l, int v)
{
  int i;
  // add sentinel item:
  a[l] = v; // prepare it with sentinel value
  for (i = 0; ; i++)
    if (a[i] == v) {
      if (i != l) // real result
        return i;
      // was sentinel value, not real result:
      return -1;
    }
}

In this case each loop iteration only has a single test (for the value), and is guaranteed to terminate, due to the sentinel value. On termination, there is a single check if the sentinel value has been hit, which replaces a test for each iteration.

In this case the loop can more simply be written as a while loop:

int find(int* a, int l, int v)
{
  int i;
  // add sentinel item:
  a[l] = v; // prepare it with sentinel value
  i = 0;
  while (a[i] != v)
    i++;
  if (i != l) // real result
    return i;
  // was sentinel value, not real result:
  return -1;
}

Linked list

For searching in a linked list, the following is the straightforward algorithm, starting at a given head node; note the use of NULL to solve the semipredicate problem:

typedef struct Node{
  Node* next;
  int value;
} Node;

// Returns pointer to node with value, NULL for no result
Node* find(Node* n, int v)
{
  if (n->value == v)
    return n;

  while(n->next!=NULL) {
    n = n->next;
    if (n->value == v)
      return n;
  }
  return NULL;
}

However, if the last node is known, the inner loop can be optimized by firstly adding (and lastly removing) a sentinel node after the last node:

typedef struct List {
  Node* firstElement;
  Node* lastElement;
} List;

Node* find(List* l, int v)
{
  Node *n, sentinelNode;
  // Add sentinel node:
  l->lastElement->next = &sentinelNode;
  sentinelNode.value = v; // prepare sentinel node with sentinel value

  // main loop
  n = l->firstElement;
  while (n->value != v)
    n = n->next;
  
  // termination
  l->lastElement->next = NULL; // clean up
  if (n != &sentinelNode) // real result
    return n;
  // was sentinel node, not real result:
  return NULL;
}

Note that this relies on memory addresses providing a unique identity to detect the sentinel node; this commonly holds in implementation.

See also

References

  1. ↑ Knuth, Donald (1973). The Art of Computer Programming, Volume 1: Fundamental Algorithms (second edition). Addison-Wesley. pp. 213–214, also p. 631. ISBN 0-201-03809-9.
  2. ↑ Mehlhorn, Kurt; Sanders, Peter (2008), Algorithms and Data Structures: The Basic Toolbox 3 Representing Sequences by Arrays and Linked Lists (PDF), Springer, ISBN 978-3-540-77977-3 p. 63
  3. ↑ McConnell, Steve. "Code Complete" Edition 2 Pg. 621 ISBN 0-7356-1967-0
  4. ↑ Knuth, Donald (1973). The Art of Computer Programming, Volume 3: Sorting and searching. Addison-Wesley. p. 395. ISBN 0-201-03803-X.
This article is issued from Wikipedia - version of the Saturday, February 20, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.