最大化此同时循环的效率

Question

我有一个while循环，应该在二维中随机种植数字真实值。我只在它们不是真的时才改变它们，并且只在真理次数上这样做：

function truthfulArray(maxY, maxX, numberOfTruths, array) {
var x;
var y;
var counter = 0;
while (counter < numberOfTruths) {
x = generateRandomNumber(maxX);
y = generateRandomNumber(maxY);
if (!array[x][y]) {
array[x][y] = true;
counter++;
}
}
return array;
}

我可以看到它与二维数组大小相关的优化问题，并且当 numberOfTruths 接近 maxY 和 maxX 的乘积时，它会浪费大量资源来完成任务。我想知道我可以对功能进行哪些调整以使其更有效率。提前感谢！

generateRandomNumber(max)是一个简单的函数，它返回一个从 0 到输入的最大值的随机数。

Answer 1

根据@Bergi的评论，这里有一个优化。它假设数组一开始是空的(或者更确切地说，它不在乎，只是覆盖东西(。

当填充因子 (N / (X * Y)( 较低时，它的速度较慢(使用 X = Y = 500 进行测试(，但似乎在大约 40% 时胜过原始实现，并且在 80% 时决定性地更快(如 3x(。(您可能希望将其用作启发式方法。

一般的想法是，我们首先从行的开头填充随机行，然后使用 Fisher-Yates shuffle 展开每一行。我将y和x与原始版本进行了转换，因为这正是我习惯于处理 2D 数组的方式。:D

function shuffle(array) {  // h/t https://bost.ocks.org/mike/shuffle/
var m = array.length, t, i;
while (m) {
i = Math.floor(Math.random() * m--);
t = array[m];
array[m] = array[i];
array[i] = t;
}
return array;
}
function truthfulArrayFillRows(maxY, maxX, numberOfTruths, array) {
var nLeft = numberOfTruths;
var nSeededPerRow = new Array(maxY).fill(0);
// Seed rows randomly with trues starting from the left
while(nLeft > 0) {
var y = generateRandomNumber(maxY);
var x = nSeededPerRow[y];
if(x < maxX) {
array[y][x] = true;
nLeft --;
nSeededPerRow[y] ++;
}
}
// Shuffle the rows we seeded
for(var y = 0; y < maxY; y++) {
if(nSeededPerRow[y] > 0) {
shuffle(array[y]);
}
}
return array;
}

Answer 2

您可以随机选择numberOfTruth许多有效仓位，而不是随机选择所有可能仓位numberOfTruth多个仓位。为此，您必须先找到这些位置。

function shuffle(a) {
var j, x, i;
for (i = a.length - 1; i > 0; i--) {
j = Math.floor(Math.random() * (i + 1));
x = a[i];
a[i] = a[j];
a[j] = x;
}
return a;
}
function chunkArray(myArray, chunk_size){
var results = [];
while (myArray.length) {
results.push(myArray.splice(0, chunk_size));
}    
return results;
}
function flatten(array) {
var flattened=[];
for (var i=0; i<array.length; ++i) {
var current = array[i];
for (var j=0; j<current.length; ++j)
flattened.push(current[j]);
}
return flattened;
}
function truthfulArray(maxY, maxX, numberOfTruths, array){
var flatArray = flatten(array);
var validPositions = flatArray.map(function(e, i){if(!e) return i});
var randomPositions = shuffle(validPositions).slice(0, numberOfTruths);
randomPositions.forEach(function(i){flatArray[i] = true;});
return chunkArray(flatArray, maxY);
}

var maxX = 20, maxY = 30;
var array = Array(maxX).fill(Array(maxY).fill(false));
truthfulArray(maxY, maxX, 40, array);

此方法是否更有效取决于您的数据。如果有许多有效的位置可供选择，您的代码应该完全精细且高效。数组中的true越多，您的代码(随机(命中它们的可能性就越小。在这种情况下，我描述的方法将更有效。 我希望你觉得有帮助。