Cumsum直到阈值

Question

我想知道是否有一种快速的方法来不断求和一个元素，直到找到一个阈值。

例如

threshold=100;
a=0; MAX=1000;
for i=1:MAX
    a=a+normrnd(2,1,1,1);
    if (a>threshold)
      index=i; break;
     end 
 end

这个很好，但速度很慢。卡姆苏姆在这里会很有用。不过，在这种情况下，我唯一知道使用累积和的方法是：

a=cumsum(normrnd(2,1, MAX,1)); 
index=find(a>threshold,1);

随着最大值的增加而变得越来越低效。

因此，基本上，我正在寻找一个累积求和方法，保持累积和的速度，但这允许我设置一个阈值。有什么想法吗？谢谢

Answer 1

基本上，这个解决方案结合了您的两个解决方案，它在大小为1000的段上迭代，并使用累积和解决方案同时处理1000个元素。

threshold=100;
a=0; MAX=9999999;
%segment size
S=1000;
for segment_start=1:S:MAX
    %process segment from _start to _end
    segment_end=min(segment_start+S-1,MAX);
    %which contains _count elements
    segment_count=segment_end-segment_start+1;
    %now use the cumsum solution to process the segment
    c=normrnd(2,1,segment_count,1);
    c=cumsum(c);
    index=find(c>threshold-a,1,'first');
    if isempty(index)
        %need to continue
        a=a+c(end);
    else
        %threshhold reached, found solution
        a=a+c(index);
        break;
    end

end

Answer 2

您可以使用二进制搜索。如果您的元素是具有已知分布的随机变量，或者至少是已知的期望值，那么您可以进行良好的初始猜测。

在您已经发布的例子中，我们有这个E[normrnd(2,1,1,1)] = 2，从threshold = 100开始，您首先生成50个数字并对它们进行求和。如果估计过高，则使用二进制搜索搜索正确的索引。如果你低估了，那么你就用你低估的数量来做一个新的猜测，然后继续这样做，直到你高估为止。