Выбрать элемент в массиве в процентах

Question

У меня есть массив, который содержит имена и проценты.Пример: [["JAMES", 3.318], ["JOHN", 3.271], ["ROBERT", 3.143]].Теперь у меня есть около тысячи таких имен, и я пытаюсь выяснить, как выбрать имя случайным образом на основе процента имени (например, как Джеймс как 3.318% и Джон как 3.271%), так что это имя будет иметьэтот процент выбора (у Роберта будет 3,143% выбора).Помощь будет оценена.

Answer 1

Я предполагаю, что вы будете рисовать несколько случайных значений, в этом случае важна эффективность.Более того, я предполагаю, что все имена уникальны и все проценты положительны (то есть, что пары с процентами 0.0 были удалены).

Вам дано то, что составляет (дискретную) функцию плотности вероятности (PDF).Первый шаг - преобразовать это в функцию кумулятивной плотности (CDF).

Предположим, нам дан следующий массив (процентная сумма которого равна 100).

arr = [["LOIS", 28.16], ["JAMES", 22.11], ["JOHN", 32.71], ["ROBERT", 17.02]]

Сначала отделимимена из процентов.

names, probs = arr.transpose
  #=> [["LOIS", "JAMES", "JOHN", "ROBERT"],
  #     [28.16, 22.11, 32.71, 17.02]]

Далее вычисляем CDF.

cdf = probs.drop(1).
            each_with_object([0.01 * probs.first]) { |pdf, cdf|
              cdf << 0.01 * pdf + cdf.last }
  #=> [0.2816, 0.5027, 0.8298, 1.0]

Идея состоит в том, что мы сгенерируем (псевдо) случайное число от нуля до единицы, r инайдите первое значение c CDF, для которого r <= c. ¹ . Чтобы сделать это эффективным способом, мы выполним интеллектуальный поиск CDF.Это возможно, потому что CDF является возрастающей функцией.

Я сделаю бинарный поиск, используя Array # bsearch_index .Этот метод по сути такой же, как Array # bseach (чей документ является релевантным), за исключением того, что возвращается индекс cdf, а не элемент cdf, выбранный случайным образом.Вскоре станет понятно, зачем нам нужен индекс.

r = rand
  #=> 0.6257547400776025
idx = cdf.bsearch_index { |c| r <= c }
  #=> 2

Обратите внимание, что мы не можем записать cdf.bsearch_index { |c| rand <= c }, так как rand будет выполняться каждый раз, когда вычисляется блок.

Случайнопоэтому выбрано имя ²

names[idx]
  #=> "JOHN"

Теперь давайте соберем все это вместе.

def setup(arr)
  @names, probs = arr.transpose
  @cdf = probs.drop(1).
    each_with_object([0.01*probs.first]) { |pdf, cdf| cdf << 0.01 * pdf + cdf.last }
end

def random_name
  r = rand
  @names[@cdf.bsearch_index { |c| r <= c }]
end

Давайте попробуем.Выполните setup для вычисления переменных экземпляра @names и @cdf.

setup(arr)
@names
  #=> ["LOIS", "JAMES", "JOHN", "ROBERT"]
@cdf
  #=> [0.2816, 0.5027, 0.8298, 1.0]

и затем вызывайте random_name каждый раз, когда требуется произвольное имя.

5.times.map { random_name }
  #=> ["JOHN", "LOIS", "JAMES", "LOIS", "JAMES"]

^{1.Вот как большинство дискретных случайных величин генерируется в имитационных моделях.}

^{2.Если бы я использовал bsearch вместо bsearch_index, мне пришлось бы раньше создать хеш с cdf=>name парами ключ-значение, чтобы получить имя для данного случайно выбранного значения CDF.}

Answer 2

Это мое решение проблемы:

array = [["name1", 33],["name2", 20],["name3",10],["name4",7],["name5", 30]]

def random_name(array)
  random_number = rand(0.000..100.000) 
  sum = 0

array.each do |x|
  if random_number.between?(sum, sum + x[1])
    return x[0]
  else
    sum += x[1]
  end
end
end

puts random_name(array)

Answer 3

Несмотря на то, что мне нравится ответ @Stefan больше, чем мой, я внесу возможное решение: я бы распределил все свои проценты по 100.0 так, чтобы они начинались с 0.0 и заканчивались до 100.0.Представьте, что у меня есть массив со следующими процентами:

a = [10.5, 20.5, 17.8, 51.2]

, где

a.sum = 100.0

Мы могли бы написать следующее, чтобы распределить их по 100.0:

sum = 0.0
b = a.map { |el| sum += el }

ирезультат будет

b = [10.5, 31.0, 48.8, 100.0]

, теперь я могу сгенерировать случайное число от 0,0 до 100,0:

r = rand(0.0..100.0) # or r = rand * 100.0

представьте, что r равно 45.32.

Я выбираюпервый элемент b, то есть> = r`

idx = b.index { |el| el >= r }

, который в нашем случае вернул бы 2.

Теперь вы можете выбрать a[idx].

Но я бы тоже ответил с @Stefan :) 1030 *

Answer 4

Вы можете использовать max_by: (документы содержат аналогичный пример)

array.max_by { |_, weight| rand ** 1.fdiv(weight) }

Это предполагает, что ваши веса являются фактическими процентами, то есть 3,1% должны быть выражены как0.031.Или, если вы не хотите корректировать свои веса:

array.max_by { |_, weight| rand ** 100.fdiv(weight) }

Я использую fdiv здесь для учета возможных целочисленных значений.Если ваш вес всегда плавает, вы также можете использовать /.