10
\$\begingroup\$

This feels like the kind of problem that has an extremely elegant solution. But my code is mechanical and straightforward. Not bad but I'm interested if there's something nicer.

Performance is not really an issue. I'm looking for elegant/shorter, not faster.

No underscore.js please; it's not worth fighting my coworkers to get another third-party library in there, especially when it duplicates so much ES5. Speaking of which, we work in an ES5-only environment so use all the array extras you want.

function getIds(array) {
    // We have added `Array.prototype.unique`; it does what you'd expect.
    return array.map(function (x) { return x.id; }).unique().sort();
}

function areDifferentByIds(a, b) {
    var idsA = getIds(a);
    var idsB = getIds(b);

    if (idsA.length !== idsB.length) {
        return true;
    }

    for (var i = 0; i < idsA.length; ++i) {
        if (idsA[i] !== idsB[i]) {
            return true;
        }
    }

    return false;
}
\$\endgroup\$
5
  • \$\begingroup\$ In general you want to name it containSameIds and just swap return true with return false. I personally would convert arrays to hash sets and then iterate over one, then another (if sizes are the same). I would not try to make the function too short at the expense of readability. \$\endgroup\$ – Leonid Feb 22 '12 at 5:37
  • \$\begingroup\$ I would remove the .length comparison code. The for loop below it, would give the same result. The only reason for putting it there would be performance. \$\endgroup\$ – Gerben Feb 22 '12 at 12:20
  • 2
    \$\begingroup\$ @Gerben consider idsA = ["x"], idsB = ["x", "y"]. \$\endgroup\$ – Domenic Feb 22 '12 at 13:34
  • \$\begingroup\$ Consider adding Array.prototype.compare too. :) \$\endgroup\$ – Quentin Pradet Feb 22 '12 at 15:17
  • 1
    \$\begingroup\$ @Domenic I see. In that case !== should be < :-P \$\endgroup\$ – Gerben Feb 22 '12 at 15:35
12
\$\begingroup\$
function areDifferentByIds(a, b) {
    var idsA = a.map( function(x){ return x.id; } ).unique().sort();
    var idsB = b.map( function(x){ return x.id; } ).unique().sort();
    return (idsA.join(',') !== idsB.join(',') );
}

This is the simplest I could make it. I think such small functions need to be as self contained as possible, and not need other functions. This makes them more readable, maintainable, and of course reusable. I therefor removed the getIds function. If you use that elsewhere you can keep it.

You might want to store the function (x) { return x.id; } inside a variable, and reuse it on both maps

I also think it is faster, because join is quite fast, and it doesn't require a for-loop.

EDIT my next attempt

function areDifferentByIds(a, b) {
    var idsA = a.map( function(x){ return x.id; } ).unique();
    var idsB = b.map( function(x){ return x.id; } ).unique();
    var idsAB = a.concat(b).unique();
    return idsAB.length!==idsA.length
}

secondly, you could make it more generic, by adding the property you want to check to the arguments of the function. Something like:

function areDifferentByProperty(a, b, prop) {
    var idsA = a.map( function(x){ return x[prop]; } ).unique();
    var idsB = b.map( function(x){ return x[prop]; } ).unique();
    var idsAB = a.concat(b).unique();
    return idsAB.length!==idsA.length
}

thirdly, I would much rather name it areEqualBy___. Seems more intuitive to me, but that's just me.

\$\endgroup\$
5
  • \$\begingroup\$ No good, my IDs can be arbitrary strings. idsA = ["x,y"] vs idsB = ["x", "y"] breaks it. \$\endgroup\$ – Domenic Feb 21 '12 at 22:21
  • 1
    \$\begingroup\$ And I'm saying right now, any solutions that rely on picking an "unguessable" sequence of Unicode characters to be the joiner will probably work in the real world, but are even less elegant than my original ;) \$\endgroup\$ – Domenic Feb 21 '12 at 22:23
  • \$\begingroup\$ I think less code is more elegant, but I guess you are right. If id's can be arbitrary strings, it could cause in incorrect result, which is not very elegant, to say the least. \$\endgroup\$ – Gerben Feb 22 '12 at 12:19
  • \$\begingroup\$ I made another attempt, that should work regardless of the id format. See edit above. \$\endgroup\$ – Gerben Feb 22 '12 at 15:47
  • 1
    \$\begingroup\$ OK the second attempt is really clever and very much along the lines of what I'm looking for. We have a winner!!! \$\endgroup\$ – Domenic Feb 22 '12 at 16:18
3
\$\begingroup\$

I don't think your main logic can be changed, but you can still write this more concisely:

function areDifferentByIds(a, b) {
    var idsA = getIds(a);
    var idsB = getIds(b);

    return idsA.length == idsB.length
      && idsA.every(function(e,i) { return idsB.indexOf(e) == i; });
}

