Peter Kras's Entry for the Unique Random Numbers Generator

Question: Peter Kras's Entry for the Unique Random Numbers Generator

Challenge: a custom Delphi function, Randomizer, takes an open integer array and should fill it with unique random numbers as fast as possible.

The code is submitted for the Unique Random Numbers Delphi Challenge

Answer: Unique random number generator entry by Peter Kras (The Netherlands):

 procedure Randomizer_Kras_Peter(const maxValue : int64; var values : array of int64) ;
 {
 Ther are in fact 2 methods of generating the numbers.
 The first one is fast for low element count:
 in the result array, compared to maxValue,
 the other one is much faster, when the result array is larger.
 I have done some testing and these are more or
 less the turning points:
 
 maxValue #elements
 10 6
 20 9
 50 16
 100 23
 200 33
 500 53
 1000 75
 
 I have used the formula SQRT(maxValue) * 2, this roughly
 matches the turning points above. (in fact I did not take the time to find a better formula).
 }
 
   procedure Randomizer_Method_1(const maxValue : int64; var values : array of int64) ;
  { Method 1:
   This is straightforward, just generate number, and if the number has not been generated
   before, store it, otherwise get a new random number and so on.
   This tends to be fast when the result array is small compared to maxValue.
   The result array is filled, element by element, for each element the following steps
   are taken:
   - generate the random number between 0 and the maxvalues
   - look at all previously filled ellements and check if the generated value is already used
   - if the number was found, repeat these steps
   - if the number is unique,store the value in the result array
   }
   var
     k, j : longint;
     iNewNumber : int64;
     bAgain : boolean;
   begin
     //loop though each element in the result array
     for k := Low(values) to High(values) do begin
       repeat
         //generate number (add 1 because numbers must start at 1)
         iNewNumber := 1 + Random(maxValue) ;
         //init flag
         bAgain := false;
         //check previous elements
         for j := Low(values) to k - 1 do begin
           if iNewNumber = values[j] then begin
             //oops, number already taken, exit for and do it again
             bAgain := true;
             Break;
           end;
         end;
       until Not(bAgain) ;
 
       //number is unique, store it
       values[k] := iNewNumber;
     end;
   end;
 
   procedure Randomizer_Method_2(const maxValue : int64; var values : array of int64) ;
 
  { Method 2:
 
   This generates a number from an array then overwrites that number
 with the value at the highest index in the array, and decrease a high
 water mark, effectively putting already chosen number
   out of reach of the randomizer. This tends to be fast when the result
 array is large compared to maxValue.
 
   First, a temporary dynamic array with maxValue elements is allocated.
 The array is filled with unique numbers, representing all the possible
 numbers that might occur in the result array. Each element will be set
 to its index number.
 Then the result array is filled, element by element, for each element
 the following steps are taken:
   - generate the random number between 0 and the "high water" mark
   - get a value from the temp array using the random number as an index
   - store the value in the result array
   - in the temp array assign the value at the "high water" mark to the
 element where the value was taken from
   - decrease the "high water" mark by 1
   - repeat this until all elements in the result array are filled
   }
 
   var
     k : longint;
     iIndex : int64;
     iHighWaterMark : int64;
     TempArray : array of int64;
   begin
     //allocate storage for temp array, and initialize it
     iHighWaterMark := maxValue;
     SetLength(TempArray, iHighWaterMark) ;
     for k := Low(TempArray) to High(TempArray) do TempArray[k] := k;
     //loop though each element in the result array
     for k := Low(values) to High(values) do begin
       //get a random number between 0 and unchosen numbers inclusive
       iIndex := Random(iHighWaterMark) ;
       //assign value (add 1 because result numbers must start with 1)
       values[k] := TempArray[iIndex] + 1;
       //assign the value at the "high water" mark to
 //the element where the value was taken from
       TempArray[iIndex] := TempArray[iHighWaterMark - 1];
       //decrease the high water mark
       iHighWaterMark := iHighWaterMark - 1;
     end;
   end;
 begin
   //use formula to determine which method to use
   if (High(values) + 1) > Sqrt(maxValue) * 2 then begin
     Randomizer_Method_2( maxValue, values ) ;
   end else begin
     Randomizer_Method_1( maxValue, values ) ;
   end;
 end;
 

Test data:
- array size: 10 000
- number range: 1 - 100 000

Peter's speed result: 3300 microseconds.

Explore the list of all accepted entries for the Fastest Unique Random Number Generator Delphi challenge.