Fastest way to check if an array of boolean contains true

Question

I have an array of boolean entries:

boolean[] myBooleanArray = new boolean[24];

Currently i check if it contains true like so:

Arrays.asList(myBooleanArray).contains(true);

Is this the fastest way to check an array of boolean? If not, what is the fastest way to perform this check?

EDIT:

I timed the methods in your answers as follows by running it as an app on an Android 4.03 Samsung S2 device:

boolean[] myBooleanArray = new boolean[24];

long startTime = System.nanoTime();
suggestedMethod(myBooleanArray);
long endTime = System.nanoTime();

long duration = endTime - startTime;
Log.i("timetest", Long.toString(duration));

Time ranking over five runs were, with fastest first:

Between 5334 and 11584 ns:

for (boolean value : myBooleanArray) {
    if (value) {
        return true;
    }
}
return false;

Between 160542 and 171417 ns:

Arrays.asList(myBooleanArray).contains(true);

Between 191833 and 205750 ns:

Booleans.contains(myBooleanArray, true);

`Arrays.asList(myBooleanArray)` gives you list of arrays not `Boolean`s. That method should not be used with arrays of primitives. — Bhesh Gurung, Dec 03 '12 at 05:56
Why don't you benchmark your various options and see rather than believing others? — Rohit Jain, Dec 03 '12 at 05:57
@Rohit Jain. Fair point, but I'm not experienced enough to know what all the options are. With these answers I can do a benchmark. — Pierre Rymiortz, Dec 03 '12 at 06:01
Thank you everyone for your suggestions. See edited answer for benchmarking of methods. — Pierre Rymiortz, Dec 03 '12 at 06:54

score 14 · Accepted Answer · answered Dec 03 '12 at 05:53

14

Just iterate through array

for(boolean value: myBooleanArray){
  if(value){ return true;}
}
return false;

answered Dec 03 '12 at 05:53

jmj

237,923
42
401
438

OP just want to check presence of `true`, its not about all the `true` – jmj Dec 03 '12 at 05:57

score 6 · Answer 2 · answered Dec 03 '12 at 05:58

6

If you are using the Guava library (which has a lot of useful stuff):

Booleans.contains(myBooleanArray, true);

(JavaDoc)

The documentation of this method also describes another way. You can replace a boolean[] with a BitSet (should be more memory efficient) and call !bitSet.isEmpty() to check whether at least one bit is true.

answered Dec 03 '12 at 05:58

Philipp Wendler

11,184
7
52
87

Is this the fastest way ? Because it is also doing the same by using contains method as it is also in question. – Android Killer Dec 03 '12 at 06:06
2

I cannot think of any faster way for a boolean array (but the BitSet might actually be faster). – Philipp Wendler Dec 03 '12 at 06:08

score 4 · Answer 3 · answered Dec 03 '12 at 06:01

Generally speaking, if you have an array (or List) of anything, the fastest/onlyest way to look for an item in it is to iterate over the array until you find what you're looking for. That's one of the limitations of arrays/Lists.

For an array of 24 elements, I wouldn't worry about this anyway. If you had millions of items and expected very few trues (or possibly none), then it could make sense to encapsulate the data in a class:

public class BooleanArray
{
    boolean[] arr = new boolean[SIZE]; // or get size from a constructor
    boolean anyTrue = false;

    boolean get(int index) {
        return arr[index];
    }

    boolean set(int index, boolean value) {
        arr[index] = value;
        anyTrue |= value;
    }

    boolean containsAnyTrues() {
        return anyTrue;
    }
}

To reiterate, I don't suggest this for your array of 24 elements. I mean it more of an example that your data structure should support the expected use case. If the expected use case is "lots of elements, very sparse trues, need to find out if there are any trues" then your concern for the fastest way is more relevant, and a data structure like the one above would be useful.

score 2 · Answer 4 · edited May 23 '17 at 10:33

2

According to this previous question iterating over an array is mostly the same using enhanced for or normal for because both use array accesses . So just iterate over your array:

public boolean containsTrue(boolean[] array){

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

    return false;
}

edited May 23 '17 at 10:33

Community

1
1

answered Dec 03 '12 at 05:58

ElderMael

7,000
5
34
53

score 0 · Answer 5 · answered Dec 03 '12 at 07:18

0

If you had an array of 0's and 1's, you could simply OR every element. If you get a 1, you know there is atleast one TRUE.

answered Dec 03 '12 at 07:18

AbuZubair

1,236
14
20

score 0 · Answer 6 · answered Apr 23 '20 at 09:20

If you are not bound to an Array of boolean, you should give a look to the class java.util.BitSet. Despite the name, it is more array-like than set-like.

The method BitSet.isEmpty is answering your question if there is any true in the "Array", and it is implemented as:

public boolean isEmpty()
{
    return wordsInUse == 0;
}

I doubt that you can get a faster check …

But the price has to be paid elsewhere: setting/unsetting a value might be more expensive as for a mere boolean [].

matt · Answer 7 · 2020-04-23T11:30:48.583

If you know the size of the array, and the array is large. Eg. 24 is pretty small so it would be hard to improve. Arrays.mismatch seems to be a bit quicker.

import java.util.Arrays;
import java.util.Random;

public class BenchMark{
    final static int N = Short.MAX_VALUE;
    static boolean[] base = new boolean[N];
    static boolean any1(boolean[] test){
        return Arrays.mismatch(base, test)==-1;
    }
    static boolean any2(boolean[] test){
        for(boolean b: test)
            if(b) return true;
        return false;
    }
    public static void main(String[] args){
        boolean[] test = new boolean[N];
        Random r = new Random(1);
        int last = 0;
        long start = System.nanoTime();
        int p = 0;
        for(int i = 0; i<100000; i++){
            test[last] = false;
            int s = r.nextInt(2);
            if(s == 0){
                last = r.nextInt(test.length);
                test[last] = true;
            } 
            if(any2(test)){
                p++;
            }
        }
        System.out.println( ( p + " in " + (System.nanoTime() - start ) / 1e9 ) + " seconds");
    }
}

I didn't setup a proper benchmark, but the output from this shows any1 to be about 4-5 times faster than any2, the standard loop technique.

To understand why, looking in the jdk source code. We find vectorizedMismatch which appears to be using the unsafe class to cast the values to a long and comparing the long values.

Fastest way to check if an array of boolean contains true

7 Answers7

Linked

Related