Generar una matriz aleatoria y única de valores INT para un tamaño determinado -- java campo con array campo con random camp codereview Relacionados El problema

Generate random and unique array of int values for a given size


3
vote

problema

Español

Necesito generar una matriz de valores INT para un tamaño determinado, los valores deben ser aleatorios y únicos. La siguiente implementación es "OK" para valores pequeños [1,10k] , me gustaría obtener algunos comentarios sobre una mejor implementación

  /**  * Generate an array of random & unique values in the interval [0,desiredSize*3]  * To use only for small arrays with size in [1,50k]  * for an array of 1k time: 0.01s  * for an array of 10k time: 0.3s  * for an array of 50k time: 8s   * @param desiredSize  * @return  */ public int[] generateRandAndUniq(int desiredSize) {     int[] arrayResult = new int[desiredSize];     Random rand = new Random();     arrayResult[0]= rand.nextInt(desiredSize);     int counter = 0;     while (counter < desiredSize) {         int randValue = rand.nextInt(desiredSize*3);/* a larger interval! */         int[] tempArray= new int[counter+2];         System.arraycopy(arrayResult, 0, tempArray,0, counter);         tempArray[counter+1]=randValue;         if(!checkDuplicate(tempArray)){             arrayResult[counter]=randValue;             counter++;         }     }     return arrayResult; }  public boolean checkDuplicate(int[] arr) {     boolean[] bitmap = new boolean[maxValueInArray(arr)+1]; /* just put a big number to avoid looping to get the max value? */     for (int v : arr) {         if (!bitmap[v]) {             bitmap[v] = true;         } else {             return true;         }     }     return false; }   public int maxValueInArray(int[] arr){     int max=-1;     for(int v:arr){         if(v>max)             max=v;     }     return max; }   
Original en ingles

I need to generate an array of int values for a given size, the values should be random and unique. the following implementation is "ok" for small values [1,10k], I would like to get some feedback on better implementation

/**  * Generate an array of random & unique values in the interval [0,desiredSize*3]  * To use only for small arrays with size in [1,50k]  * for an array of 1k time: 0.01s  * for an array of 10k time: 0.3s  * for an array of 50k time: 8s   * @param desiredSize  * @return  */ public int[] generateRandAndUniq(int desiredSize) {     int[] arrayResult = new int[desiredSize];     Random rand = new Random();     arrayResult[0]= rand.nextInt(desiredSize);     int counter = 0;     while (counter < desiredSize) {         int randValue = rand.nextInt(desiredSize*3);/* a larger interval! */         int[] tempArray= new int[counter+2];         System.arraycopy(arrayResult, 0, tempArray,0, counter);         tempArray[counter+1]=randValue;         if(!checkDuplicate(tempArray)){             arrayResult[counter]=randValue;             counter++;         }     }     return arrayResult; }  public boolean checkDuplicate(int[] arr) {     boolean[] bitmap = new boolean[maxValueInArray(arr)+1]; /* just put a big number to avoid looping to get the max value? */     for (int v : arr) {         if (!bitmap[v]) {             bitmap[v] = true;         } else {             return true;         }     }     return false; }   public int maxValueInArray(int[] arr){     int max=-1;     for(int v:arr){         if(v>max)             max=v;     }     return max; } 
        
     
     

Lista de respuestas

6
 
vote

Mientras su código se ve bien, hay dos preocupaciones que tengo con ella.

El primero es el uso un tanto arbitrario de after_login()1 como el límite de los números aleatorios. ¿Por qué ese valor?

El problema de rendimiento que tiene es el bucle anidado que tiene primero para generar los valores, y luego dentro de su bucle nuevamente para verificar si hay duplicados. Puede reducir significativamente el bucle interno utilizando un 99887766655443312 en combinación con la matriz para verificar la singularidad. El SET consumirá más memoria, pero permitirá un cheque sin ningún bucle (reducirá su algoritmo $ O (n ^ 2) $ a $ O (n) $).

El código se vería como:

  after_login()3  

El cambio establecido tendrá un impacto significativo en su rendimiento ... pero, ¿hay una mejor manera?

Suponiendo su límite de after_login()4 y asumiendo un conjunto de datos relativamente pequeño (menos de un millón, más o menos), entonces una mejor opción sería para usted:

  1. Crear una matriz de tamaño after_login()5
  2. Poverlo con números consecutivos after_login()6
  3. nos baraja usando una fisher-yates shuffle < / a>.
  4. devuelve el primer after_login()7 elementos de la matriz barajada.

Esto no requeriría ninguna revisión duplicada en absoluto.

Puse un código para demostrar esto:

  after_login()8  

Himié este método contra el suyo por unos tamaños de datos aquí en Ideone: https://ideone.com/mrwwlv < / a>

Nota los resultados del tiempo:

  after_login()9  
 

