fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.Arrays;
  4. import java.util.Random;
  5. import java.util.function.IntFunction;
  6. import java.util.stream.IntStream;
  7.  
  8. /* Name of the class has to be "Main" only if the class is public. */
  9. class Randomize
  10. {
  11.  
  12.     public static int[] generateRandAndUniq(int desiredSize) {
  13.         int[] arrayResult = new int[desiredSize];
  14.         Random rand = new Random();
  15.         arrayResult[0]= rand.nextInt(desiredSize);
  16.         int counter = 0;
  17.         while (counter < desiredSize) {
  18.             int randValue = rand.nextInt(desiredSize*3);/* a larger interval! */
  19.             int[] tempArray= new int[counter+2];
  20.             System.arraycopy(arrayResult, 0, tempArray,0, counter);
  21.             tempArray[counter+1]=randValue;
  22.             if(!checkDuplicate(tempArray)){
  23.                 arrayResult[counter]=randValue;
  24.                 counter++;
  25.             }
  26.         }
  27.         return arrayResult;
  28.     }    
  29.  
  30.     public static boolean checkDuplicate(int[] arr) {
  31.         boolean[] bitmap = new boolean[maxValueInArray(arr)+1]; /* just put a big number to avoid looping to get the max value? */
  32.         for (int v : arr) {
  33.             if (!bitmap[v]) {
  34.                 bitmap[v] = true;
  35.             } else {
  36.                 return true;
  37.             }
  38.         }
  39.         return false;
  40.     }
  41.  
  42.  
  43.     public static int maxValueInArray(int[] arr){
  44.         int max=-1;
  45.         for(int v:arr){
  46.             if(v>max)
  47.                 max=v;
  48.         }
  49.         return max;
  50.     }
  51.  
  52.     public static final int[] generateRandAndUniqRGL(int desiredSize) {
  53.         int[] set = IntStream.range(0,  desiredSize * 3).toArray();
  54.         int index = set.length;
  55.         // Fisher-Yates.
  56.         Random rand = new Random();
  57.         while (index > 1) {
  58.             final int pos = rand.nextInt(index--);
  59.             final int tmp = set[pos];
  60.             set[pos] = set[index];
  61.             set[index] = tmp;
  62.         }        
  63.         return Arrays.copyOf(set, desiredSize);
  64.     }
  65.  
  66.     private static final void trialFn(String name, IntFunction<int[]> fn, int input) {
  67.         long nanos = System.nanoTime();
  68.         int[] data = fn.apply(input);
  69.         long time = System.nanoTime() - nanos;
  70.         System.out.printf("%s function for %d input took %6.3fms\n", name, input, time / 1000000.0);
  71.     }
  72.  
  73.     public static void main(String[] args) {
  74.     	// warm up:
  75.         trialFn("OPWarm", Randomize::generateRandAndUniq, 1000);
  76.         trialFn("RLWarm", Randomize::generateRandAndUniqRGL, 1000);
  77.  
  78.         for (int input : new int[]{10, 100, 1000, 10000}) {
  79.             trialFn("OP", Randomize::generateRandAndUniq, input);
  80.             trialFn("RL", Randomize::generateRandAndUniqRGL, input);
  81.         }
  82.     }
  83. }
Success #stdin #stdout 0.32s 4386816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
OPWarm function for 1000 input took 13.276ms
RLWarm function for 1000 input took 29.842ms
OP function for 10 input took  0.012ms
RL function for 10 input took  0.016ms
OP function for 100 input took  0.054ms
RL function for 100 input took  0.032ms
OP function for 1000 input took  3.896ms
RL function for 1000 input took  0.603ms
OP function for 10000 input took 164.937ms
RL function for 10000 input took  1.750ms
https://ideone.com/MrwWLV
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!