在巨大向量和大多数权重等于零的情况下高效使用 Octave 的 randsample（带权重）

Question

在即将进行的模拟项目中，我会遇到这样一种情况，我必须在加权意义上从一个巨大的向量中抽取一个随机元素。对于向量的大多数元素，分配的权重将为零。我也只需要绘制一个元素，所以替换或不替换功能是无关紧要的。

这个随机选择步骤将成为我模拟的瓶颈，因此获得最佳效率和速度将是至关重要的。

有没有什么是最好的hacks/tips？在我的项目中是否有任何重要的节约可能？

PS: randsample 在大向量上可靠吗？

Answer 1

查看统计包中randsample.m的源代码。这实际上是一个非常简单的实现。它从权重向量创建归一化的累积权重向量，然后通过标准逆采样对其进行有效采样。

我不知道你所说的 'huge' 是什么意思，但只要权重向量可以放入内存，就没有理由不快。

如果 'huge' 你的意思是一些不适合内存的东西，那么你可以创建一个 'huge version' 这个函数，将累积权重向量拆分成可预测的 'bins' 保存在disk, 并且只从右 bin 执行逆采样。

我唯一要补充的是，考虑到实现并且您只对一次抽奖感兴趣，那么如果将 'replacement' 指定为 [=28，您可能会受益于速度=] 明确地，因为默认是 'false' （即 without replacement），并且采样 with replacement 似乎避免了很多不必要的和昂贵的步骤（排列等）。

Answer 2

知道大多数权重等于零，您可以从 Octave 源代码重写 randsample 的更快实现。在我的时间里，它比原来的实现快 6X-7X：

function y = randsample_fast(v, w)
    f = find(w);
    w = w(f);
    w = w / sum(w);
    w = [0 cumsum(w)];
    y = f(lookup (w , rand));
    %y = f(find (w <= rand, 1, "last"));
    y = v(y);
end

假定输入为行向量。
将 find 更改为 lookup 可能会略微提高性能。

在巨大向量和大多数权重等于零的情况下高效使用 Octave 的 randsample（带权重）

Efficient use of Octave's randsample (with weights) in a situation of huge vector and most weights equal to zero

random

octave