纯 javascript 中的延迟赋值

Question

在this question中我遇到了以下简化的问题：

我们从一组具有值属性的对象开始。我们要计算每个值占值总和的百分比，并将其作为属性添加到结构中。为此，我们需要知道值的总和，但这个总和并不是事先计算出来的。

//Original data structure
[
  { "value" : 123456 },
  { "value" : 12146  }
]

//Becomes
[
  { 
    "value" : 123456,
    "perc"  : 0.9104
  },
  {
    "value" : 12146 ,
    "perc"  : 0.0896
  }
]

一个简单且可能最易读的解决方案是遍历数据结构两次。首先我们计算总和，然后计算百分比并将其添加到数据结构中。

var i;
var sum = 0;
for( i = 0; i < data.length; i++ ) {
  sum += data[i].value;
}
for( i = 0; i < data.length; i++ ) {
  data[i].perc = data[i].value / sum;
}

我们能否改为只遍历一次数据结构，并以某种方式告诉我们只有在知道整个总和后才应计算百分比表达式？

我主要对解决纯粹 javascript 的答案感兴趣。即：没有任何库。

Answer 1

根据我的评论，如果不有效地循环两次，我无法找到执行此操作的方法。

实际计算值
根据总数评估每个值

要回答问题的 "deferred" 部分，一种可能的解决方案，尽管速度较慢（只是由于函数调用而猜测？）并且可能不是您想要使用的 (JSFiddle)：

var data = [
  { value: 10 },
  { value: 20 },
  { value: 20 },
  { value: 50 }
];

var total = 0;

for (var i = 0; i < data.length; i++) {
  var current = data[i];
  total += current["value"];
  current.getPercent = function() { return this["value"] / total; };
}

for (var i = 0; i < data.length; i++) {
  var current = data[i];
  console.log(current.getPercent());
}

输出：

0.1
0.2
0.2
0.5

这有一个额外的好处，即在您需要它之前不会实际计算该值，但是当它计算它时，将会有更高的 cpu 成本（由于调用函数等）。

这可以通过将 getPercent 行更改为：

来略微优化

current.getPercent = function() { 
    return this["percent"] || (this["percent"] = this["value"] / total);
}

这将确保计算只是运行第一次。 Updated Fiddle

编辑我运行一些测试（由于测试太多迭代而崩溃 chrome 之前忘记保存，但它们很简单，可以复制）。我得到

Sumurai 初始方法（1000000 个值为 0 的对象 -> 9999999）= 2200ms
我的初始方法（相同）= 3800ms
我的"optimised"方法（相同）=4200ms

Answer 2

一种减少循环的方法是写出由所有可能项组成的整个求和语句，例如

var sum = (data[0] ? data[0].value : 0) +
          (data[1] ? data[1].value : 0) +
          (data[2] ? data[2].value : 0) +
          ...
          (data[50] ? data[50].value : 0);

for( i = 0; i < data.length; i++ ) {
   data[i].perc = data[i].value / sum;
}

并不是说这实际上是一个真正的解决方案

您可以使用 Array 的 reduce 函数，但这仍然是后台循环，并且每个数组元素都有一个函数调用：

var sum = data.reduce(function(output,item){
   return output+item.value;
},0);
for( i = 0; i < data.length; i++ ) {
  data[i].perc = data[i].value / sum;
}

你可以使用 ES6 Promise，但你仍然添加了一堆函数调用

var data = [
  { "value" : 123456 },
  { "value" : 12146  }
]
var sum = 0;
var rej = null;
var res = null;
var def = new Promise(function(resolve,reject){
    rej = reject;
    res = resolve;
});
function perc(total){
    this.perc = this.value/total;
}

for( i = 0; i < data.length; i++ ) {
  def.then(perc.bind(data[i]));
  sum+=data[i].value;      
}
res(sum);

Perf Tests

Addition statement
10,834,196
±0.44%
fastest

Reduce
3,552,539
±1.95%
67% slower

Promise
26,325
±8.14%
100% slower

For loops
9,640,800
±0.45%
11% slower

Answer 3

