4

我编写了一个算法来使用广度优先搜索来解决N-puzzle问题。为了让事情变得更快，我决定预先分配一个大数组，而不是重复地将值推送和移动到一个空数组。

偶然我注意到一个奇怪的行为，即两次分配大数组实际上使挂钟时间更快。我用完整的代码创建了一个要点，但是给我奇怪行为的部分在这里：

var values = new Array(1000000);

function breadthFirstSearch(state, goalState) {
  values = new Array(1000000);
  // implementation of a breadth first search for the n-puzzle problem
}

在我的机器上，使用 node.js 初始化两次值的典型运行时间约为 550 毫秒。当我注释掉我实例化值的地方之一时，我只实例化它一次，运行时间增加到大约 650 毫秒 - 700 毫秒。在我看来，当只分配一次数组时，运行时间应该会减少。我制作了一个视频来解释我在做什么，并在此处显示我的机器上的运行时间。

奇怪的是，当我在repl.it上运行它时，无论是否被注释掉，运行时都差不多，这让我觉得它与 v8 引擎有关。

谁能给我一个解释，为什么在做应该少做的工作时挂钟时间会增加？

4

1 回答 1

3

我已经在评论中写下了这个答案的大部分内容，因为在撰写这些评论时，这个问题被锁定了。

我用更好的时间测量调用扩展了原始代码，这些调用performance.now在现代浏览器中可用或作为节点模块使用performance-now。代码作为这个 gist上传。

我改变了什么：

  1. 添加function init()，它（重新）初始化所有全局变量，否则程序将无法在多次运行中运行。

  2. 复制function breadthFirstSearch到breadthFirstSearchUncommentedand中，第一个在每次调用时breadthFirstSearchCommented初始化，第二个按原样使用全局变量，即前面提到的语句被注释/删除。values = new Array(1000000);values

  3. 修改function time为接受应该使用哪个 BFS 函数。

  4. 添加了function measureTime，它time使用给定的 BFS 函数参数调用并测量runs（参数）测量的最小值、最大值和平均值。最后，它输出总时间（所有time调用的时间总和）。这个函数的代码在下面，当然在index.js文件末尾。

  5. 删除添加日志消息，只剩下日志消息是每次measureTime通话的开始和结束。

功能measureTime：

function measureTime(bfsFn, label, runs) {
  console.log('starting', runs, 'measures for', label);
  var diff = 0;
  var min = Number.MAX_VALUE, max = Number.MIN_VALUE;
  for (var i = 0; i < runs; i++) {
    init();
    var start = now();
    time(bfsFn);
    var d = now() - start;
    diff += d;
    min = Math.min(d, min);
    max = Math.max(d, max);
  }
  var avg = diff / runs;
  console.log('%s - total time for %d measures: %sms', label, runs, diff.toFixed(3));
  console.log('%s - avg time: %sms (%sms - %sms, Δt = %sms)',
    label, avg.toFixed(3), min.toFixed(3), max.toFixed(3), (max - min).toFixed(3));
}

实际答案：问题是为什么程序定义新数组两次，即在开始时一次，在每个 BFS 函数调用时一次，比初始化代码被注释时更快。

答案是对此没有任何解释。这不是 JavaScript VM 工作方式的结果，也不是任何 JavaScript 怪癖，它更简单：有问题的陈述实际上是错误的。

OP 所说的，后来甚至还提供了视频解释，仅适用于单次运行。最重要的原因是，众所周知，现代操作系统正在同时进行大量工作——我知道这并不完全正确，但为了这个解释，请耐心等待。这意味着在多次运行中很难获得完全相同的运行时间，因此我们看到多次运行之间的执行时间有些波动。

为了获得更准确的测量结果，我measureTime为每个注释的函数调用了 100 次，为未注释的函数调用了另外 100 次。这创建了一个最小化波动的样本。

我为不同的执行环境创建了比较表。所有测试均在 OS X Yosemite 上运行，使用截至 2015 年 6 月 18 日的最新稳定版本的浏览器和 io.js。

|   Environment   |  Uncommented time [ms]  |  Commented time [ms]  |
| :-------------- | :---------------------- | :-------------------- |
| Chrome          |         460.254         |        424.725        |
| Firefox         |         796.471         |        781.662        |
| Safari          |         529.492         |        474.580        |
| Node.js (io.js) |         411.804         |        394.807        |

这是我能做的最好的表格，因为 Stack Overflow 不支持表格降价。有关实际的表格样式，请查看gist。

在这个表中，很明显，原始语句表示未注释数组重新初始化的代码更快，因为我们可以看到这对于我测试的所有四个环境都是错误的。

这里要吸取的教训是不要仅根据几次运行就得出性能结论。应收集多次测试运行的数据并将其解释为所有值的平均值，或者在某些情况下，应使用更复杂的统计方法以获得更准确的结果。

于 2015-06-18T04:00:30.003 回答