Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I have implemented functions that will let me reverse a one-to-many value 'Map', that is a plain JavaScript object.

For example,

var map = {'foo': 'bar', 'baz': 'bar', 'moo': 'zoo'};

becomes

var reversedMap = {'zoo': ['moo'], 'bar': ['foo', 'baz']}

and also a function to bring back reversed map to a non-reversed map.

Here's a jsbin to show that my solution is working.

In the following code I have used lo-dash utility toolbelt, but you need not be acquainted with it in order to understand the code. Assume that I trust in performance of lo-dash and what I'm trying to optimize is my own code.

Just for sake of clarity, _.forOwn iterates over object's own properties, and _.forEach iterates over each element of an array.

var identity = function(x) {return x;};
var reverseMapFromMap = function(map, callback) {
    callback = callback || identity; //callback helps to parseInt numeric values, otherwise every object key is a string by default
    var reversedMap = {};
    _.forOwn(map, function(value, key) {
        key = callback(key);
        if (_.isUndefined(reversedMap[value]))
            reversedMap[value] = [key];
        else
            reversedMap[value].push(key);
    });
    return reversedMap;
};

var mapFromReverseMap = function(reverseMap, callback) {
    callback = callback || identity;
    var map = {};
    _.forOwn(reverseMap, function(revMembers, revKey) {
        _.forEach(revMembers, function(revMember) {
            map[revMember] = callback(revKey);
        });
    });
    return map;
};

I'm pretty confident in my solution as it's quite basic, but as it is a frequent part of my code, I'd like to know if you can see any ways to improve performance, or alternatively if there's a better way to solve this problem.

UPDATE: Here's how I ended up doing it.

I liked the suggestion by Flambino to use transforms and to use alternate syntax for if...else. Also, I renamed variables to make the meaning of the code clearer.

var reverseMapFromMap = function(map, callback) {
  callback = callback || _.identity;
  return _.transform(map, function(reverseMap, one, manyone) {
    reverseMap[one] = reversedMap[one] || [];
    reverseMap[one].push(callback(manyone));
  }, {});
};

var mapFromReverseMap = function(reverseMap, callback) {
  callback = callback || _.identity;
  return _.transform(reverseMap, function(map, many, one) {
    _.forEach(many, function(manyone) {
      map[manyone] = callback(one);
    });
  }, {});
};

Here's a performance overview: http://jsperf.com/object-key-value-map-reversal-one-many

As you can see from the above link, transform method and my original code are almost same in performance when it comes to large data, but I chose transform as it looks better to me in terms of readability. Native-only option does not perform so well when operating on large data.

share|improve this question

2 Answers 2

up vote 4 down vote accepted

Your code is pretty good as-is. There are other ways to do the same thing, but yours is fine.

One thing I noticed is that you've skipped braces on the if...else in reverseFromMap. My advice is to always use braces, even for one-line expressions.

However, you could also do

reversedMap[value] || (reversedMap[value] = []);
reversedMap[value].push(key);

You can collapse that into 1 line, although it's a little too terse if you ask me

(reversedMap[value] || (reversedMap[value] = [])).push(key);
// or 
(reversedMap[value] = reversedMap[value] || []).push(key);

Or just reduce it to a ternary

reversedMap[value] ? reversedMap[value].push(key) : reversedMap[value] = [key];

The _.isUndefined check isn't really required, since reversedMap[key] is either a non-empty array, or it's false'y.

