DEVTOME.COM HOSTING COSTS HAVE BEGUN TO EXCEED 115$ MONTHLY. THE ADMINISTRATION IS NO LONGER ABLE TO HANDLE THE COST WITHOUT ASSISTANCE DUE TO THE RISING COST. THIS HAS BEEN OCCURRING FOR ALMOST A YEAR, BUT WE HAVE BEEN HANDLING IT FROM OUR OWN POCKETS. HOWEVER, WITH LITERALLY NO DONATIONS FOR THE PAST 2+ YEARS IT HAS DEPLETED THE BUDGET IN SHORT ORDER WITH THE INCREASE IN ACTIVITY ON THE SITE IN THE PAST 6 MONTHS. OUR CPU USAGE HAS BECOME TOO HIGH TO REMAIN ON A REASONABLE COSTING PLAN THAT WE COULD MAINTAIN. IF YOU WOULD LIKE TO SUPPORT THE DEVTOME PROJECT AND KEEP THE SITE UP/ALIVE PLEASE DONATE (EVEN IF ITS A SATOSHI) TO OUR DEVCOIN 1M4PCuMXvpWX6LHPkBEf3LJ2z1boZv4EQa OR OUR BTC WALLET 16eqEcqfw4zHUh2znvMcmRzGVwCn7CJLxR TO ALLOW US TO AFFORD THE HOSTING.

THE DEVCOIN AND DEVTOME PROJECTS ARE BOTH VERY IMPORTANT TO THE COMMUNITY. PLEASE CONTRIBUTE TO ITS FURTHER SUCCESS FOR ANOTHER 5 OR MORE YEARS!

Bingo Algorithm

A (very) long time ago, as a trainee programmer, I was given the task of writing a computer algorithm to simulate the action of a Bingo caller. The requirement is to draw each of the numbers from 1 to 100 in a random order, and the point of the exercise is to write the computer simulation of this in the most efficient way possible.

This article describes some of the techniques that can be used to do this, explaining the relative merits of each solution, and hopefully will provide some useful instruction to a novice programmer.

Method 1

My first idea was to fill up an array with the numbers, and then start generating random numbers (in the range 1 to 100). On each occasion we set the number in the array to 0 as we match it, and if we select a number at random which matches one we have already called, then we simply try again and select another number.

Pros and Cons

Pros: A simple and easy to understand algorithm.

Cons: As more and more numbers are drawn, it becomes more and more likely that the next random number will correspond to a number that has been already drawn, so more and more random numbers will need to be generated for each number called, slowing down the program.

Code

% cat hat1.c
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <math.h>
#include <unistd.h>

#define BINGO_SIZE 20000000

long numbers[BINGO_SIZE] ;

main (int argc, char **argv)
{
    // init random seed
    struct timeval tp ;
    gettimeofday (&tp, NULL) ;

    srandom (tp.tv_usec) ;

    // create the bingo numbers

    long i = 0 ;
    for (i=0;i<BINGO_SIZE;i++)
    {
         numbers[i] = i + 1 ;
    }

    // now call them

    long remaining = BINGO_SIZE ;

    while (remaining)
    {
	 // choose a random element in the array
         long pos = random() % BINGO_SIZE ;

	 // if we haven’t already selected this number, it is our next result
         if (numbers[pos] != 0)
         {
               if (remaining < 50)
                    printf ("%d, ", numbers[pos]) ;

	       // mark the number as selected
               numbers[pos] = 0 ;
               remaining-- ;
          }
     }
     printf ("etc \n") ;
}

Performance

You will notice looking at the program code that it is not dealing with only 100 bingo numbers but in fact a staggering 20 million. I should point out that the programs I am presenting in this article are not the originals from this trainee programmer exercise of nearly 30 years ago (1985) but my recent recreation of the programs using the same algorithms. The original programs were run in interpreted BASIC 1) on what used in those days to be termed an “IBM compatible” PC . Because of the advancements in processing power over the years, I have had to increase the size of the data set to make it easier to measure the relative merits of each of the algorithms in terms of performance. All the algorithms I am presenting run almost instantaneously as compiled code 2) on a modern system if the size of the data set is left as 100 numbers.

Believe it or not, my recollection is that the performance of the original programs (to operate on only 100 numbers using interpreted BASIC on the IBM compatible PC of the time) was somewhat worse than the performance of the new versions I have created that manipulate 20 million numbers.

Here is the output from a timed run of the program

% time ./hat1
9609161, 7290025, 10692180, 4540009, 5159560, 19385050, 14157180, 2695951, 18591275, 15897045, 
16002389, 14153865, 4344174, 6411181, 14217771, 18360853, 710570, 11780676, 5720755, 6495986, 
13588493, 18458123, 16437398, 1387770, 11920787, 4414674, 2575774, 16885899, 7742104, 2867165, 
8899627, 9679329, 7261282, 18995627, 6371500, 18043792, 10369864, 19905308, 9513110, 8142800, 
4623736, 16613533, 19747558, 2502960, 8637128, 12438735, 5184601, 10509484, 16774046, etc
[2]    21770 exit 5     ./hat1
./hat1  27.53s user 0.20s system 98% cpu 28.222 total

Method 2

After some thought on the matter I realized that if each number in the array is swapped with another number (at random) then the whole array of numbers would be randomized. All that would then be necessary is to read out the numbers from the array elements in order, since the contents are now randomized.

