Optimal Binary Insertion Sort - Scoreboard

| Introduction | | Investigation | | C Implementation | | Contact Information | | 64-Bit CRC Transition To Bytewise Lookup-Table | | Parent Web Page |

    A scoreboard holds a predefined number of scores.  It is always sorted in a descending order.  Identities are associated with every score on the board, and these values must be sorted to correspond with their scores.  When performing an in-depth search of an astronomical number of elements contained in a set, it is crucial to maintain a large scoreboard to keep track of the progress that your high level algorithm is making, and to assist with the search algorithm itself.  An optimal method exists to insert new elements into a scoreboard, but adequate documentation does not exist.  This page purports to provide just that; a comprehensive treatment of the Binary Insertion Sort, applied to the maintainance of a scoreboard.  A high level programming language capable of low level optimization is a prudent choice when performance is a concern, so the implementation presented below will use standard C.

    Here is an example scoreboard of size 10, produced by searching for the most point dense 5x5 Boggle board using the TWL06 word list:

    The board string located in position #0 translates to a Boggle board that looks like this:

---------------------
| R | S | L | C | S |
---------------------
| D | E | I | A | E |
---------------------
| G | N | T | R | P |
---------------------
| A | T | E | S | E |
---------------------
| S | M | I | D | R |
---------------------

    There are at least eight Boggle boards that contain 10,769 points on them.  The leader board presented above will produce 7 more, superficially unique boards either by a rotation, or reflection, with the same score.  I have every reason to believe that this top 10 list is the global maximal list of unique boards for the TWL06 Tournament Scrabble Word List lexicon.

    The first task when adding a new entry to a scoreboard is to determine if the score is high enough to qualify it for inclusion.  This is accomplished by testing if the score is greater than that of the current scoreboard's final entry at position #(Size - 1).  Now check if it belongs in position #0, or position #(Size - 1) to narrow the search domain.  Finally, we proceed to determine the insertion position with our bounds set to (0, Size - 2].

    The task of optimal position determination is predictably a type of Binary Search.  There is one major caveat attached to the Binary Search algorithm in the scoreboard domain; the score that we are looking to find may not be on the scoreboard.  A Binary Search proceeds through a number of iterations, each time reducing the search domain by a factor of 2.  If the score that we are searching for exists on the scoreboard, then the number of iterations required is kept to a minimum, while at the same time eliminating the need to test an additional conditional statement every iteration.  There is no guarantee that the score we are looking for will be on the board, so we need to find a method to eliminate the required iterative conditional statement test.

    The optimal solution to the iterative-conditional-test problem is as barbaric as it is optimal.  Simply set the number of positions on the scoreboard to be a very particular type of number.  This number is chosen to keep the total number of conditional tests to an absolute minimum when the new score does not exist on the scoreboard already.  To accomplish this, the search uses a constant number of iterations to land on the correct position, or one position above the correct position.  The equation defining the optimal # of positions on a scoreboard is posted below.  The numbers resulting from this calculation enforce that no entry on the scoreboard will ever be examined more than once.

    The # of positions listed above may seem odd, but remember that there is a very good reason why these represent optimal scoreboard sizes.  If the initial differene between the left and right bounds of a Binary Search is a power of 2, we know something important with absolute certainty.  We know that on the LOG-base-2 of (n)'th iteration, we will arrive at a position flanked by the final, left and right bounds.  Further, this guarantees that the correct insertion position is one conditional statement away from being determined.

    We have now arrived at our insertion position with a minimal number of comparisons.  One comparison is made to see if the new score makes the list.  The second and third comparisons determine if the new score should be in the last or first position on the list, respectively.  Now the iterations begin and one comparison is made for sure.  If the first comparison fails, a second comparison will determine if we should move in the opposite direction or if we have found an identical score in the scoreboard.  After this conditional cascade, the "NextElement" is set to "Left"+(("Right"-"Left")>>1), where "Left" and "Right" are the current search boundaries, and >>1 is a single right bit-shift equivalent to a division by 2.  If compiler optimization is used, the constant iteration loop will be unwound, and there will not be either a counter variable or an exit condition.  For this reason it is important to use an optimization flag with your compiler.  For example:   gcc -O3 ProperBinaryInsertionSort.c   Another low level optimization is to replace integer values with unsigned integers, where possible, because the arithmetic is less complex.

    Say that the insertion position is found at "NextElement".  First, the new identity is copied into the space that the entry being terminated currently occupies, and a pointer to it is saved in a temporary variable.  Next, use an optimized memory movement function like C's memmove() to push the memory block starting at "NextElement" back one position in the scoreboard array; this needs to be done for both the scores and the associated identities.  Finally, copy the new score and temporary identity pointer into the "NextElement" position on the scoreboard.

    The scoreboard has now been maintained in an optimal fashion, but let's not pat each other's backs just yet.  We need to consider a common application of a scoreboard to really improve the real world performance.

