Fastest way to check if all elements in an array are equal
What would be the fastest way, like native for 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, the check is set to true, otherwise, false.
EDIT: would it 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 realize the code is as small as it is, so I'll have to look for streams and parallel processing, thanks everyone for the help and links
source to share
This algorithm O(n)
, which is the fastest way to check all the elements of the list, because you only need to check each element only once.
Now, just because it is the fastest algorithm
when searching, if all items are equal to value, does not mean that you have optimized it to its fullest potential.
This leaves room for implementation multi-threaded/multiprocessor
.
A solution using more cores or threads splits the array into the number of threads / cores you want to process at the same time, i.e. if you have an array of 100 elements and you want 10 threads to execute at the same time - divide the array into 10 pieces and start each section of the array.
Some psudo codes:
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
source to share
In Java 8, you can use the Stream API :
boolean check = Arrays.asList(times).stream().allMatch(t -> t == n);
That alone won't be faster than iterating over the array directly. But if you switch to parallel streaming, it can be significantly faster on large arrays. And if performance is an issue, these are probably large arrays that you care about.
boolean check = Arrays.asList(times).parallelStream().allMatch(t -> t == n);
A parallel thread allows you to split an array into multiple threads by scanning the array using parallel processors or cores.
source to share