javascript - 访问不完整数组的随机索引？

Question

我有一个最大长度为几十万行的数组。它看起来像这样:

arr[12]   = false
arr[334]  = true
arr[753]  = true
arr[1001] = false
arr[1222] = true

等等……

我想找到最快的方法来随机选择为真的行的索引...

我最初的尝试是这样做的:

for(k in arr) {
 if(arr[k]) {
  candidate.push(k);
 }
}

return Math.floor(Math.random() * candidate.length);

但是速度很慢。

有更好的方法吗？

我

Answer 1

如果缺失元素的比例足够小，它将足够快地生成随机索引，直到你被命中。试一试。

var chose_true = function(array) {
    while (true) {
        var index = Math.floor(Math.random() * array.length)
        if (array[index]) {
            return array[index];
        }
    }
}