C# Sentinel Element

Sentinels can simplify loops.

How can you optimize a loop with two conditions by using a sentinel value in the data? With the C# language, we make a loop with two conditions only have one by using a sentinel element in the data array.

Optimizations

Example. In this example, we have two conditions that must be satisfied for the while-loop to continue. We require the number of elements encountered must be less than N, and the elements must be greater than zero.

While

In Example1, we specify these two conditions as if-statements. In Example 2, meanwhile, we force the search to stop at the maximum number of elements by changing the data after the last valid element.

If

Then: We can use a single check for each element to ensure validity. Example2 has only one if-statement.

C# program that uses sentinel

using System;

class Program
{
    static void Main()
    {
	Console.WriteLine(Example1(5));
	Console.WriteLine(Example2(5));
    }

    static int Example1(int n)
    {
	// Count number of elements greater than zero in first N elements.
	int[] array = { 1, 1, 2, 2, 3, 3, 4, 4, 5, 5 };

	// Loop.
	int position = 0;
	int count = 0;
	while (true)
	{
	    if (position >= n)
	    {
		break;
	    }
	    if (array[position] <= 0)
	    {
		break;
	    }
	    count++;
	    position++;
	}
	return count;
    }

    static int Example2(int n)
    {
	// Count number of elements greater than zero in first N elements.
	int[] array = { 1, 1, 2, 2, 3, 3, 4, 4, 5, 5 };

	// Assign a sentinel.
	array[n] = 0;

	// Loop.
	int position = 0;
	int count = 0;
	while (true)
	{
	    if (array[position] <= 0)
	    {
		break;
	    }
	    count++;
	    position++;
	}
	return count;
    }
}

Output

5
5

Discussion. The difficulty with demonstrating sentinel code is that most of the uses of sentinels would come in complex searching algorithms. Because of their complexity, they are not easy to demonstrate. And examples are not widely applicable.

Tip: You can mutate the data source to reduce the number of logical checks in an inner loop, improving performance by reducing branches.

Summary. Sentinels can be used in arrays to make search loops less complicated and faster. The cost of changing the data must be weighed against the performance gain. Because of this, sentinels are best suited for long-running loops.

Related Links