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.

Close votes!!! What's wrong with these idiots? You must be feeling SO powerful!! A perfectly valid question here. — Agnel Kurian, Oct 21 '09 at 19:18
Well, crucial details were added after the initial post. As I saw it, this was a duplicate of http://stackoverflow.com/questions/1534748/design-an-efficient-algorithm-to-sort-5-distinct-keys-in-fewer-than-8-comparisons By the time I had tracked down that question, and pasted the URL in the close dialog, the text of this question had changed. So, I am one of the idiots. — Sinan Ünür, Oct 21 '09 at 19:27

score 14 · Accepted Answer · answered Oct 21 '09 at 18:54

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.

I see, I will make the change. Thanks! – Lukasz Oct 21 '09 at 19:02 — Lukasz, Oct 21 '09 at 19:02

Kip · Answer 2 · 2009-10-21T19:01:56.577

5

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);

edited Oct 21 '09 at 19:01

answered Oct 21 '09 at 18:54

Kip

107,154
87
232
265

and so you might as well make the code really clear by simply comparing result1 with each of the other values in turn. – djna Oct 21 '09 at 18:58
@Kip agreed. Apparently, transitivity of equality is too hard for some. – Sinan Ünür Oct 21 '09 at 19:29
I like the cyclical symmetry here. Comparing one result with every other isn't any more or less clear in my opinion, the difference is purely aesthetic. – Joren Oct 21 '09 at 19:39

score 2 · Answer 3 · answered Oct 21 '09 at 18:57

2

Nope, that's pretty much perfect.

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

answered Oct 21 '09 at 18:57

Anthony Mills

8,676
4
32
51

It's a good quote, but he's about the last person I'd expect to hear it from ;). – Hardryv Oct 21 '09 at 19:15
1

@Hadryv, what Einstein did could be (and often is) characterized as one of History's most significant and most elegant simplifications. – Charles Bretana Oct 21 '09 at 19:28

score 2 · Answer 4 · answered Oct 21 '09 at 19:05

2

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]);

answered Oct 21 '09 at 19:05

Jason

3,736
5
33
40

1

Now timer.CalculateElapsedTimeInMinutes() stands out like a sore thumb :) – Oct 21 '09 at 19:50

score 1 · Answer 5 · answered Oct 21 '09 at 18:57

1

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.

answered Oct 21 '09 at 18:57

Austin Salonen

49,173
15
109
139

Charles Bretana · Answer 6 · 2009-10-21T19:29:29.703

1

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!)

edited Oct 21 '09 at 19:29

answered Oct 21 '09 at 19:20

Charles Bretana

143,358
22
150
216

although it's 9 operations now, as opposed to 7. :) – Kip Oct 22 '09 at 03:06

score 0 · Answer 7 · answered Oct 21 '09 at 18:58

0

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);

answered Oct 21 '09 at 18:58

Codism

5,928
6
28
29

score 0 · Answer 8 · answered Oct 21 '09 at 19:24

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.

score 0 · Answer 9 · answered Oct 21 '09 at 19:43

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;
}

Comparing 5 Integers in least number of comparisons

9 Answers9