在没有循环的情况下执行随机抽签吗？

Question

以下是伪代码。

float totalStakes = 0；float[] participantStakes[]；

int EnterDraw(float _stakes) {
    totalStakes += _stakes;
    participantStakes.push(_stakes);
    return participantStakes.length - 1;
}

int SelectWinner() {
    float rnd = Random(0, totalStakes);
    float sum = 0;
    for(int i=0; i<participantStakes.length; i++) {
        sum += participantStakes[i];
        if (rnd <= sum) {
            return i;
        }
    }
}

bool DidIWin(int _participantID) {
    return (SelectWinner() == i);
}

这个伪代码运行抽奖，参与者有不同的中奖概率。我的问题是，是否有任何方法可以实现这一点，而不必潜在地迭代所有元素？

重要提示:只有在所有参与者都参与抽奖后，才会生成随机数。

Answer 1

我同意这样的评论，如果你只存储赌注的计数，你就无法避免在数组中循环，我的回答是基于@juvian的评论。

我没有在数组中存储赌注数量，而是存储了每个参与者的索引范围。这样就不需要依赖数组的其他元素中的值了。从那里进行二进制搜索以找到获胜的索引。

搜索中的一个调整是，它从相对于获胜赌注价值的位置开始到总赌注，而不是绝对中点。因此，对于正态分布的数据集，这应该会执行得更好。

int EnterDraw(float _stakes) {
    totalStakes += _stakes;
    min = (pStakes.length > 0) ? pStakes[pStakes.length - 1].cutoff : 0;
    cutoff = min + _stakes;
    pStakes.push({ min, cutoff });
    return pStakes.length - 1;
}

int SelectWinner() {
    float rnd = Random(0, totalStakes);
    int i = floor(pStakes.length * rnd / totalStakes);
    int high = totalStakes - 1;
    int low = 0;
    while (!(pStakes[i].min <= rnd && pStakes[i].max > rnd) {
      if (pStakes[i].min > rnd) {
        high = i - 1;
        i = floor((i - low) / 2) + low;
      }
      else {
        low = i + 1;
        i = floor((high - i) / 2) + low;
      }
    }
    return i;
}