访问一个不完整数组的随机索引？

我有一个数组，它可以有几十万行的最大长度。它看起来像这样：访问一个不完整数组的随机索引？

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);

但它是相当缓慢的。

有没有更好的方法来做到这一点？

泰

来源

2011-06-09 mrwooster

'arr'确实是一个数组还是一个对象？ 'for..in'比''正常''循环慢几倍。 – 2011-06-09 09:45:11

它是作为一个数组构建的，但不确定JavaScript是否会将它内部地转化为对象。＃ – mrwooster 2011-06-09 09:56:00

如果将它定义为数组，那么它将是一个数组;为什么数组不完整？也许使用其他数据结构可能会更好... – 2011-06-09 09:57:12

如果缺少元素的比例是非常小这将是速度不够快，只是生成随机指标，直到你得到一个打击。试一试。

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

来源

2011-06-09 09:45:52

如果我们有10000个缺陷和1个真实情况会发生什么？：D – bezmax 2011-06-09 09:47:16

然后他注定要继续使用他当前的代码。 – 2011-06-09 09:48:32

另外，如果您在索引中存在巨大差距，会发生什么情况。 – Petah 2011-06-09 09:48:42

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

它快，如果有很多trues的和缓慢的，如果有很多falses，但至少它快那么你的解决方案

来源

2011-06-09 09:48:25 GeertvdC

我认为'candidate.length'在这里是错误的。它看起来很像@Jeremy已经发布的内容。 – 2011-06-09 09:51:02

是的，它看起来几乎一样..当我写我的帖子时，还没有答案。也@Jeremy返回数组[index]的值，而不是索引。 – GeertvdC 2011-06-09 09:52:55

对于稀疏数组也很慢：'var arr = []; arr [10000000] = true;' – Petah 2011-06-09 09:55:46

据我所知，有没有漂亮的方式来做到这一点。

我会尝试使用的是，当你用true/false元素填充数组时，将一个真正值的索引推到一个辅助结构上。之后，生成这些值的随机应该很容易，你一定会得到该指数的真实值。

来源

2011-06-09 09:50:37 seth

你最好的解决办法为这个阵列中创建另一个指标：

每次修改这个数组，你重建所有true值的索引一些true_values阵列。例如：

function addNewIndex(key, value) { 
    arr[key] = value; 
    if (value) { 
     true_arr.push(key); //<<<< 
    } 
}

然后只需从您构建的索引中选择随机元素。

来源

2011-06-09 09:52:12 bezmax

是的，我希望能够这样做，但是如果我需要将索引xxx从true更改为false，该怎么办？我将无法直接在true_arr中访问它... – mrwooster 2011-06-09 09:59:06

如果这个数组将会不断变化，并且它非常大，并且如果true元素的数量可能非常少，那么保持True索引列表又如何？

当索引变为true时，它被添加到列表中，当索引设置为false时，它将从列表中删除，然后您可以通过从true列表中选择一个随机元素来选择索引索引。

来源

2011-06-09 09:56:31

访问一个不完整数组的随机索引？

回答

相关问题