javascript - 并行计算方差

Question

我正在尝试实现 variance 的并行计算在 JavaScript 中使用 MapReduce。我相信这 Parallel algorithm可以使用，但我不知道如何将它应用于任意数量的数据集。到目前为止，我得出的结论是，解决该问题的最佳方法是根据平方和进行归约，而不是根据方差进行归约。一个天真的实现看起来像这样:

// partials is an array of [count, sum, sumsquare] arrays
function variance(partials) {
  var count = 0;
  var sum = 0;
  var sumsquare = 0;
  for (var i = 0; i < partials.length; ++i) {
    count += partials[i][0];
    sum += partials[i][1];
    sumsquare += partials[i][2];
  }
  return (sumsquare / count) - Math.pow(sum / count, 2);
}

// variance([[3, 6, 14], [3, 15, 77], [3, 24, 194]]) should return 6.666666666666668

不是统计学家，我很难弄清楚这样的并行算法是否会引入太多的复合错误。但是如果可以接受的话，值得注意的是在map阶段不需要计算方差。只需要平方和、sum 和 count。

Answer 1

我不确定我是否清楚地理解您所说的reduce 函数将为映射到一组 worker 。不过，根据您截取的代码，我会使用类似的东西:

Array.sums = function (arr, addarr) {
   var newarr = [0,0,0];
   if (addarr.length === arr.length) {
      arr.forEach( function (v,i) {
        newarr[i] = v + addarr[i];
      });
   }
   return newarr;
}
    
function variance(arr) {
  var summations = arr[0].map(function () {return 0;});
  arr.forEach(function (v){
   summations = Array.sums(v, summations);
  });
  summations.unshift( (summations[2] / summations[0]) -
                      Math.pow(summations[1] / summations[0], 2) );
  // summations is now a quadruplet containing [variance, count, sum, sumsquare]
  return summations;
}

alert( variance([[3, 6, 14], [3, 15, 77], [3, 24, 194]])[0] );