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

• user14393: Why assert that args.length > 0? If argshas zero length, why not just return n == 0?
• 200_success: Please don't edit the code in the question in a way that invalidates existing answers. I've rolled it back to Rev 2.

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.

• RoToRa: @ambigram_maker You changed the assert to args.length > -1. Is that really useful? Is it even technically possible for the length of an array to become negative?
• Hungry Blue Dev: Sorry... Now I understand that the assert is useless.

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.

• 200_success: According to best practices, all if statements should have braces, and count++ should be on its own line. However, if the author insists on omitting the braces, then treating if (b) count++; as one statement on one line is safer.
• DannyMo: I would argue that the check for at least 1 boolean is not needed. The method is still correct without it, no?
• palacsint: @DannyMo: Yes, it as far as I see it is. (I didn't want to change the original behaviour.)
• Hungry Blue Dev: @DannyMo: I'm not checking my method with 1 boolean, but I'm implementing it! That's what I wanted to know... is it Okay if I use it to check only ONE boolean? :-)

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.

• 200_success: Your observation about efficiency is valid. However, it would be clearer to write it as a nested statement. if (b) { count++; if (count > n) { return false; }}
• Tony D: @200_success: I considered that, but I think programmers reading this should either already know how short-circuit evaluation and pre- vs post-increment work and be entirely comfortable with them, or make the time to learn. :^) This is pretty basic stuff, and if they're not 100% clear, they'll be guessing at what a lot of existing code does. But then I'm a C++ programmer at heart... bread and butter ;-).
• user14393: @TonyD: Short-circuit evaluation is great for dealing with cases where the latter tests might give exceptions or undefined behavior should the earlier ones fail... using it to control side effects is rather strange. (shell scripting aside... but then shell scripting is always strange!) If I saw code like that in real life, and noticed the effect, I would be far more likely to think "oh, the author made a mistake" before anything else.

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.

• palacsint: Using xor in unit tests reminds me Production Logic in Test

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.

• 200_success: I think you've just described Bitset.cardinality() (assuming it is efficiently implemented).
• Hungry Blue Dev: Yes, I understand that storing the required values on creation is definitely faster... but I'm applying this in a static method, so I don't know how much practical it would be. Would'nt using a wrapper add additional overhead every time I call it?
• Todd Lehman: @ambigram_maker — Using a wrapper class would add additional overhead, yes. If you are doing tons of updates and relatively few counting queries, then it may not be worth it; but if you are doing relatively few updates and tons of counting queries, then it will pay for itself easily — especially if there are millions of elements. It's hard to know which way would be best without knowing more about the problem domain... but you may find that the overhead is minimal anyway.