时间戳

首页 > 解决方案 > 最大化这个while循环的效率

javascript - 最大化这个while循环的效率

问题描述

我有一个 while 循环，它应该在二维中随机植入 numberOfTruth 真值。如果它们不是真的，我只会更改它们，并且只在 numberOfTruths 次这样做：

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 到输入的最大值的随机数。

标签： javascriptoptimizationwhile-loop

解决方案

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

当填充因子 ( N / (X * Y)) 较低时（使用 X = Y = 500 进行测试），它会变慢，但似乎在 40% 左右胜过原始实现，并且在 80% 时明显更快（如 3 倍）。（您可能希望将其用作启发式方法。）

一般的想法是，我们首先从行的开头填充随机行，然后使用 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;
}

推荐阅读