再看一下问题，使用堆栈最容易重现所需的效果。最简单的方法是创建递归函数而不是循环。递归函数会起到一个循环的作用，可以使用destacking来设置百分比属性.

/**
 * Helper function for addPercentage
 * @param arr Array of data objects
 * @param index
 * @param sum
 * @return {number} sum
 */
function deferredAddPercentage(arr, index, sum) {
  //Out of bounds
  if (index >= arr.length) {
    return sum;
  }

  //Pushing the stack
  sum = deferredAddPercentage(arr, index + 1, sum + arr[index].value);

  //Popping the stack
  arr[index].percentage = arr[index].value / sum;

  return sum;
}

/**
 * Adds the percentage property to each contained object
 * @param arr Array of data Objects
 */
function addPercentage(arr) {
  deferredAddPercentage(arr, 0, 0);
}


// ******

var data = [{
  "value": 10
}, {
  "value": 20
}, {
  "value": 20
}, {
  "value": 50
}];

addPercentage(data);

console.log( data );

它的性能比 2 个简单的 for-loops 差 29%。扩展 Patrick 的 JSPerf.

Answer 4

self-modifying code 的解决方案。

它将用于计算的函数f移动到迭代的末尾，然后它通过链式函数来分配单个项目的百分比。

var data = [
        { "value": 123456 },
        { "value": 12146 },
    ];

data.reduceRight(function (f, a, i) { // reduceRight, i=0 is at the end of reduce required
    var t = f;                        // temporary save previous value or function
    f = function (s) {                // get a new function with sum as parameter
        a.perc = a.value / s;         // do the needed calc with sum at the end of reduce
        t && t(s);                    // test & call the old func with sum as parameter
    };
    f.s = (t.s || 0) + a.value;       // add value to sum and save sum in a property of f
    i || f(f.s);                      // at the last iteration call f with sum as parameter
    return f;                         // return the function
}, 0);                                // start w/ a value w/ a prop (undef/null don't work)

document.write('<pre>' + JSON.stringify(data, 0, 4) + '</pre>');

Answer 5

此解决方案使用单个循环来计算总和，并使用 getter:

在每个元素上放置计算的 perc 属性

function add_percentage(arr) {
  var sum = 0;
  arr.forEach(e => {
    sum += e.value;
    Object.defineProperty(e, "perc", {
       get: function() { return this.value / sum; }
    });
  });
}

直接推迟就是

function add_percentage(arr) {
  var sum = 0;
  arr.forEach(e => {
    sum += e.value;
    setTimeout(() => e.perc = e.value / sum);
  });
}

但是，这样做到底有什么意义呢？

Answer 6

OP 已经给出了。虽然我相信非尾递归函数是完成这项任务的理想方法，但我认为它们的实现有两个缺点：

它会改变其父作用域的状态
它非常具体，因此很难重复使用

我试图在不改变全局状态的情况下实现更通用的解决方案。请注意，我通常会通过组合几个较小的、可重用的函数来解决这个问题。然而，OP 的条件是只有一个循环。 这是一个有趣的挑战，我的实现并不是为了在实际代码中使用！

我调用函数defmap即延迟映射：

const xs = [
  { "value" : 10 },
  { "value" : 20 },
  { "value" : 20 },
  { "value" : 50 }
];

const defmap = red => map => acc => xs => {
  let next = (len, acc, [head, ...tail]) => {
    map = tail.length
     ? next(len, red(acc, head), tail)
     : map([], red(acc, head), len);
    
    return map(Object.assign({}, head));
  };

  return next(xs.length, acc, xs);
};

const map = f => (xs, acc, len) => o => xs.length + 1 < len
 ? map(f) (append(f(o, acc), xs), acc, len)
 : append(f(o, acc), xs);

const append = (xs, ys) => [xs].concat(ys);

const reducer = (acc, o) => acc + o.value;
const mapper = (o, acc) => Object.assign(o, {perc: o.value / acc});

console.log(defmap(reducer) (map(mapper)) (0) (xs));

纯 javascript 中的延迟赋值

Deferred assignment in pure javascript

javascript

deferred-execution