加权概率随机选择数组

Question

我有一个数组和 returning 随机值。

const array = [ 1, 2 ,3 ,4 ,5, 6, 7, 8]
const rand = array[~~(Math.random() * array.length)]

我想 return 数组的一个随机元素，但具有更高索引（索引）不太可能被 returned 的加权概率。即 8 比 1.

更不可能 returned

我怎样才能做到这一点？

Answer 1

您可以使用一种技巧，通过加权概率将原始数组克隆到新数组。

您可以通过以下方式修改：

增加您想要显示更多的项目的权重
减少您想要展示的项目的权重。

您可以查看以下演示：

const array = [ 1, 2 ,3 ,4 ,5, 6, 7, 8 ]
const weight = [ 8, 7, 6, 5, 4, 3, 2, 1 ];

let randomArray = [];
array.forEach((item, index) => {
   var clone = Array(weight[index]).fill(item);
   randomArray.push(...clone);
});

const result = randomArray[~~(Math.random() * randomArray.length)]

console.log('random value:', result);

Answer 2

这是实现此目的的有效方法。此方法使用二进制搜索（尽管已根据您的需要进行了修改）。

以下是其工作原理的摘要：

你代表了在数组中被选中的某些元素的概率。所以如果你有 50% 的概率“A”，20% 的“B”，10% 的 C，5% 的 D，5% 的 E，0.1% 的 F 和 9.9% 的 G，这将是数组中的 [.5, .2, .1, .05, .05, .001, .099]。然而，这并不好，因为我们不能在二进制搜索中使用它，因为它没有排序——但如果我们对它进行排序，概率将不再对应于我们的字母数组 ([A,B,C,D,E,F,G])。因此，我们需要将每个概率相加，直到得到 1。现在概率数组如下所示：[.5, .7, .8, .85, .9, .901, 1]。现在已经排序了，还是对应上面的字母数组
现在我们在概率数组中创建一个介于 0 和最大值之间的运行dom 小数。 Math.random() 非常适合。
现在我们看看概率数组中的哪个值最接近这个分数。但有一个问题 - “最接近”的值不能小于分数。
一旦我们有了这个“最接近”值的索引，我们就可以使用相同的索引从字母数组中选择一个值。这是 JavaScript 中的示例：

function find(arr, x , start=0, end=arr.length) {
  if(end < start) return -1;
  else if(end == start) return end;
  const mid = Math.floor((start + end) / 2);  
  if(arr[mid] === x) return mid+1;
  else if(arr[mid] < x) return find(arr, x, mid+1, end);
  else
    return find(arr, x, start, mid);
};


const table_of_corresponding_probabilities = [.5,.7,.8,.85,.9,.901,1];
const values_to_pick_from = ["A", "B", "C", "D", "E", "F", "G"];


function weighted_random_pick(items, weights) {
    return items[find(weights, Math.random())];
};

console.log(weighted_random_pick(values_to_pick_from, table_of_corresponding_probabilities));

因此，根据这些概率，我们应该有 50% 的时间得到 As，其余时间得到其他字母。这是测试上述算法的运行domness 的测试：

function find(arr, x , start=0, end=arr.length) {
  if(end < start) return -1;
  else if(end == start) return end;
  const mid = Math.floor((start + end) / 2);  
  if(arr[mid] === x) return mid+1;
  else if(arr[mid] < x) return find(arr, x, mid+1, end);
  else
    return find(arr, x, start, mid);
};
const prob = [.5,.7,.8,.85,.9,.901,1];
const vals = ["A", "B", "C", "D", "E", "F", "G"];
const results = {A:0, B:0, C:0, D:0, E:0, F:0, G:0};
const times_it_ran = 160000;
for(let i = 0; i<times_it_ran; i++) {
    results[vals[find(prob, Math.random())]]++
};
for(letter in results) {
    console.log(letter+":",(results[letter]/(times_it_ran/100)).toFixed(3),"%");
};

当您运行上面的代码片段时，您应该会发现每个字母被选中的次数百分比接近该字母被选中的预期概率。当然它永远不会绝对相等，因为毕竟它是运行dom（或者至少是伪运行dom）。

好的，那速度和效率呢？让我们也测试一下：

function find(arr, x , start=0, end=arr.length) {
  if(end < start) return -1;
  else if(end == start) return end;
  const mid = Math.floor((start + end) / 2);  
  if(arr[mid] === x) return mid+1;
  else if(arr[mid] < x) return find(arr, x, mid+1, end);
  else
    return find(arr, x, start, mid);
};
const array_length = 330000;
const probs = Array.apply(null, {length: array_length}).map((x,i) => (i??0)/(array_length-1)); // Note: this way of creating an array means that each value has an equal chance of getting picked but the array is still very long;
const vals = Array.apply(null, {length: array_length}).map(Function.call, String);
const time = func => {
    console.time("timer");
    func();
    console.timeEnd("timer");
};

// Now time the time it takes to search within this LONG array:
function button_click() {
    var x = time(() => {
        vals[find(probs, Math.random())];
    });
};

<button onclick="button_click();">Run test</button>

如您所见，测试速度非常快。我的平均时间约为 2 毫秒。但是，这只会在长度为 3.3e5 的数组中搜索。这是我选择的值，否则我会收到运行ge 错误（内置函数的限制 Array.apply）。所以在这里我做了同样的测试，但使用了不同的方法来生成大量数组（一个 for 循环......我知道这可能是最糟糕的方法但它完成了工作）。

function find(arr, x , start=0, end=arr.length) {
  if(end < start) return -1;
  else if(end == start) return end;
  const mid = Math.floor((start + end) / 2);  
  if(arr[mid] === x) return mid+1;
  else if(arr[mid] < x) return find(arr, x, mid+1, end);
  else
    return find(arr, x, start, mid);
};


const len = 75e6; // 75 million elements in this array!

let probs = [];
for(let i = 0; i < 1; i+=(1/len)) {
    probs.push(i);
};

const time = func => {
    console.time("timer");
    func();
    console.timeEnd("timer");
};

// Now time the time it takes to search within this LONG array:
function button_click() {
    var x = time(() => {
        find(probs, Math.random());
    });
};

<button onclick="button_click();">Run test</button>

那么在运行对 7500 万个元素进行此测试之后，我们发现了什么？第一个测试比我们之前的测试稍微慢运行（有 3.3e5 个元素），其余的平均在 2ms 到 2.25ms 左右。所以这比使用 227 TIMES 个元素少的数组搜索慢 (2+2.25)/2 - avg time from last tests = 2.125-2 = 0.125 0.125ms。那就是二分查找高效的程度。实际上，我想建议 0.125 毫秒延迟的一部分可能是由于 CPU 内核由于构建数组的错误方法而非常热。是的，我说的是我们必须完成的 7500 万次迭代才能创建该数组！

希望效率对您有所帮助！如果您想使用此算法，只需使用我给您的第一个代码段，那里的所有内容都比最后几个代码段更具可读性。

加权概率随机选择数组

Weighted probability random choice array

javascript

statistics

probability

以下是其工作原理的摘要：