Note that every and reduce only work since IE9. An implementation is proposed on MDN's Array.every page. It is still ES5 though.


(For the comments below to make sense, I kept the nonsense below).

Do you know about ES5's reduce() function? It runs through every value of the array (x in my code), letting you know the current index (i in my code), and asks you to "reduce" your array using an accumulator (acc in my code).

The accumulator is first set to true, and is still true only if the current indices are equal.

function areDifferentByIds(a, b) {
    return a.reduce(function(acc,x,i) { return acc && a[i] == b[i] }, true);
}

Here is a simpler example of reduce which could help you understand how it works. This one sums the elements of my array:

sum = [1, 2, 3, 4].reduce(function(acc, x) { return acc + x}, 0);

Update:

  1. This new version does compare id properties. I don't think you can avoid the getIds() step anyway, which is why it wasn't in the previous version.
  2. b being longer than a wasn't a problem. b being shorter than a could have been one: with a = [undefined], a[20] == a[0] is true. Using indexOf to search elements means I no longer have to deal with that.
  3. There is no duplication since ids are unique.
  4. I switched to every(), which does the same thing that my previous reduce() implementation, but is way simpler.

The code:

function areDifferentByIds(a, b) {
    var idsA = getIds(a);
    var idsB = getIds(b);

    return a.every(function(e, i) { return b.indexOf(e) == i }
}

Did I miss anything else? edit: OK, ["x"] versus ["x", "y"] won't work. I'm back to work.

\$\endgroup\$
2
  • \$\begingroup\$ OK this is nice: out of the box thinking. But a few problems: 1) doesn't compare id properties; 2) doesn't account for if b is longer than a; 3) doesn't deal with out-of-order values or doubled-up values. So really it looks like it's just a replacement for the for loop in my original solution, and not for the entire chunk of code. \$\endgroup\$ – Domenic Feb 22 '12 at 13:37
  • \$\begingroup\$ Your code is the simplest way to do that. With ES5 only, I don't think you can come up with a completely alternate way of doing it. Any other solutions will simply alleviate the needs for the checks and explicit loops you're using. \$\endgroup\$ – Quentin Pradet Feb 22 '12 at 14:34
1
\$\begingroup\$

Depending on the performance of your JavaScript engine's sort(), your sort-both-then-compare algorithm might very well be overwhelmed by it. Some sorts have worst-case performance of O(n²), which you could beat by skipping the two sorts and searching all of B for each element in A. For example:

function areDifferentByIds(a, b) {
    if (a.length !== b.length) {
        return true;
    }

    aLoop: for (var i = 0; i < a.length; ++i) {
        bLoop: for (var j = 0; j < b.length; ++i) {
            if (a[i] == b[j]) {
                continue aLoop;
            }
        }
        return true;
    }

    return false;
}
\$\endgroup\$
4
  • \$\begingroup\$ I fail to see why anyone would implement a O(n²) sort? \$\endgroup\$ – Quentin Pradet Feb 22 '12 at 10:49
  • \$\begingroup\$ Also, your solution is all about performance, but not about concise code, which is not what the OP asked. It's still a nice trick, thanks for sharing. \$\endgroup\$ – Quentin Pradet Feb 22 '12 at 11:10
  • \$\begingroup\$ if a is [{x:1},{x:1}] and b is [{x:1}] your code would say they are different. I didn't know you could label loops. \$\endgroup\$ – Gerben Feb 22 '12 at 12:16
  • \$\begingroup\$ +1 for the loop-labeling novelty, but not really much better than what I already have, considering performance doesn't matter. \$\endgroup\$ – Domenic Feb 22 '12 at 16:16
1
\$\begingroup\$

May I propose my own solution. The elegance is in how it is called. Two objects are compared by property 'id', if no other parameter is passed. Otherwise, you can extend the call to areDifferentByIds to indicate the properties to compare.

function areDifferentByIds(a, b) {
    var addArgs = Array.prototype.slice.call(arguments, 2);
    var props = addArgs.length > 0 ? addArgs : ['id'];
    for(var diff=false, i=0; !diff && i<addArgs.length; i++) {
        diff = a[addArgs[i]] !== b[addArgs[i]];
    }
    return diff;
}

Usage example:

// false
areDifferentByIds({id: 'test', b: 'me'}, {id: 'test', b:'test', c: 'test'});  
// false
areDifferentByIds({id: 'test', b: 'me'}, {id: 'test', b:'test', c: 'test'}, 'id');
// true 
areDifferentByIds({id: 'test', b: 'me'}, {id: 'test', b:'test', c: 'test'}, 'b'); 
// true
areDifferentByIds({id: 'test', b: 'me'}, {id: 'test', b:'test', c: 'test'}, 'id', 'b'); 

areDifferentByIds Let me know. I hope that helps!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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