Estoy creando un tratamiento y quiero saber qué generador de números aleatorios es el más adecuado para generar prioridades en la inserción.
El conjunto de datos tiene aproximadamente 6000 elementos.
Estoy modificando una clase de plantilla existente (en gran parte solo métodos declarados sin definiciones) que se nos dio. El generador predefinido es el std::default_random_engineque solo genera números pseudoaleatorios. Me gustaría saber, si este generador es suficiente, y si no, ¿cuáles son las alternativas? Los datos se leerán de un archivo a la vez.
El generador de números aleatorios se declara como:
std::default_random_engine* generator_;
Solo se usa cuando se crea en un constructor de una clase contenedora
TreapItem<K, T>(key, data, (*generator_)())
Me gustaría tener la menor cantidad de colisiones posible. ¿Es std::default_random_engine* generator_;suficiente para no lograr colisiones o se necesita algún otro generador?
EDITAR : Preferiría una distribución uniforme, o algo parecido. Sin embargo, la distribución normal también podría funcionar.
El puntero al generador estaba en el código dado, no parecía un defecto a primera vista.
Este es un punto de referencia simple (¡pero no exhaustivo!) De los generadores aleatorios c ++ más la antigua función C rand y un generador rot-xor simple.
Hay una prueba de humo simple, que toma algunos bits del medio del número, pero de ninguna manera a prueba de cifrado.
Creo que todos funcionarían bien para un árbol de búsqueda binario aleatorio.
#include <random>
#include <iostream>
#include <chrono>
#include <stdlib.h>
struct rot_xor {
int32_t seed = 0x95abcfad;
inline uint32_t operator() () {
return seed = (seed << 1) ^ ((seed >> 31) & 0xa53a9be9);
}
};
struct crand {
int32_t seed = 0x95abcfad;
inline uint32_t operator() () {
return rand();
}
};
template <class Generator>
void benchmark(std::vector<int> &histo) {
Generator r;
int mask = histo.size() - 1;
for (int i = 0; i != 10000000; ++i) {
uint32_t val = (uint32_t)r();
histo[(val>>16) & mask]++;
}
}
int main() {
using std::chrono::high_resolution_clock;
using std::chrono::duration_cast;
using std::chrono::microseconds;
for (int i = 0; i != 9; ++i) {
std::vector<int> histo(0x100);
auto t0 = high_resolution_clock::now();
switch (i) {
case 0: benchmark<std::minstd_rand0>(histo); break;
case 1: benchmark<std::minstd_rand>(histo); break;
case 2: benchmark<std::mt19937>(histo); break;
case 3: benchmark<std::mt19937_64>(histo); break;
case 4: benchmark<std::ranlux24_base>(histo); break;
case 5: benchmark<std::ranlux48_base>(histo); break;
case 6: benchmark<std::default_random_engine>(histo); break;
case 7: benchmark<crand>(histo); break;
case 8: benchmark<rot_xor>(histo); break;
}
auto t1 = high_resolution_clock::now();
int min_histo = histo[0];
int max_histo = histo[0];
for (auto h : histo) {
min_histo = std::min(min_histo, h);
max_histo = std::max(max_histo, h);
}
std::cout << "test " << i << " took " << duration_cast<microseconds>(t1-t0).count() << "us\n";
std::cout << " smoke test = " << min_histo << " .. " << max_histo << "\n";
}
}
Los resultados muestran un rendimiento sorprendente para los valores predeterminados de C ++ bastante complejos, solo 3-5 veces más lento que un simple RNG. El mejor de los estándar parece ser el de sustraer con versiones de acarreo ranlux_ *. La antigua función C rand (), que creo que contiene una división, es, como era de esperar, la más lenta.
test 0 took 58066us
smoke test = 38486 .. 39685
test 1 took 39310us
smoke test = 38533 .. 39604
test 2 took 26382us
smoke test = 38503 .. 39591
test 3 took 29146us
smoke test = 38591 .. 39670
test 4 took 27721us <- not bad, ranlux24
smoke test = 38419 .. 39597
test 5 took 27310us
smoke test = 38608 .. 39622
test 6 took 38629us
smoke test = 38486 .. 39685
test 7 took 65377us
smoke test = 38551 .. 39541
test 8 took 10984us <-- fastest (rot-xor)
smoke test = 38656 .. 39710
Este artículo se recopila de Internet, indique la fuente cuando se vuelva a imprimir.
En caso de infracción, por favor [email protected] Eliminar
Déjame decir algunas palabras