neoflash neoflash - 3 months ago 5
Javascript Question

Javascript: Optimizing `reduce` for performance

I'm using a

.reduce
method to iterate thru an array of objects in order to return the array index for the object that best fits certain conditions. My array has around 30,000 indexes right now and I'm shooting for well over a million. Trouble is, iterating thru the array using
.reduce
takes FOREVER!!! We're talking almost 4 seconds at the moment, imagine if the array had my projected 1 million indexes. The array is compact. I'm not connected to a database or server. Here is my code:

var startMatchMaking = function () {
var loopCounter = 0;
var length = personArray.length;
do {
var manCounter = 0;
loopCounter++;
for (var i = length; i--;){
if (!personArray[i].isSingle && personArray[i].sex === "Male" &&
personArray[i].isAvailable === true) {
manCounter++;
var num = normalRandomScaled(2.1, 12.44);

var result = personArray.reduce(function(p,c,k,a){
return c.sex !== personArray[i].sex &&
!c.isSingle && c.isAvailable === true &&
c.age <= (personArray[i].age + num) &&
c.age >= (personArray[i].age - num) ? k : p;
}, 0);

result = !personArray[result].isSingle &&
personArray[result].sex !== personArray[i].sex &&
personArray[result].age <= (personArray[i].age + num) &&
personArray[result].age >= (personArray[i].age - num) ? result : -1;

if (result >= 0) {
householdArray.push (new Household (personArray[i], personArray[result]));
personArray[result].isAvailable = false;
personArray[i].isAvailable = false;
}
}
}
document.write("<br>Mancounter is: " + manCounter +
" loopCounter is: " + loopCounter + " households: " + householdArray.length);
}
while (manCounter > 0 && loopCounter <= 5);
};

startMatchMaking();


CONTEXT: I'm trying to develop a standalone application to run an agent-based model demographics simulation.
personArray
essentially contains 30,000 human beings. The particular bit of code above is related to the initial setup of the population.
Person
s were previously created and pushed to the array. Each
Person
object has a
firstName
,
lastName
,
sex
,
age
and
isSingle
property. They were assigned random values for each. At this stage in the program, I need to take the
Person
s who are meant to be not single, and match them with a suitable mate of the opposing sex and a compatible age to form households.

How can I optimize this in order to increase performance significantly? I'm open to small changes or completely different alternatives that would output the same
result
.

Answer

I think you'll need some pre-processing in order to speed this up.

For instance:

  • split population into men and women
  • sort men by age
  • iterate on the sorted array of men and compute a new set of matching women only when a new age is being processed
  • just pick women from the current set while it's up-to-date and not empty

EDIT: We can optionally optimize the number of matches by sorting the set of women by age difference, so that couples with a small age difference are created first.

Below is some example code.

var personArray = [];

// create test population
for(var n = 0; n < 30000; n++) {
  personArray.push({
    isSingle: Math.random() < 0.5,
    age: Math.round(18 + Math.random() * 80),
    sex: Math.random() < 0.5 ? 'M' : 'F',
    isAvailable: true
  });
}

var num = 7, // instead of num = normalRandomScaled(2.1, 12.44)
    sex = [ [], [] ],
    curAge = -1, subset,
    houseHold = [],
    ts = performance.now();

// split population into men & women
personArray.forEach(function(p) {
  sex[p.sex == 'M' ? 0 : 1].push(p);
});

// sort men by age
sex[0].sort(function(a, b) { return a.age - b.age; });

// iterate on men
sex[0].forEach(function(m) {
  if(m.age != curAge) {
    // create set of matching women for this age
    subset = sex[1].filter(function(w) {
      return w.isAvailable && w.isSingle && Math.abs(m.age - w.age) <= num;
    });
    // sort by age difference, so that women with
    // a small age difference are picked first
    subset.sort(function(a, b) {
      return Math.abs(m.age - b.age) - Math.abs(m.age - a.age);
    });
    curAge = m.age;
  }
  if(m.isSingle && subset.length) {
    // pick woman from set
    var w = subset.pop();
    m.isAvailable = false; // (not really necessary)
    w.isAvailable = false;
    houseHold.push([ m, w ]);
  }
});

console.log(
  'Found ' + houseHold.length + ' matches ' +
  'in ' + Math.round(performance.now() - ts) + 'ms'
);
console.log(
  'Random example:',
  houseHold[(Math.random() * houseHold.length) | 0]
);