Reducing a 'raw' javascript array into a more compact array (of objects)

Question

In javascript, I'm looking for a tidy way of processing an array such that the short, repeating sequences (tuples) in a collection become reduced into a more compact collection. I want to convert an array of length 3n to a collection of length n.

Here's an imaginary example:

// A flat (1-dimensional) array of numbers for input
var input = [ 
  1, 11, 5,
  2, 12, 10,
  3, 13, 6,
  4, 14, 11,   
  ... ];

// A custom "lambda". This is my main intent, the rest is just plumbing.
var formatData = function(a,b,c) {
  return { foo: a, bar: b, woot: c };
};

var output = input.reduceMulti(3, formatData); // ficticious 'reduceMulti'!

// output: 
// [
//   { foo: 1, bar: 11, woot: 5  },
//   { foo: 2, bar: 12, woot: 10 },
//   { foo: 3, bar: 13, woot: 6  },
//   { foo: 4, bar: 14, woot: 11 },
//   ...
// ]

Alternatively, those objects in output could easily be strings, or arrays, if formatData returned something different.

I'm looking for a solution a lot like reduce, except with the ability to reduce to more than a single value.

Bonus points for being performant, but ultimately the solution should be readable, maintainable, and usable.

did you intend to make the input variable a list of lists or is the existing assignment right? — Hrishi
– Hrishi, Commented Oct 7, 2014 at 4:27
@Hrishi The input array is just a simple 1-dimensional array, formatted to make the groups of three clearer. (It is correct as is.) — aaaidan
– aaaidan, Commented Oct 7, 2014 at 4:36
Which do you want more... native Array functions or speed? A for loop is usually much faster. — user1106925
– user1106925, Commented Oct 7, 2014 at 4:56
@squint Keen on speed, but not at the cost of readability and functional usability. (Sometimes the two can even intersect!) Native functions not necessary: use your judgement. — aaaidan
– aaaidan, Commented Oct 7, 2014 at 5:52
you want to use map() on the main array (to trasnform each), and reduce on the sub-arrays (to summarize each). — dandavis
– dandavis, Commented Oct 7, 2014 at 5:59

elclanrs · Accepted Answer · 2014-10-07 05:10:44Z

3

You can still use reduce which takes also an index and the array as arguments:

var formatData = function(x, y, z) {
  return [x, y, z]
}

var reduceMulti = function(n, f, xs) {
  return xs.reduce(function(acc, x, i, xs) {
    if (i % n === 0) {
      acc.push(f.apply(null, xs.slice(i, i+n)))
    }
    return acc
  },[])
}

reduceMulti(3, formatData, input)
//^ [[1,11,5], [2,12,10], [3,13,6], [4,14,11]]

If you give n a value of 3 then you'd have to pass a function that expects 3 arguments.

edited Oct 7, 2014 at 5:10

answered Oct 7, 2014 at 4:19

elclanrs

94.2k21 gold badges137 silver badges171 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

aaaidan Over a year ago

Nice! Great to see the native reduce function used to solve this. It's a shame you can't skip over the "return acc" calls.

user663031 Over a year ago

If I give this an array whose number of elements is not an exact multiple of n, then it gives me back undefineds at the end of the last partition. It would also not work for other partition sizes. This could be solved by changing formatData to simply return arguments. From a design perspective, I'm also not convinced that combining the notion of a partition with a notion of somehow transforming (via formatData) the elements in each partition, is ideal. It would seem better to have a stand-alone partitioner, and then let the user do whatever he wants with the partitions.

score 2 · Accepted Answer · 2014-10-08 03:26:11Z

2

I would start off with a simple little routine to partition an array into segments of equal size:

function partition(arr, n) {
    return arr.length ? [arr.splice(0, n)].concat(partition(arr, n)) : [];
}

And a little sum function:

function sum(arr) { return arr.reduce(function(s, v) { return s + v; }); }

Now, we'll partition the original array and map it to the objects of statistical measures:

partition(input, 3).map(function(seg) {
    return {
        max:  Math.max.apply(0, seg), 
        min:  Math.min.apply(0, seg), 
        mean: sum(seg)/seg.length};
    };
})

If you would prefer a non-recursive segmenter:

function partition(arr, n) {
    var result = [];
    while (arr.length) { result.push(arr.splice(0, n)); }
    return result;
}

This takes advantage of the behavior of Array#splice, that it modifies the array to remove the specified elements and returns an array of the removed elements.

If you really want to achieve exactly the syntax you propose, then you would need to put reduceMulti on the Array prototype, not that I'm recommending that:

Array.prototype.reduceMulti = function(n, reducer) {
    return partition(this, n).map(reducer);
}

var output = input.reduceMulti(3, formatData);

edited Oct 8, 2014 at 3:26

answered Oct 7, 2014 at 7:13

user663031

3 Comments

aaaidan Over a year ago

Oh wow, recursive partition function! Since there's no tail recursion in any browser I know, is there a danger that for large datasets you'd get a ... stack overflow?

user663031 Over a year ago

@aaaidan Not only recursive and prone to stack overflows, but also destructive--your array magically becomes empty!

aaaidan Over a year ago

Wow, great sell dude!

dandavis · Accepted Answer · 2014-10-08 00:39:47Z

1

Break the problem into steps: group the flat array, use map() to transform each one, and reduce to calc the sum.

var r= [ 
  1, 11, 5,
  2, 12, 10,
  3, 13, 6,
  4, 14, 11,
 ];

function flatToGrouped(r, width){
  var o=[];
  for(var i=0, mx=r.length; i<mx; i+=width){
   o.push(r.slice(i, i+width) );
  }
  return o.filter(Boolean);
}

function report(a,_,__){
  return { 
    min:  Math.min.apply(0,a), 
    max:  Math.max.apply(0,a), 
    mean: a.reduce( function(a,b,_,__){ return a+b; } ) 
  }
}

flatToGrouped(r, 3).map(report);

The extra formal parameters look weird, but they make the function run faster than they other wise would (i just found out arity matching improves optimization - i'm telling everyone).

EDIT: i didn't realize the initial array was flat. you can still use the simple map on the item transformer, and use a collector to make the n-level array you want to analyze. by breaking them into two parts, you're not locked into a reduce, but rather anything an array can do (map/reduce/filter/etc).

edited Oct 8, 2014 at 0:39

answered Oct 7, 2014 at 6:06

dandavis

16.8k5 gold badges43 silver badges38 bronze badges

10 Comments

user1106925 Over a year ago

The initial array is flat.

aaaidan Over a year ago

Thanks for the answer, but calculating the min, max, mean, isn't what I'm trying to achieve. Read the question again, and let me know how you think I could make it clearer.

dandavis Over a year ago

@aaaidan: i edited... the logic is hot-swappable, just pass a different function to map() instead of report(); you don't need to build anything ahead of time if you use interchangeable generic parts...

aaaidan Over a year ago

@dandavis That sounds reasonable, but forgive me, I'm a little confused by your use of Math.min/max and reduce in the report function. They had led me to believe you think I want to perform those operations, so I've edited the question. Awesomely, flatToGrouped looks very promising, I'll have a look at that now.

dandavis Over a year ago

@aaaidan: yeah, i just filled-in some logic, but it's a weed among trees.

|

Collectives™ on Stack Overflow

Reducing a 'raw' javascript array into a more compact array (of objects)

3 Answers 3

2 Comments

3 Comments

10 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

3 Comments

10 Comments

Your Answer

Sign up or log in

Post as a guest

Related