The Prototype Application:

5x5 Boggle...  Out of the 26^25 possible boards, find the board with the most points on it.

The number 236,773,830,007,967,588,876,795,164,938,469,376 qualifies as astronomical in my books.

    There will almost certainly be rounds of batch processing involved, as well as a master and evaluation list that keep track of the best results.  Each batch will have its own list of board scores, and these are inherently unordered.  Binary Insertion Sort can not stand up to C's qsort() when sorting an entire unordered list, so each batch will rely heavily on an optimization of C's internal Quick Sort that replaces recursion with an explicit stack.  This concept is documented here.  Next, we have to merge the batch lists into the master and evaluation lists.  In a multi-threaded environment, it is very important for the main thread to minimize the time required for coordinating the efforts of the worker threads so that CPU resources can be fully exploited.  Merging will be accomplished one board at a time, and when a board on the batch list is reached that does not qualify for the master list, the merging is complete.  The rest of the boards on the batch list will be terminated.  The insertion point for the previous board in the batch list could be considered an upper bound for the next board on the batch list, but the initial range of values being searched must have a difference equal to a power of 2.  Further investigation is required to determine if an index of master list waypoints for initial search parameters would provide a performance boost in the insertion procedure.  I speculate that the increased complexity will outweigh the benefits of a smaller search range, so I have not carried out this investigation.  Log(N) complexity is very hard to beat.

    I am posting the file ProperBinaryInsertionSort.c as a template for the optimal maintainance of a size 10 scoreboard.  It includes the comparison counter "Result", which I used to refine the algorithm, so please remove this variable before you put the code into use.  Also, remember that I converted the C file into an HTML format so download the untampered with file here...  ProperBinaryInsertionSort.c.

// This program is to my knowledge, the best low level scoreboad insertion scheme possible.
// ARRAY_SIZE must be equal to 2^n + 2 for this algorithm to work as optimally as it does.
// memmove() has replaced for() loops to shift array elements, because there is a claim that it is faster.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <limits.h>

#define ARRAY_SIZE 10
// This constant search depth is 1 less than LOG-base-2(ARRAY_SIZE - 2) because the final condition statement is conducted outside of the loop.
#define MAX_LOOP_SEARCH_DEPTH 2

