Deferred assignment in pure javascript

Question

In this question I encountered the following simplified problem:

We start with an array of Objects with a value attribute. We want to calculate for each value what percentage of the sum of values it is, and add it to the structure as a property. To do this, we need to know the sum of values, but this sum is not calculated beforehand.

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

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

---

An easy, and probably most readable, solution is to go through the data structure twice. First we calculate the sum, then we calculate the percentage and add it to the data structure.

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;
}

---

Can we instead just go through the data structure once, and somehow tell that the percentage expression should only be evaluated once the entire sum is known?

I am primarily interested in answers that address pure javascript. That is: Without any libraries.

Tortilla

I would think of it from a physical aspect. If I give you x apples from a cart, how can you tell me what % of apples you have? You need to go and count all the objects before you can make this calculation. I personally can not see a different way of achieving this. – Martyrology

@Martyrology It is impossible to do it with less actions. That is, I need at least to read n values and write n values. I am just curious if there is a certain syntax or construct that allows me to defer assignment of the percentage until the sum is known by, possibly, putting something in the first loop. – Tortilla

Why are you interested in doing this? Is it a mental exercise? – Salinasalinas

@torazaburo It is more or less a mental exercise. There are probably applications where going through the data is more expensive than this for-loop, or in which it is not critical (or ever needed) to have that property set right away. I knew it should be possible, I just wasn't sure how, or how efficient such a solution would be. – Tortilla

The default in SO is that unless a library such as jQuery is specified in the question (or the tags), a non-jQuery solution is expected, no real need to call this out specifically. – Salinasalinas

I know. And the majority of people don't know that's in the tag description, and will reply with "in library x or y this is easy". So I just put it in the question. Saves me downvoting answers. – Tortilla

Answer 1

A way to make this with one less loop is to write out the whole sum statement made up of all possible items, for instance

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;
}

Not that this is actually a real solution

You could use Array's reduce function but that is still a loop in the background, and a function call for each array element:

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;
}

You could use the ES6 Promise, but there you are still adding a bunch of function calls

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

Oatcake

I don't think unrolling the loop counts as a solution. – Cagle

That promise thing is kinda neat, only it is unnecessarily asynchronous. .perc can only be used asynchronously, and should be a promise itself. Btw, please don't call promise variables def, and avoid rej and res variable - just place the code that is responsible for resolving the promise inside the Promise constructor callback. – Cagle

Nor do I, I just included it as it was the only thing that I could think of that would make it have 1 less loop – Oatcake

I was surprised at the performance of Reduce, until I saw that you were doing string operations instead of calculating a sum ;-) It should be item.value, making it about 62% slower. jsperf.com/loops-perfomrace/5 – Tortilla

Opps yea messed it up, will fix – Oatcake

@torazaburo, the for loop adds a then callback for each array object, that object also being bound as the execution context. When the promise is resolved, each then callback will be called in turn calculating and setting the percentage for the bound object – Oatcake

There is no reason why res and rej need to be global though. Moving the for-loop into the function and calling res there should do the same. – Tortilla

@Sumurai8, yes the work should be in the callback passed to the constructor, but since you cannot access the .then method from there I just moved the resolve function outside, I really didnt spend much time making the promise solution, hence why its not very optimized – Oatcake

Answer 2

A solution with self-modifying code.

It moves the function f for the calculation to the end of the iteration and then it goes through the chained functions for the assignments of the percentage of the single items.

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>');

Shekinah

I'm sorry to spoil the party but, it is a disguised double for loop, hard to read, with a bigger memory footprint, and it makes a debatable use of properties. In spite of it all, it's an interesting answer, but I think there is too much approval here :-/ – Bikales

@procrastinator, it was just to show what's possible, without stressing footprint, memory or other performance questions. – Shekinah

I understand the idea, but it goes through the data structure twice actually, which is what the op wanted to avoid. Since it's just another form of double for loop, I don't think that it deserves this amount of upvotes, which can be misleading for a beginner. – Bikales

@procrastinator, of course it goes twice, otherwise it would not work -- nowhere. even if you take the answer of torazaburo for example, the second loop is deferred to the max, at the request of the property. – Shekinah

I know it has to go twice, your solution is correct from this point of view. What makes me react this way is the amount of upvotes. In my opinion Torazaburo is closer to the point, though his answer does not raise such an enthusiasm. Looks weird to me, and above all, misleading :-/ – Bikales

This is cool for an obfuscation contest, but after going through the code I felt a bit disappointed. There is little about this code you could call "self-modifying code", unless you consider closures to be "self-modifying code"? If there was an eval somewhere inside, perhaps. But this is just a rather convoluted way to calculate the sum in a loop (btw, forEach would be more appropriate and less convoluted than reduceRight) and push individual values into an implicit stack to run the recursion, which is also redundant since you already have the array in the first place. – Bybidder

Answer 3

This solution uses a single loop to calculate the sum and place a computed perc property on each element using a getter:

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

A straightforward deferral would just be

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

But, what is the point of doing this exactly?

Salinasalinas

Answer 4

Looking at the problem some more, the desired effect is most easily reproduced using a stack. The easiest way of doing that here is by creating a recursive function instead of a loop. The recursive function will act as a loop, and the destacking can be used to set the percentage property.

/**
 * 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 );

It will perform 29% worse than 2 simple for-loops. Extended Patrick's JSPerf.

Tortilla

Answer 5

The OP has already given an example of a recursive solution. Although I believe that a non-tail recursive function is the ideal approach for this task, I think their implementation has two drawbacks though:

1. It mutates state of its parent scope
2. It is very specific and thus hardly reusable

I'm trying to implement a more generic solution without mutating global state. Please note that I would usually solve this problem by combining several smaller, reusable functions. The OP's condition is, however, to have only a single loop. This is a fun challenge and my implementation isn't intended for being used in real code!

I call the function defmap that is, deferred map:

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));

Sunfish

Can you elaborate on what this complicated looking code is actually doing? – Sexlimited

Answer 6

As per my comment, I can not see a way to do this without effectively looping over it twice.

1. To actually count the values
2. To evaluate each value against the total

To answer the "deferred" part of your question, one possible solution, albeit slower (Just guessing due to function call?) and probably not what you would want to use (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());
}

Outputs:

0.1
0.2
0.2
0.5

This has the added benefit of not actually calculating the value until you need it, but when it does calculate it, there will be a higher cpu cost (Due to calling the function etc).

This could be marginally optimised by changing the getPercent line to:

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

Which would ensure the calculation is only run the first time. Updated Fiddle

EDIT I ran some tests (Forgot to save before I crashed chrome by testing too many iterations, but they are simple enough to replicate). I was getting

1. Sumurai initial method (1000000 objects with value 0 -> 9999999) = 2200ms
2. My initial method (Same) = 3800ms
3. My "optimised" method (Same) = 4200ms

Martyrology

Creating that many function objects is probably more costly than just doing the calculation. Although it's really the only way to defer the calculation. – Cagle

@Bergi, absolutely! I don't recommend using this deferred method for this specific task at all. Although I concede someone might be able to find some ultra niche use for it...maybe – Martyrology

Well, lazy evaluation by itself is not exactly "ultra niche" - and can be implemented quite fast even in JavaScript. – Cagle

If you go as far as adding lazy evaluation functions, you can just add it to the prototype, which reduces the amount of functions to... 1. – Tortilla

@Bergi: I think you can defer the calc with a non tail recursive solution too (see my answer). – Sunfish