Optimizing boolean checking method

Question

I have written a method that checks if n number of true booleans are present in a boolean[] array. Then I improved it to var args format which is as follows:

public static boolean checkNTrue(int n, boolean... args) {
    assert args.length > 0;
    int count = 0;
    for( boolean b : args ) {
        if(b)   count++;
        if( count > n )
            return false;
    }
    return ( count == n );
}

I implement it to check if only one of all those booleans is true by using:

boolean result = checkNTrue(1, false, true, false, false);

The above returns true confirming the required case. But what if there are only two boolean arguments? A simple XOR could return the right result.

And in the case of 3 booleans, return (a ^ b ^ c) ^ (a && b && c); works fine too. So, my question is:

Do I need to write separate methods to check in cases with 2 and 3 variables?

Or will this one method do fine? I invite every kind of criticism through downvotes and comments, but please enlighten me! :-)

Answer 1

Premature optimization is a bad idea. Before you try to optimize anything, run a profiler to measure where your bottlenecks are. Unless you are running this function in a tight loop, it's unlikely that this function will be a bottleneck.

The special cases that you would introduce don't come for free:

• The more line of code you write, the more bugs you are likely to have, statistically.
• Your unit tests also have to address the special cases.
• There is a bit of overhead in checking whether your special cases apply.

Taking all that into consideration, it's almost certainly not worthwhile to add special cases.

---

The assertion assert args.length > 0 might be inappropriate. Considering this code in a vacuum, there is nothing to guarantee that that assertion is logically true. Rather, it's a runtime validation check. Validation failures should throw an IllegalArgumentException. They shouldn't be assertion failures. (Assertions can be disabled, defeating your check.)

If this were a non-public method, and you are sure that you've written your code such that all call sites have at least two arguments, then an assertion might be appropriate.

Here's a philosophical question: should checkNTrue(0) be true or false? I think it should be true.

Answer 2

1. assert statements can be disabled, so I'd throw an exception instead:

   if (args.length < 1) {
       throw new IllegalArgumentException("must have at least one boolean parameter");
   }
   

2. if(b)   count++;
   

   I'd put the count++ statement to a separate line. From Code Complete, 2nd Edition, p759:

   With statements on their own lines, the code reads from top to bottom, instead of top to bottom and left to right. When you’re looking for a specific line of code, your eye should be able to follow the left margin of the code. It shouldn’t have to dip into each and every line just because a single line might contain two statements.

3. I'd rename the method to checkExactlyNTrue for easier understanding. (It would have answered my initial question: what does it do if I have more than n true parameters?)

4. Do I need to write separate methods to check in cases with 2 and 3 variables?

   If you don't have a concrete reason why would you do it? Keep it simple. The method in the question works with two and three parameters too, I would use that.

5. And in the case of 3 booleans, return (a ^ b ^ c) ^ (a && b && c); works fine too. So, my question is:

   This would be really hard to read and understand, the method in the question expresses the intent/purpose of the method better.

Answer 3

if(b)   count++;
if( count > n )
    return false;

...can be improved as...

if (b && ++count > n)
    return false;

...which uses "short circuit evaluation" so the stuff after && doesn't run if b if false, i.e. it doesn't bother to check count when it hasn't just been modified. I wouldn't bet on an optimiser understanding this relationship well enough to eliminate the extra check in !b situations.

Answer 4

At the moment, your code is simple enough so that it's quite easy to understand what it does and to be convinced quite easily that is does correctly. One of the main principle of programming is Keep it simple.

Adding special cases will give you more code to maintain and potentially introduce bugs. This is probably not something you want.

If you want to be sure that your function returns the same thing as xor, you might want to use this in your unit test (you were about to add unit tests, weren't you?)

If your reasoning to add special cases was performances, I guess you shouldn't be too worried about that as it corresponds to a situation which would have been super fast anyway.

Answer 5

If you really want this to be fast — like smokingly, freakingly, astonishingly fast — then throw everything out that you've go so far and rewrite the whole thing to be an O(1) implementation instead of an O(n) implementation.

Always remember the first rule of optimization: The fastest way to do something is to not do it. And the thing you want to avoid here is looping through the array to count values. Memory accesses are expensive, especially if they result in L1 or L2 cache misses or VM page faults.

So here's what I would do: Create a wrapper class for the boolean array. Provide read and write methods for accessing elements of the array. Maintain a count c of true values. When an element is set (e.g., true or false value being stored at some index), compare the new value against the old value. If the value is transitioning from false to true, increment c by 1; if the value is transitioning from true to false, decrement c by 1. Then, in the method which checks if n true boolean values are present, simply compare n to c and you're done. Extremely minimal overhead, and extremely fast checking with no looping.