// Returns the number of comparisons made to arrive at the insertion position.  Returns "1" if the "NewValue" is too small to make the list.
// When put into use, this function should only return a boolean flag to indicate if the "NewValue" made the cut.
unsigned int BinaryInsertionSortOne(unsigned int *ThisArray, unsigned int NewValue){
  unsigned int X;
  unsigned int Result = 1;
  unsigned int Left = 0;
  unsigned int Right = ARRAY_SIZE - 1;
  unsigned int NextElement;
  
  // "NewValue" does not make the cut; it is too small.
  if ( NewValue <= ThisArray[Right] ) return Result;

  // "NewValue" belongs at the end of the list.
  Right -= 1;
  Result += 1;
  if ( NewValue <= ThisArray[Right] ) {
    ThisArray[ARRAY_SIZE - 1] = NewValue;
    return Result;
  }
  
  // "NewValue" belongs at the first position in the list.
  Result += 1;
  if ( NewValue >=  ThisArray[Left] ) {
    memmove(ThisArray + 1, ThisArray, sizeof(unsigned int)*(ARRAY_SIZE - 1));
    ThisArray[Left] = NewValue;
    return Result;
  }
  
  // Set the initial midpoint.
  NextElement = Left + ((Right - Left)>>1);
  
  // This loop will be unwound by compiler optimization.
  for ( X = 0; X < MAX_LOOP_SEARCH_DEPTH; X++ ) {
    Result += 1;
    // "NextElement" is the new "Left".
    if ( ThisArray[NextElement] >  NewValue ) {
      Left = NextElement;
    }
    // "NextElement" will become the new "Right".
    else if ( ThisArray[NextElement] <  NewValue ) {
      Result += 1;
      Right = NextElement;
    }
    // "NextElement" holds a value equal to "NewValue", and is the insertion point.
    else {
      Result += 1;
      // memmove() is going to employ pointer arithmatic for pointers to internal array members.
      memmove(ThisArray + NextElement + 1, ThisArray + NextElement, sizeof(unsigned int)*(ARRAY_SIZE - 1 - NextElement));
      ThisArray[NextElement] = NewValue;
      printf("Out Early\n");
      return Result;
    }
    // Advance the "NextElement";
    NextElement = Left + ((Right - Left)>>1);
  }
  
  Result += 1;
  // "NextElement" is now flanked by "Left" and "Right", and this is known with absolute certainty.
  // Since two cases will result in the insertion position being equal to "Right", we only need to make one comparison on the final iteration.
  if ( ThisArray[NextElement] <  NewValue ) {
    memmove(ThisArray + NextElement + 1, ThisArray + NextElement, sizeof(unsigned int)*(ARRAY_SIZE - 1 - NextElement));
    ThisArray[NextElement] = NewValue;
    printf("Out First\n");
    return Result;
  }
  // The "NewValue" is smaller or equal to "ThisArray[NextElement]", so the insertion position will be "Right".
  else {
    memmove(ThisArray + Right + 1, ThisArray + Right, sizeof(unsigned int)*(ARRAY_SIZE - 1 - Right));
    ThisArray[Right] = NewValue;
    printf("Out Second\n");
    return Result;
  }
}

int main(){
  unsigned int X;
  unsigned int NumberOfComparisons;
  long int Input;
  unsigned int TheArray[ARRAY_SIZE];
  
  // Set the initial values on the scoreboard far enough apart, so we can test the insertion performance at every position in the array.
  for ( X = 0; X < ARRAY_SIZE; X++ ) TheArray[X] = 10*(ARRAY_SIZE - X);
  printf("We are going to be inserting values into this array if they are big enough:\n\n");
  for ( X = 0; X < ARRAY_SIZE; X++ ) printf("|%u", TheArray[X]);
  printf("|\n\n");
  
  while ( 1 ) {
    printf("Enter an unsigned, 32 bit integer that you want on the scoreboard(ctrl c - To Exit): ");
    if ( scanf("%ld", &Input) == 0 ) return 0;
    if ( Input < 0 ) return 0;
    if ( Input > UINT_MAX ) return 0;
    NumberOfComparisons = BinaryInsertionSortOne(TheArray, (unsigned int)Input);
    printf("\nThe Insertion of |%u| required |%d| comparisons.\n\n", (unsigned int)Input, NumberOfComparisons);
    for ( X = 0; X < ARRAY_SIZE; X++ ) printf("|%u", TheArray[X]);
    printf("|\n\n");
  }
  
  return 0;
}

| Go Back to the Top |