Взвешенное случайное значение в JavaScript - UPROGER

Примеры взяты из репозитория javascript-алгоритмов

Что такое “взвешенное случайное”

Допустим, у вас есть список предметов . Предметом может быть что угодно. Например, мы можем иметь список фруктов и овощей , которые вы хотели бы съесть: [ '🍌', '🍎', '🥕' ].

Список весов представляет собой вес (или вероятность, или важность) каждого элемента. Вес – это числа. Например, веса вроде [3, 7, 1]бы говорят, что:

вы хотели бы есть 🍎 apples чаще (в 7 нерабочее 3 + 7 + 1 = 11время),
тогда вы хотели бы есть bananas 🍌 реже (только в 3 неурочное 11 время),
и то, что carrots 🥕 вам действительно не нравится (есть его только в 1 нерабочее 11 время).

Если говорить о вероятностях, то список весов может быть массивом чисел с плавающей запятой, сумма которых равна 1 (т.е. [0.1, 0.5, 0.2, 0.2]).

Weighted Random в этом случае будет функция , которая будет случайным образом возвращать вам пункт из списка, и он будет принимать вес каждого элемента во внимание, так что элементы с большим весом будут выбраны чаще.

Пример интерфейса функции:

const items =   [ '🍌', '🍎', '🥕' ];
const weights = [  3,    7,    1  ];

function weightedRandom(items, weights) {
  // implementation goes here ...
}

const nextSnackToEat = weightedRandom(items, weights); // Could be '🍎'

Приложения взвешенного случайного

В генетическом алгоритме взвешенная случайная величина используется во время фазы «отбора», когда нам нужно выбрать наиболее приспособленных / сильнейших особей на основе их оценки пригодности для спаривания и для получения следующего более сильного поколения. Вы можете найти пример в статье « Самостоятельная парковка автомобиля в 500 строках кода» .
В рекуррентных нейронных сетях (RNN) при попытке решить, какую букву выбрать следующей (для формирования предложения), на основе вероятности следующей буквы. Вы можете найти пример в блокноте Jupyter « Создание рецептов с использованием рекуррентной нейронной сети» (RNN) .
В Nginx Load Balancing чаще отправлять HTTP-запросы на серверы с большим весом.
И более…

Алгоритм

Простой подход будет заключаться в следующем :

Повторите каждый элемент в списке в соответствии с его весом.
Выберите случайный предмет из списка.

Например, в нашем случае с фруктами и овощами мы могли бы создать следующий список размеров 3 + 7 + 1 = 11:

const items =   [ '🍌', '🍎', '🥕' ];
const weights = [  3,    7,    1  ];

// Repeating the items based on weights.
const weightedItems = [
  '🍌', '🍌', '🍌',
  '🍎', '🍎', '🍎', '🍎', '🍎', '🍎', '🍎',
  '🥕',
];

// And now just pick the random item from weightedItems array.

Однако, как вы можете видеть, этот подход может потребовать много памяти, в случае если объекты тяжелые, и в случае, если у нас их много, чтобы повторить в weightedItemsсписке.

Более эффективный подход будет заключаться в следующем :

Подготовьте список совокупных весов для каждого элемента (т. Е. cumulativeWeights Список, который будет иметь такое же количество элементов, что и исходный weightsсписок). В нашем случае это будет выглядеть так: cumulativeWeights = [3, 3 + 7, 3 + 7 + 1] = [3, 10, 11]
Сгенерируйте случайное число randomNumber от 0 до наивысшего значения совокупного веса. В нашем случае случайное число будет в диапазоне [0..11]. Допустим, у нас есть randomNumber = 8.
Просмотрите cumulativeWeights список слева направо и выберите первый элемент, который больше или равен randomNumber. Индекс такого элемента мы будем использовать для выбора элемента из items массива.

Идея этого подхода заключается в том, что более высокие веса будут «занимать» больше числового пространства. Следовательно, существует более высокая вероятность того, что случайное число попадет в «числовую корзину с более высоким весом».

const weights =           [3, 7,  1 ];
const cumulativeWeights = [3, 10, 11];

// In a pseudo-representation we may think about the cumulativeWeights array like this.
const pseudoCumulativeWeights = [
  1, 2, 3,               // <-- [3] numbers
  4, 5, 6, 7, 8, 9, 10,  // <-- [7] numbers
  11,                    // <-- [1] number
];

Вот пример того, как weightedRandomможно реализовать эту функцию:

/**
 * Picks the random item based on its weight.
 * The items with higher weight will be picked more often (with a higher probability).
 *
 * For example:
 * - items = ['banana', 'orange', 'apple']
 * - weights = [0, 0.2, 0.8]
 * - weightedRandom(items, weights) in 80% of cases will return 'apple', in 20% of cases will return
 * 'orange' and it will never return 'banana' (because probability of picking the banana is 0%)
 *
 * @param {any[]} items
 * @param {number[]} weights
 * @returns {{item: any, index: number}}
 */
export default function weightedRandom(items, weights) {
  if (items.length !== weights.length) {
    throw new Error('Items and weights must be of the same size');
  }

  if (!items.length) {
    throw new Error('Items must not be empty');
  }

  // Preparing the cumulative weights array.
  // For example:
  // - weights = [1, 4, 3]
  // - cumulativeWeights = [1, 5, 8]
  const cumulativeWeights = [];
  for (let i = 0; i < weights.length; i += 1) {
    cumulativeWeights[i] = weights[i] + (cumulativeWeights[i - 1] || 0);
  }

  // Getting the random number in a range of [0...sum(weights)]
  // For example:
  // - weights = [1, 4, 3]
  // - maxCumulativeWeight = 8
  // - range for the random number is [0...8]
  const maxCumulativeWeight = cumulativeWeights[cumulativeWeights.length - 1];
  const randomNumber = maxCumulativeWeight * Math.random();

  // Picking the random item based on its weight.
  // The items with higher weight will be picked more often.
  for (let itemIndex = 0; itemIndex < items.length; itemIndex += 1) {
    if (cumulativeWeights[itemIndex] >= randomNumber) {
      return {
        item: items[itemIndex],
        index: itemIndex,
      };
    }
  }
}