Comparing 5 Integers in least number of comparisons

Question

I have this code and need to make sure that all result variables are equal?

long result1 = timer.CalculateElapsedTimeInMinutes();
long result2 = timer.CalculateElapsedTimeInMinutes();
long result3 = timer.CalculateElapsedTimeInMinutes();
long result4 = timer.CalculateElapsedTimeInMinutes();
long result5 = timer.CalculateElapsedTimeInMinutes();

This is what I did, but I feel like it can be done in a simpler way, maybe not?

bool allEqual = (result1 == result2) && (result3 == result4) && (result1 == result3) && (result1 == result5);

Thanks.

Answer 1

Nope, you're going to require at least n-1 comparisons. Though I'd write it like this:

bool allEqual = (result1 == result2)
             && (result2 == result3)
             && (result3 == result4)
             && (result4 == result5);

Answer 2

It's just about possible that there's some hacky/clever bit-twiddling way of doing this with XORs or something - but your code makes it clear what you want to do, and will still be ridiculously fast. The chances of this becoming a bottleneck are close enough to 0 to not be worth considering IMO - so go with the most readable code.

I would be a bit more consistent in your comparisons though:

bool allEqual = (result1 == result2) && 
                (result1 == result3) && 
                (result1 == result4) &&  
                (result1 == result5);

It's easier to see visually that you've got all the bases covered, IMO.

Answer 3

Nope, that's pretty much perfect.

Everything should be made as simple as possible, but no simpler. -- Albert Einstein

Answer 4

The only way it might be faster is to short-circuit it in such a way that the pair most likely to be different is evaluated first.

Answer 5

How about this with LINQ:

var firstValue = timer.CalculateElapsedTimeInMinutes();

var list = new List<long>();
list.Add(timer.CalculateElapsedTimeInMinutes());
list.Add(...);

bool allEqual = list.All(i => i == firstValue);

Answer 6

You can also do this with link using the All extension method.

        var results = new long[] {
            timer.CalculateElapsedTimeInMinutes(),
            timer.CalculateElapsedTimeInMinutes(),
            timer.CalculateElapsedTimeInMinutes(),
            timer.CalculateElapsedTimeInMinutes(),
            timer.CalculateElapsedTimeInMinutes()
        };

        bool allEqual = results.All(x => x == results[0]);

Answer 7

Just for the heck of it, would this work ?

  bool allequal =
       res1 & res2 & res3 & res4 & res5 == 
       res1 | res2 | res3 | res4 | res5;

only one comparison... <grin> (if you don't count the bitwise operations!)

Answer 8

It depends on what you mean by comparison. You can do it using only one explicit comparison operaor:

bool result = 
    ((result1 ^ reesult2) | (result1 ^ result3) | (result1 ^ result4) | (result1 ^ result5))==0;

This might even have an advantage in the generated code -- the code using the logical and is required to stop doing comparisons as soon as it finds any un-equal value. That means each comparison has to be done individually, and it has to include code to quit the testing after each comparison.

Unless you're doing this inside a really tight loop, however, it's not worth it -- just do what you find the most readable.

Answer 9

You could also make a helper function for this:

bool AllEqual<T>(params T[] values) where T : IEquatable<T> {
    // make a decision here and document it
    if (values.Length < 1) return true; // I guess?

    bool result = true;
    T first = values[0];

    for (int i = 1; i < values.Length; i++) {
        result = result && first.Equals(values[i]);
    }

    return result;
}