While your code looks right, there are two concerns I have with it.

The first is the somewhat arbitrary use of desiredSize * 3 as the limit of the random numbers. Why that value?

The performance issue you have is the nested looping you have first to generate the values, and then inside you loop again to check for duplicates. You can reduce the inner loop significantly by using a Set in combination with the array to check for uniqueness. The set will consume more memory, but it will allow a check without any looping (it will reduce your \$O(n^2)\$ algorithm to \$O(n)\$).

The code would look something like:

public static int[] generateRandAndUniqSet(int desiredSize) {     int[] arrayResult = new int[desiredSize];     Set<Integer> uniq = new HashSet<>();     Random rand = new Random();     int counter = 0;     while (counter < desiredSize) {         int randValue = rand.nextInt(desiredSize*3);/* a larger interval! */         if (uniq.add(randValue)) {             arrayResult[counter++] = randValue;         }     }     return arrayResult; }     

That Set change will have a significant impact on your performance.... but, is there a better way?

Assuming your limit of desiredSize * 3 and assuming a relatively small dataset (less than a million, or so), then a better option would be for you to:

  1. create an array of size desiredSize * 3
  2. populate it with consecutive numbers [0, 1, 2, 3, 4, ....., desiredsize * 3 - 1]
  3. shuffle it using a Fisher-Yates shuffle.
  4. return the first desiredSize elements from the shuffled array.

This would require no duplicate-checking at all.

I put together some code to demonstrate this:

public static final int[] generateRandAndUniqRGL(int desiredSize) {      // generate set of sequential values from 0 ... desiredSize * 3     int[] set = IntStream.range(0,  desiredSize * 3).toArray();      // shuffle them     int index = set.length;     // Fisher-Yates.     Random rand = new Random();     while (index > 1) {         final int pos = rand.nextInt(index--);         final int tmp = set[pos];         set[pos] = set[index];         set[index] = tmp;     }      // return the first batch of them     return Arrays.copyOf(set, desiredSize); } 

I timed this method against yours for a few sizes of data here in ideone: https://ideone.com/MrwWLV

Note the timing results:

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 
 
 
   
   

Relacionados problema

14  Generación de token del proveedor de OAURH  ( Oauth provider token generation ) 
Actualmente estoy creando una oauth proveedor en Java usando jersey . A lo mejor de mi conocimiento, Jersey no proporciona un método para crear tokens de O...

3  Generador de horario aleatorio  ( Random schedule generator ) 
En un intento de probar algo nuevo, y posiblemente ayudar en el trabajo, intenté crear un generador de programación aleatorio que genera horarios basados ​​en...

4  Agregar una entrada duplicada al azar a una lista en Haskell usando Mónad aleatorio  ( Adding a duplicate entry randomly into a list in haskell using random monad ) 
Hay una nueva versión de esto como V2 - Agregar una entrada duplicada al azar a una lista en Haskell usando Monad Random Escribí esto tratando de configur...

20  Algoritmo de arrastre para un juego de "Supongo que afinar"  ( Shuffling algorithm for a guess that tune game ) 
Estoy haciendo un juego de "Supongo que afinar" en Visual Basic 6 que se supone que debe jugar cada canción en un orden aleatorio: ' from frmGuessGame.frm ...

6  Clasificación de números no repetidos aleatorios  ( Sorting random non repeating numbers ) 
Estoy trabajando en un programa en el que 10000 números no repetidos aleatorios se clasifican de forma selectiva en orden ascendente " Team | Another Team ...

5  Selector y reproductor de MP3 aleatorio  ( Random mp3 selector and player ) 
Entonces, soy un glotón para el castigo, o no tengo vida, pero yo escribió un script para responder una pregunta sobre Preguntar en preguntar Ubuntu como sol...

4  Tarea de lotería virtual  ( Virtual lotto task ) 
Tuve la tarea de escribir un simulador de lotería. Mi programa funciona de la siguiente manera: Para comenzar, el usuario puede escribir en 6 números. Lu...

4  Simple WinForm que aleatoriza imágenes en una caja de fotos  ( Simple winform that randomizes images in a picturebox ) 
Escribí este código para una aplicación simple que nos da imágenes aleatorias. El código funciona, pero siento que estoy haciendo algo mal. Y una cosa que me ...

-1  Aleatorizar una lista de objetos jquery  ( Randomize a jquery object list ) 
Bueno, este fue un competencia de código más simple en mi trabajo. Probé un par de cosas, aceptaron, pero ninguno de ellos lo quería. Porque ambos siempre est...

4  Plantilla de C ++ para elegir aleatoriamente de N Elementos con distribución uniforme  ( C template to randomly choose from n elements with uniform distribution ) 
Hay un bonito algoritmo para elegir al azar un elemento de una lista en una sola pasada: Pase a través de la lista Manteniendo el elemento elegido hasta aho...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos