java generar - Genera números aleatorios sin usar ninguna función externa




clase como (9)

Podría obtener la hora actual del sistema, pero eso también requeriría una función en la mayoría de los idiomas.

Estas fueron las preguntas formuladas en una de las entrevistas a las que asistí recientemente.

Por lo que sé, un número aleatorio entre dos números se puede generar de la siguiente manera

public static int rand(int low, int high) {
    return low + (int)(Math.random() * (high - low + 1));
}

Pero aquí estoy usando Math.random () para generar un número aleatorio entre 0 y 1 y usar eso para ayudarme a generar entre bajo y alto. ¿Hay alguna otra manera que pueda hacer directamente sin usar funciones externas?


Puede usar la dirección de una variable o combinar la dirección de más variables para hacer una más compleja ...


Los generadores de números pseudoaleatorios típicos calculan nuevos números basados ​​en los anteriores, por lo que en teoría son completamente deterministas. La única aleatoriedad se garantiza al proporcionar una buena semilla (inicialización del algoritmo de generación de números aleatorios). Mientras que los números aleatorios no sean muy críticos para la seguridad (esto requeriría números aleatorios "reales"), un generador de números aleatorios recursivo de este tipo satisface las necesidades.

La generación recursiva se puede expresar sin ninguna función "externa", una vez que se proporcionó una semilla. Hay un par de algoritmos para resolver este problema. Un buen ejemplo es el generador lineal congruente .

Una implementación de pseudocódigo podría parecerse a la siguiente:

long a = 25214903917;   // These Values for a and c are the actual values found
long c = 11;            // in the implementation of java.util.Random(), see link
long previous = 0;

void rseed(long seed) {
    previous = seed;
}

long rand() {
    long r = a * previous + c;
    // Note: typically, one chooses only a couple of bits of this value, see link
    previous = r;
    return r;
}

Aún necesita sembrar este generador con algún valor inicial. Esto se puede hacer haciendo uno de los siguientes:

  • Usar algo como la hora actual (bueno en la mayoría de los casos que no son críticos para la seguridad, como los juegos)
  • Uso de ruido de hardware (bueno para la aleatoriedad de seguridad crítica)
  • Usando un número constante (bueno para la depuración, ya que siempre obtienes la misma secuencia)
  • Si no puede usar ninguna función y no quiere usar una semilla constante, y si está usando un lenguaje que lo permite, también podría usar algo de memoria no inicializada. En C y C ++, por ejemplo, defina una nueva variable, no le asigne algo y use su valor para generar el generador. Pero tenga en cuenta que esto está lejos de ser una "buena semilla" y solo un truco para cumplir con sus requisitos. Nunca uses esto en código real.

Tenga en cuenta que no existe un algoritmo que pueda generar diferentes valores para diferentes ejecuciones con las mismas entradas sin acceso a algunas fuentes externas como el entorno del sistema. Cada generador de números aleatorios bien sembrados hace uso de algunas fuentes externas.


public class randomNumberGenerator {

    int generateRandomNumber(int min, int max) {
        return (int) ((System.currentTimeMillis() % max) + min);
    }

    public static void main(String[] args) {
        randomNumberGenerator rn = new randomNumberGenerator();
        int cv = 0;
        int min = 1, max = 4;
        Map<Integer, Integer> hmap = new HashMap<Integer, Integer>();

        int count = min;
        while (count <= max) {
            cv = rn.generateRandomNumber(min, max);
            if ((hmap.get(cv) == null) && cv >= min && cv <= max) {
                System.out.print(cv + ",");
                hmap.put(cv, 1);
                count++;
            }
        }

    }
}

Generador aleatorio de poisson

Digamos que comenzamos con un valor esperado 'v' de los números aleatorios. Luego, para decir que una secuencia de enteros no negativos satisface una Distribución de Poisson con el valor esperado v, significa que sobre las subsecuencias, la media (promedio) del valor aparecerá como "v". Poisson Distribution es parte de las estadísticas y los detalles se pueden encontrar en wikipedia. Pero aquí la principal ventaja de usar esta función es: 1. Solo se generan valores enteros. 2. La media de esos enteros será igual al valor que inicialmente proporcionamos.

Es útil en aplicaciones donde los valores fraccionarios no tienen sentido. La cantidad de aviones que llegan a un aeropuerto en 1 minuto es de 2.5 (no tiene sentido), pero implica que en 2 minutos llegan 5 planes.

int poissonRandom(double expectedValue) {
  int n = 0; //counter of iteration
  double limit; 
  double x;  //pseudo random number
  limit = exp(-expectedValue);
  x = rand() / INT_MAX; 
  while (x > limit) {
    n++;
    x *= rand() / INT_MAX;
  }
  return n;
}

La línea

rand() / INT_MAX

Debe generar un número aleatorio entre 0 y 1. Para que podamos usar el tiempo del sistema. Segundos / 60 servirá el propósito. La función que deberíamos usar es totalmente dependiente de la aplicación.


Puede hacerlo sin funciones externas si se le permite usar algún estado externo (por ejemplo, una inicialización larga con la hora actual del sistema). Esto es suficiente para que usted implemente un generador de números puedo-aleatorios simple.

En cada llamada a su función aleatoria, usaría el estado para crear un nuevo valor aleatorio y actualizar el estado, de modo que las llamadas subsiguientes obtengan resultados diferentes.

Puede hacer esto solo con operaciones aritméticas y / o bit a bit de Java normales, por lo que no se requieren funciones externas.


¿ System.currentTimeMillis() cuenta como externo? Siempre se puede obtener esto y calcular mod por algún valor máximo:

int rand = (int)(System.currentTimeMillis()%high)+low;

Puede obtener casi aleatoriedad (en realidad caótica y definitivamente no es uniforme *) del mapa logístico x = 4x(1-x) comenzando con una "no racional" x entre 0 y 1 .

La "aleatoriedad" aparece debido a los errores de redondeo en el borde de la precisión de la representación de punto flotante.

(*) Puedes deshacer el sesgo una vez que sepas que está ahí.


Si usa mutexes para proteger todos sus datos, realmente no debería preocuparse. Mutexes siempre ha proporcionado suficientes garantías de orden y visibilidad.

Ahora, si usó atomics o algoritmos sin bloqueo, debe pensar en el modelo de memoria. El modelo de memoria describe con precisión cuándo los atómicos proporcionan garantías de ordenación y visibilidad, y proporcionan cercas portátiles para garantías codificadas a mano.

Anteriormente, los métodos atómicos se realizarían mediante el uso de compiladores intrínsecos o alguna biblioteca de nivel superior. Las cercas se habrían hecho usando instrucciones específicas de la CPU (barreras de memoria).





java c++ c algorithm data-structures