Remove items in an array as they are matched

Question

Remove items in an array as they are matched

I have a large array of comments that are threaded. Suppose the comments look like this:

{
  _id: [ObjectID],
  parentid: [ObjectID],
  ...
}

And I have a single large array of all the comments retrieved from the db:

comments = [comment1, comment2, comment3]

To get the replies of any arbitrary comment, I have a helper function like this:

function getReplies(comment, replies) {
  return replies.filter(function(reply) {
    return reply.parentid === comment._id
  }
}

I am however unsettled by the fact that this getReplies function will always check the whole array when many comments have already been processed (each only has one parent) or the comment only has 1 reply or none at all (deeper in the comment thread).

This is over-optimization, but I'd like to know how you guys would solve this problem. I don't think I would change this function unless there's a much more elegant solution. How would you structure this helper so that it doesn't unnecessarily process the same comment twice?

javascript
node.js

Answer 1

I'd process the entire list of comments once to build a lookup table from comment._id to a list of replies. Assuming comment._id has a reasonable toString() representation something like this should work:

var commentIdToReplies = {};
comments.forEach(function(comment) {
  if (comment.parentid) {
    var replies = commentIdToReplies[comment.parentid];
    if (!replies) {
      replies = [];
      commentIdToReplies[comment.parentid] = replies;
    }
    // Or just the _id if desired
    replies.push(comment);
  }
});
// now you can get the replies using:
// commentIdToReplies[comment._id]

If undefined is returned from commentIdToReplies that means there were no replies for that comment.

This approach trades off the time of having to scan the entire list every time with using more memory to maintain the lookup table.