3

设计一种快速算法，从离散分布中重复生成数字：给定一个数组 a[]，其中包含总和为 1 的非负实数，目标是以概率 a[i] 返回索引 i

我在一本在线算法书籍《Java 编程简介》第 4.2 章：排序和搜索 (http://introcs.cs.princeton.edu/java/42sort/) 中发现了这个问题。

提示说：

形成一个累加和的数组 s[]，使得 s[i] 是 a[] 的前 i 个元素的和。现在，生成一个介于 0 和 1 之间的随机实数 r，并使用二进制搜索返回 s[i] ≤ s[i+1] 的索引 i。

有些我无法理解提示，因此无法找到解决方案..

4

4 回答 4

8

有很多方法可以回答这个问题。 本文介绍了许多方法、它们的优势、劣势和运行时间。它以一个算法结束，该算法需要 O(n) 预处理时间，然后在每个 O(1) 时间内生成数字。

您正在寻找的特定方法在“轮盘赌选择”下进行了描述。

希望这可以帮助！

于 2012-04-08T16:31:46.410 回答
2

这是一个实现“轮盘赌”技术的 Python 算法。没有图形很难解释。由 templatetypedef 链接的文章应该可以很好地解决这个问题。另外，请注意，该算法实际上并不需要对权重进行归一化（它们不需要总和为 1），但这仍然有效。

import random

trials = 50
selected_indices = []

# weights on each index
distrib = [0.1, 0.4, 0.2, 0.3]

index = random.randrange(0, len(distrib) - 1)
max_weight = max(distrib)
B = 0
# generate 'trials' random indices
for i in range (trials):

    # increase B by a factor which is
    # guaranteed to be much larger than our largest weight
    B = B + random.uniform(0, 2 * max_weight)

    # continue stepping through wheel until B lands 'within' a weight
    while(B > distrib[index]):
        B = B - distrib[index]
        index = (index + 1) % len(distrib)
    selected_indices.append(index)

print("Randomly selected indices from {0} trials".format(trials))
print(selected_indices)
于 2012-04-08T19:45:59.263 回答
0

这是 wakkerbot/megahal 的一个片段。这里的权重是（无符号的）整数，它们的总和在 node->childsum 中。为了获得最大速度，孩子按降序（或多或少）排序。（权重预计具有类似幂律的分布，只有少数高权重和许多较小的权重）

    /*
     *          Choose a symbol at random from this context.
     *          weighted by ->thevalue
     */
    credit = urnd( node->childsum );
    for(cidx=0; 1; cidx = (cidx+1) % node->branch) {
        symbol = node->children[cidx].ptr->symbol;
        if (credit < node->children[cidx].ptr->thevalue) break;
        /* 20120203 if (node->children[cidx].ptr->thevalue == 0) credit--; */
        credit -= node->children[cidx].ptr->thevalue;
    }
done:
    // fprintf(stderr, "{+%u}", symbol );
    return symbol;
于 2012-04-08T16:49:27.353 回答
0

根据粒度，您可以创建包含 100、1000 或 10000 个元素的索引。假设分布 (a,b,c,d) 且 p=(10%, 20%, 30%, 40%)，我们创建一个 Map：

val prob = Map ('a' -> 10, 'b' -> 20, 'c' -> 30, 'd' -> 40) 
val index = (for (e <- prob;
  i <- (1 to e._2)) yield e._1 ).toList 

index: List[Char] = List(a, a, a, a, a, a, a, a, a, a, 
b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, 
c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, 
d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d)

我们现在可以非常快速地选择所需概率的元素：

val x = index (random.nextInt (100))

x 现在是 40% d，10% a，依此类推。设置短，访问速度快。

这些数字甚至不需要总和为 100，但您必须计算一次范围，然后：

val max = prob.map (_._2).sum 
val x = index (random.nextInt (max))
于 2012-04-08T17:35:46.317 回答