检查布尔数组中是否包含true的最快方法

Question

我有一个boolean类型的数组：

boolean[] myBooleanArray = new boolean[24];

目前我是这样检查是否包含true：

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

这是检查布尔数组的最快方法吗？如果不是，那么执行此检查的最快方法是什么？

编辑：

我通过在Android 4.03三星S2设备上运行该应用程序来计时您答案中的方法，结果如下：

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

五次运行的时间排名，最快的排在第一位：

1. Between 5334 and 11584 ns:

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

2. Between 160542 and 171417 ns:

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

3. Between 191833 and 205750 ns:

   Booleans.contains(myBooleanArray, true);
   

- Pierre Rymiortz

---

Arrays.asList(myBooleanArray) 会给你一个数组列表，而不是 Boolean 类型的列表。该方法不应与原始类型的数组一起使用。 - Bhesh Gurung

为什么不对您的各种选项进行基准测试，而不是相信别人的说法呢？ - Rohit Jain

@Rohit Jain。说得不错，但我缺乏足够的经验，不知道所有的选择都是什么。有了这些答案，我可以进行基准测试。 - Pierre Rymiortz

@PierreRymiortz.. 嗯。好的。 - Rohit Jain

感谢大家的建议。请查看编辑后的答案以获取方法的基准测试结果。 - Pierre Rymiortz

Answer 1

只需遍历数组即可

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

- jmj

---

OP只想检查true是否存在，而不是所有的true。 - jmj

Answer 2

如果您正在使用Guava库（该库有很多有用的功能）：

Booleans.contains(myBooleanArray, true);

(JavaDoc)

这个方法的文档中还描述了另一种方式。你可以用 BitSet 替换 boolean[]（应该更节省内存），并调用 !bitSet.isEmpty() 来检查是否至少有一个位为真。

- Philipp Wendler

---

这是最快的方法吗？因为它也使用了contains方法，就像问题中所描述的那样。 - Android Killer

我想不出任何更快的方法来处理布尔数组（但BitSet可能会更快）。 - Philipp Wendler

Answer 3

一般来说，如果你有一个数组（或者List）并想在其中查找元素，最快/唯一的方法是迭代整个数组直到找到目标。这是数组/List的局限之一。

但对于只有24个元素的数组，通常不需要担心这个问题。如果你有数百万个元素且期望很少会出现true（或者根本没有），那么封装数据到类中可能是有意义的：

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

再强调一遍，我不建议将这种方法用于你的包含24个元素的数组。 我更多的是想给你一个例子，告诉你的数据结构应该支持预期的使用情况。 如果预期的使用情况是“许多元素，非常稀疏的true值，需要找出是否有任何true值”，那么你对最快速度的关注更加相关，上面提到的数据结构将会很有用。

- yshavit

Answer 4

根据这个之前的问题所述，使用增强型for循环或普通for循环来遍历数组在大多数情况下都是相同的，因为两者都使用数组访问。所以只需遍历您的数组即可：

public boolean containsTrue(boolean[] array){

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

    return false;
}

- ElderMael

Answer 5

如果你有一个由0和1组成的数组，你可以简单地对每个元素进行OR运算。如果得到1，那么你就知道至少有一个是TRUE。

- AbuZubair

Answer 6

如果您不受限于布尔类型的数组，那么应该看看 java.util.BitSet 类。尽管名称为“位集”，但它更像是一个数组而不是集合。

方法 BitSet.isEmpty 将回答您是否在“数组”中有任何一个 true，并且其实现如下：

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

我怀疑你能否获得更快的检查...

但代价必须在其他方面支付：设置/取消设置一个值可能比仅使用boolean []更昂贵。

- tquadrat

Answer 7

如果您知道数组的大小，并且该数组很大。例如，24相当小，因此很难改进。Arrays.mismatch似乎更快一些。

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

我没有设置适当的基准测试，但是从这个输出来看，any1 大约比标准循环技术 any2 快 4-5 倍。

要理解为什么，我们需要查看 jdk 源代码。我们发现 vectorizedMismatch，它似乎使用了 unsafe 类将值转换为 long 并比较 long 值。

- matt