1

So, I have an array of booleans and I am trying to find if there is at least one "true" in there. What is the fastest way to compute this? Would changing the boolean array to a byte array (or some other type) would help in any way?

RIFAT Rafael Birmizrahi
  • 47
  • 6
  • 1
    "Would changing the boolean array to a byte array (or some other type) would help in any way?" How would that help? Do you mean at the time of checking, then it definitely isn't going to be faster. Are you asking if there is a better data structure? – matt Apr 23 '20 at 07:46
  • 1
    @matt If you use 1 bit per boolean in the other type you can check 8 (byte) or up to 64 (long) bits with one comparison, e.g. there is at least one "true" bit when then other type's value is not 0. – Lucero Apr 23 '20 at 10:18
  • @Lucero but if you created a long from a bunch of booleans, you have to go through each boolean and set the bit. Java doesn't have an actual cast function. So if you're going through all of the booleans anyways, you will be slower then just checking the boolean value. – matt Apr 23 '20 at 10:25
  • 1
    @matt My understanding of the OP's "Would changing the boolean array to a byte array (or some other type) help?" is that he would be using a different array to store the booleans in the first place, not convert them before checking. – Lucero Apr 23 '20 at 10:46
  • 1
    @Lucero which was the point of my question. using a long[] over a boolean[] might offer a marginal increase but using something like a BitSet could be much quicker depending on the nature of the data. – matt Apr 23 '20 at 10:52
  • 2
    Actually, I found Arrays.mismatch to be a bit faster than looping. Going down the source code rabbit hole leads to [vectorizedMismatch](https://github.com/openjdk/jdk/blob/a7830958e36df78c1bd3ba7943147beaaa1a9c41/src/java.base/share/classes/jdk/internal/util/ArraysSupport.java#L112) which uses unsafe to cast the data to a long and evaluate. – matt Apr 23 '20 at 11:26
  • @matt yes that was exactly what I meant, sorry for the confusion. – RIFAT Rafael Birmizrahi Apr 25 '20 at 00:24

1 Answers1

1

The fastest way is to iterate through array:

for (boolean element : array){
  if (element) { 
    return true; 
  }
}
return false;

Sure, it's O(n).

I.R.
  • 442
  • 1
  • 7
  • 16