CODEWITHSUNDEEP
javascriptperformancenode.jsunderscore.jsasync.js
Abe Miessler
Abe Miessler

Reputation: 85116

Joining two collections efficiently?

I have run into an issue where I am trying to join two arrays similar to the ones below:

var participants = [
                      {id: 1, name: "abe"}, 
                      {id:2, name:"joe"}
                   ];
var results = [
                  [ 
                      {question: 6, participantId: 1, answer:"test1"},
                      {question: 6, participantId: 2, answer:"test2"}
                  ],
                  [
                      {question: 7, participantId: 1, answer:"test1"},
                      {question: 7, participantId: 2, answer:"test2"}
                  ]
              ];

Using nested loops:

_.each(participants, function(participant) {
  var row, rowIndex;
  row = [];
  var rowIndex = 2
  return _.each(results, function(result) {
    return _.each(result, function(subResult) {
      var data;
      data = _.find(subResult, function(part) {
        return part.participantId === participant.id;
      });
      row[rowIndex] = data.answer;
      return rowIndex++;
    });
  });
});

This works ok as long as the arrays are small, but once they get larger I am getting huge performance problems. Is there a faster way to combine two arrays in this way?

This is a slimmed down version of my real dataset/code. Please let me know if anything doesn't make sense.

FYI

My end goal is to create a collection of rows for each participant containing their answers. Something like:

[
    ["abe","test1","test1"],
    ["joe","test2","test2"]
]

Upvotes: 0

Views: 147

Answers (3)

Esailija
Esailija

Reputation: 140236

The perf* is not from the for loops so you can change them to _ iteration if they gross you out

var o = Object.create(null);

for( var i = 0, len = participants.length; i < len; ++i ) {
    o[participants[i].id] = [participants[i].name];
}

for( var i = 0, len = results.length; i < len; ++i ) {
    var innerResult = results[i];
    for( var j = 0, len2 = innerResult.length; j < len2; ++j) {
        o[innerResult[j].participantId].push(innerResult[j].answer);
    }

}

//The rows are in o but you can get an array of course if you want:

var result = [];

for( var key in o ) {
    result.push(o[key]);
}

*Well if _ uses native .forEach then that's easily order of magnitude slower than for loop but still your problem is 4 nested loops right now so you might not even need the additional 10x after fixing that.

Upvotes: 3

Xotic750
Xotic750

Reputation: 23492

Here is a solution using ECMA5 methods

Javascript

var makeRows1 = (function () {
    "use strict";

    function reduceParticipants(previous, participant) {
        previous[participant.id] = [participant.name];

        return previous;
    }

    function reduceResult(previous, subResult) {
        previous[subResult.participantId].push(subResult.answer);

        return previous;
    }

    function filterParticipants(participant) {
        return participant;
    }

    return function (participants, results) {
        var row = participants.reduce(reduceParticipants, []);

        results.forEach(function (result) {
            result.reduce(reduceResult, row);
        });

        return row.filter(filterParticipants);
    };
}());

This will not be as fast as using raw for loops, like @Esailija answer, but it's not as slow as you may think. It's certainly faster than using Underscore, like your example or the answer given by @Maroshii

Anyway, here is a jsFiddle of all three answers that demonstrates that they all give the same result. It uses quite a large data set, I don't know it compares to the size you are using. The data is generated with the following:

Javascript

function makeName() {
    var text = "",
        possible = "abcdefghijklmnopqrstuvwxy",
        i;

    for (i = 0; i < 5; i += 1) {
        text += possible.charAt(Math.floor(Math.random() * possible.length));
    }

    return text;
}

var count,
    count2,
    index,
    index2,
    participants = [],
    results = [];

for (index = 0, count = 1000; index < count; index += 4) {
    participants.push({
        id: index,
        name: makeName()
    });
}

for (index = 0, count = 1000; index < count; index += 1) {
    results[index] = [];
    for (index2 = 0, count2 = participants.length; index2 < count2; index2 += 1) {
        results[index].push({
            question: index,
            participantId: participants[index2].id,
            answer: "test" + index
        });
    }
}

Finally, we have a jsperf that compares these three methods, run on the generated data set.

Upvotes: 1

Maroshii
Maroshii

Reputation: 4027

Haven't tested it with large amounts of data but here's an approach:

var groups = _.groupBy(_.flatten(results),'participantId');
var result =_.reduce(groups,function(memo,group) {
  var user = _.find(participants,function(p) { return p.id === group[0].participantId; });
  var arr = _.pluck(group,'answer');
  arr.unshift(user.name);
  memo.push(arr);
  return memo ;
},[]);

The amounts of groups would be the amount of arrays that you'll have so then iterating over that with not grow exponentially as if you call _.each(_.each(_.each which can be quite expensive.

Again, should be tested.

Upvotes: 0

Related Questions