Comment générer des nombres aléatoires pondérés en programmation : échantillonnage par rejet ou recherche itérative ?

Generating Weighted Random Numbers in Programming

Weighted random numbers find application in various scenarios where specific values within a range have different probabilities of being selected. In this article, we explore two effective approaches to achieve this:

The first approach, proposed by the original questioner, involves Rejection Sampling. This method creates a lookup table populated with the elements in the range, where each element appears a number of times proportional to its weight. Subsequently, a random index is chosen from the lookup table to retrieve the random number. The trade-off here lies in the linear time complexity for building the lookup table and the potential memory consumption for large weight specifications.

Alternatively, the Iterative Search method iteratively calculates the sum of weights while traversing the weight specification. It compares this sum with a randomly generated number between 0 and 1. If the sum exceeds the random number, the corresponding value is returned as the random number. Unlike rejection sampling, this approach incurs no upfront cost but exhibits an average time complexity linear to the number of entries in the weight specification.

To demonstrate both approaches in JavaScript:

// Rejection Sampling
function weightedRand(spec) {
  var i, j, table = [];
  for (i in spec) for (j = 0; j < spec[i] * 10; j++) table.push(i);
  return function() { return table[Math.floor(Math.random() * table.length)]; };
}
var rand012 = weightedRand({0:0.8, 1:0.1, 2:0.1});

// Iterative Search
function weightedRand2(spec) {
  var i, sum = 0, r = Math.random();
  for (i in spec) { sum += spec[i]; if (r <= sum) return i; }
}

The choice of approach depends on the specific application requirements, balancing time complexity, memory usage, and deterministic behavior. Rejection sampling offers constant-time lookups at the cost of upfront table construction, while iterative search provides a simpler implementation with linear-time performance. By leveraging these techniques, programmers can effectively generate weighted random numbers for their various programming needs.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!