Other small stuff:

  • I'd prefer the name iterator instead of callback, but lo-dash uses callback in similar situations, so sticking with that convention is fine.

  • You don't necessarily need the identity function, as you could also do

    x = callback ? callback(x) : x;
    

    and just not bother with the identity function. It may or may not be faster - I haven't benchmarked it. In any event, both approaches work just fine, so there's no need to change anything.

  • If you do need an identity function, lo-dash has one built-in (_.identity). Saves you having to type it out.

  • Lastly, if you want to be stringent, you might want to check whether callback is a function, instead of just doing "default if false'y". E.g.

    callback = _.isFunction(callback) ? callback : _.identity;
    // or just plain JS
    callback = typeof callback === 'function' ? callback : _.identity;
    

    Personally, I'd skip this, though. If people pass in something that's not a function, it's their bug to deal with. Besides, I'd rather have the code fail loudly than having it silently ignore my (faulty) callback argument and default to something else without telling me. Still, type-checking is an option, so I thought I'd mention it.

As for alternatives to the overall approach, I'd use _.transform (which is basically the same as reduce/foldl but aimed at objects)

var reverseMapFromMap = function(map, callback) {
  callback = callback || _.identity;
  return _.transform(map, function (memo, value, key) {
    key = callback(key);
    memo[value] || (memo[value] = []);
    memo[value].push(key);
  }, {});
}

And again for mapFromReverseMap

var mapFromReverseMap = function(reverseMap, callback) {
  callback = callback || _.identity;
  return _.transform(reverseMap, function (memo, keys, value) {
    _.forEach(keys, function (key) {
      memo[callback(key)] = value;
    });
  }, {});
};
share|improve this answer
2  
Nice, but I think callback = callback || _.identity is better than callback || (callback = _.identity). It's natural that way, no need to mess with it. –  janos Aug 31 at 17:34
    
@janos Heh, hadn't even noticed that I changed that. It wasn't on purpose. And you're right, the version without the parens is more natural, though I personally don't mind either one. Still, I'll update my answer –  Flambino Aug 31 at 17:52
    
Thanks @Flambino! I employed some of your suggestions and have updated the question with the final code. –  Peeyush Kushwaha Sep 1 at 10:15

I would recommend using built-in methods when you can. In this case I doesn't look like you need LoDash at all. You can use Object.keys and reduce:

var reverseMapFromMap = function(map, f) {
  return Object.keys(map).reduce(function(acc, k) {
    acc[map[k]] = (acc[map[k]] || []).concat((f || id)(k))
    return acc
  },{})
}

var mapFromReverseMap = function(rMap, f) {
  return Object.keys(rMap).reduce(function(acc, k) {
    rMap[k].forEach(function(x){acc[x] = (f || id)(k)})
    return acc
  },{})
}

I renamed identity to id, as it is a well known function in functional programming. I don't think it would create confusion, and lets you pass it in one liners easily, like shown above.

The above works with your example http://jsbin.com/cadig/1/edit. But I would recommend you reverse the arguments, so the callback comes first, and the receiver last, so it works better with composition.

Other than the missing braces in the if statement, I'd say your code looks pretty good. It is quite common though to use one or two letter variables in functional programming, as these transformations shall apply to many things in theory (polymorphism), and we only have a handful of objects. f clearly means "function" for example, and x is any value, where k is a "key". After getting used to these conventions, a line like:

rMap[k].forEach(function(x){acc[x] = (f || id)(k)})

seems faster to visually parse than:

rMap[key].forEach(function(value) {
  acc[value] = (callback || identity)(key)
})

Eventually your mind removes the function keyword, and you just see the transformation as it is. In ES6 this becomes even shorter, and calls for a concise one-liner:

rMap[k].forEach(x => acc[x] = (f || id)(k))
share|improve this answer
    
+1 for "native" functions. I consciously chose to stick to lo-dash in my answer, just for maximum compatibility. Besides, lo-dash will, I believe, just forward as much as possible to the native implementations, if available. Still, the more built-in functions you can use, the better. –  Flambino Sep 1 at 8:27
    
On the contrary, lodash is faster than native for most cases. This is primarily because it does not handle obscure use cases. –  Peeyush Kushwaha Sep 1 at 9:54
    
Native solution didn't turn out so well, performance-wise. I have updated the question with some performance information. –  Peeyush Kushwaha Sep 1 at 10:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.