As it turned out, this was the solution that my mentor was hoping for.

Pros and Cons

Pros: The data set only has to be parsed once to create the randomisation, and thus is much more efficient than Method 1. Also it is easy to describe what is going on. In software engineering this is usually preferable to a more efficient but harder to follow design, since the code may well have to be maintained by other people in the future.

Cons: It is not the absolute fastest algorithm.

Code

% cat hat2.c
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <math.h>
#include <unistd.h>

#define BINGO_SIZE 20000000

static  long numbers[BINGO_SIZE] ;

main (int argc, char **argv)
{
        long tmp = 0 ;

        // init random seed
        struct timeval tp ;
        gettimeofday (&tp, NULL) ;

        srandom (tp.tv_usec) ;

        // create the bingo numbers

        long i = 0 ;
        for (i=0;i<BINGO_SIZE;i++)
        {
                numbers[i] = i + 1 ;
        }

        // now shuffle the array. Swap each array element with another one at random

        for (i=0;i<BINGO_SIZE;i++)
        {
	        // select a random position in the array
                long newpos = random() % BINGO_SIZE ;

	        // swap this element with the element in the randomly selected position
                tmp = numbers[newpos] ;
                numbers[newpos] = numbers[i] ;
                numbers[i] = tmp ;
        }

        // now call them

        for (i=0;i<BINGO_SIZE;i++)
        {
                if (i < 50)
                        printf ("%d, ", numbers[i]) ;
        }
        printf ("etc \n") ;
}

Performance

% time ./hat2
6068748, 14802624, 13687226, 13221347, 17912271, 490687, 4072190, 17374265, 2422813, 11019818, 
16238890, 10670013, 12996111, 4848285, 17737360, 15205892, 1231741, 10708433, 4905488, 18869997, 
3638096, 2252122, 13964663, 16523510, 12875497, 1805864, 5543236, 19460394, 19653573, 15778226, 
4355475, 4345297, 1800775, 2430728, 17064313, 15628445, 6205914, 11965925, 3814169, 12642794, 
16710733, 4586916, 19291519, 9706843, 1007785, 2614954, 139317, 6490882, 5839738, 9876470, etc
[2]    21757 exit 5     ./hat2
./hat2  2.55s user 0.18s system 98% cpu 2.777 total

Method 3

There is a faster solution than my mentor’s preferred solution (Method 2). With 30 years of programming experience behind me, this solution is obvious to me, but it certainly was not obvious at the time when I was just starting out as a programmer, so I will present it here as it may be instructive for others.

The array is filled up with the numbers 1 to 100 as in the other solutions. This corresponds to array elements 0 to 99. A random number is drawn in the range 0 to 99 and the content of that array element is our first result. Instead of setting it zero (as in Method 1) and thus leaving a gap in our data, we instead copy in the value from the last array element (element 99). Now we have a smaller data set (0 to 98) and we generate another random number for our next result, but this time we generate a number in the range 0 to 98. The content of that element of the array is our next result. Now we copy in the value from array element 98 to the element selected at random. With each iteration we reduce the range of the random number by 1, and also reduce the part of the array that we are looking at by 1.

Pros and Cons

Pros: This is the fastest solution to the problem (at least that I can come up with)

Cons: It is harder to describe what the code is doing than in Method 2, and thus maintainability of the code is reduced.

Code

borg02{msgmedia}8531% cat hat3.c
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <math.h>
#include <unistd.h>

#define BINGO_SIZE 20000000

static long numbers[BINGO_SIZE] ;

main (int argc, char **argv)
{
        // init random seed
        struct timeval tp ;
        gettimeofday (&tp, NULL) ;

        srandom (tp.tv_usec) ;

        // create the bingo numbers

        long i = 0 ;
        for (i=0;i<BINGO_SIZE;i++)
        {
                numbers[i] = i + 1 ;
        }

        // now call them

	// select a number at random and reduce the size of the data set
	// each time
        for (i=BINGO_SIZE;i>0;i--)
        {
                long pos = random() % i ;
                if (i < 50)
                        printf ("%d, ", numbers[pos]) ;
                numbers[pos] = numbers[i-1] ;
        }
        printf ("etc \n") ;
}

Performance

% time ./hat3
7113522, 4100963, 8762511, 8244692, 14209354, 16080200, 9326632, 8741749, 7328258, 15641102, 
8987140, 18932018, 16949197, 793406, 2483526, 12392363, 18642963, 9416116, 10161641, 19224275, 
2608833, 2242183, 14912980, 7342075, 17903118, 19980261, 13088727, 6064406, 9884282, 19840516, 
1705854, 15227216, 4154276, 7085028, 12331318, 14030105, 6270425, 9399990, 5887938, 3650571, 
15201167, 19175301, 13045451, 6914858, 14493332, 11135082, 8551081, 13575993, 2345387, etc
[2]    21758 exit 5     ./hat3
./hat3  1.99s user 0.15s system 98% cpu 2.183 total

As you can see runtime is 2.183 seconds compared with 2.777 seconds for Method 2. Unless performance is paramount I would prefer Method 2 for the clarity of what is being done.

Computing | Programming


QR Code
QR Code bingo_algorithm (generated for current page)
 

Advertise with Anonymous Ads