Improving performance while iterating two nested loops [closed]

Question

I calculate a "Top-5-List" of Birthplaces organized in an array of objects in this form

var myObjArr =[
{
  "birth": 
  {
    "year": 2012,
    "name": "Manchester, Vermont, USA",
  }
} , (and so on)
];

My approach however does not seem to be much performant:

for (var i = 0; i < myObjArr.length; i++) {

    var alreadyListed = -1;

    for (var j = 0; j < resultData.length; j++) {
      if(resultData[j].key == myObjArr[i]['birth']['name']) { // birthname already in resultData   
        alreadyListed = j;
        break;
      }
    }
    if(alreadyListed != -1 ) { // birthname already in resultData -> raise count
      resultData[alreadyListed].count += 1;

    }else {  // birthname not yet in resultData -> add to resultData
      resultData.push({key: myObjArr[i]['birth']['name'], count: 1 });    
    }
  }
}  

Neiter javascript's forEach nor angulars angular.forEach seem to improve the performance. Any Suggestions?

Answer 1

You can use an object as a dictionary instead of using an array and looking for a key by iterating, this way the second "loop" is done by the Javascript implementation when looking for object keys (also it's probably not a linear scan but an hash table lookup):

var result = {};
myObjArr.forEach(function(obj) {
    var key = "!" + obj.birth.name;
    result[key] = 1 + (result[key] || 0);
});

I'm always adding a "!" in front of the key when using objects as dictionaries because all Javascript objects do have an inherited constructor property and I don't want to interfer with that.

The (x || 0) trick is to start with a 0 when a name has not seen before (undefined is falsy in Javascript). Adding 1 to undefined instead results in NaN.

If you really need an array as result the code is only slightly more complex:

var result = [];
var index = {};
myObjArr.forEach(function(obj) {
    var key = "!" + obj.birth.name;
    var ix = index[key];
    if (ix === undefined) {
        // Allocate a new entry
        index[key] = result.length;
        result.push({key:key, count:1});
    } else {
        result[ix].count += 1;
    }
});