fastest way to check if all elements in an array are equal

Question

What would be the fastest way preferably native to java to check if all elements of an array are equal to a value? (denoted here by n)

So far I have:

boolean check = true;
int len = times.length;
for(int a = 0; check && a < len; a++) {
    check = times[a]==n && check;
}

So if each element is equal to a value, check is set to true, otherwise it is set to false.

EDIT: Would this be faster?

boolean check = true;
int len = times.length
int a = 0;
while(a < len && times[a]==n) {
    a++;
}
check=(a==len);

Ok, after looking at the answers here I understand the code is as small as its gonna get, so I'll have to look into threads and parallel processing, thanks everyone for the help and the links

Solution 1

This algorithm is O(n) which is the fastest way to check all elements of a list because you only have to check each element only one time.

Now just because this is the fastest algorithm in finding if all elements equal a value doesn't mean you have optimized it to its fullest potential.

This then leaves room for a multi-threaded/multiprocessor implementation.

A solution using more cores or threads is splitting the array into the amount of thread/cores you want to process simultaneously i.e. if you have an array of 100 elements and want 10 threads running at the same time-- split the array into 10 pieces and run each section on the array.

Some psudo code:

 int from,to, threadCount = 10;
 boolean check[threadCount];  

 int factor = array.length()/threadCount;
 for(int i = 0; i < threadCount; i++){
      from = i*factor;
      to = i*factor+factor;
      newThreadProcess(from, to, array, check[i]);     
 }

 barrier(); //Wait till all the threads are done processing
 for(int i = 0; i < threadCount; i++){
    if(!check[i]) return false;
 }
 return true;

This is best when the array is very large

Solution 2

In Java 8, you could use the Stream API:

boolean check = Arrays.asList(times).stream().allMatch(t -> t == n);

This alone won't be faster than iterating over the array directly. But if you then switch to a parallel stream, it could be significantly faster on large arrays. And if performance is a concern, it's presumably large arrays that you care about.

boolean check = Arrays.asList(times).parallelStream().allMatch(t -> t == n);

A parallel stream allows the array scanning to be parcelled out to multiple threads, scanning the array using parallel CPUs or cores.

Solution 3

A simple and clean way:

public static boolean allEqual(E[] array, E element) {
    for(E e : array) {
        if(e != element) {
            return false;
        }
    }
    return true;
}

Solution 4

check = times[a]==n && check;

can be

check = times[a]==n;

since you never would've gotten to that line unless check were true.

Solution 5

You can write it in a shorter way :

for(int a = 0; a < len && (check = times[a]==n); a++);

View more solutions

Comments

[spyr03]

you'd have to reverse the two sides of the condition so a < len would go at the start

[Kirill Rakhman]

docs.oracle.com/javase/8/docs/api/java/util/stream/… also says that allMatch() may short-circuit, meaning it won't event evaluate all elements if it finds a non-matching one.

[kaqqao]

Sententiously? How did "concurrently" get turned into that?