Check if all the elements of a Julia array are equal
all
is the right solution, but you want the method all(p, itr)
for predicate p
and iterable itr
, since it will employ short-circuiting behaviour (break as soon as a false
is found). So:
all(y->y==x[1], x)
To see the difference, you can run the following little speed test:
for n = 100000:250000:1100000
x = rand(1:2, n);
@time all(x .== x[1]);
@time all(y->y==x[1], x);
println("------------------------")
end
Ignore the first iteration as it is timing compile time.
0.000177 seconds (22 allocations: 17.266 KiB)
0.006155 seconds (976 allocations: 55.062 KiB)
------------------------
0.000531 seconds (23 allocations: 47.719 KiB)
0.000003 seconds (1 allocation: 16 bytes)
------------------------
0.000872 seconds (23 allocations: 78.219 KiB)
0.000001 seconds (1 allocation: 16 bytes)
------------------------
0.001210 seconds (23 allocations: 108.781 KiB)
0.000001 seconds (1 allocation: 16 bytes)
------------------------
0.001538 seconds (23 allocations: 139.281 KiB)
0.000002 seconds (1 allocation: 16 bytes)
The first solution is fairly obviously O(n), while the second is O(1) at best and O(n) at worst (depending on the data generating process for itr
).
Great question @tparker and great answer @ColinTBowers. While trying to think about them both, it occurred to me to try the straight-forward old-school Julian way-of-the-for
-loop. The result was faster on the important input of a long vector of identical elements, so I'm adding this note. Also, the function name allequal
seems to be appropriate enough to mention. So here are the variants:
allequal_1(x) = all(y->y==x[1],x)
# allequal_2(x) used to be erroneously defined as foldl(==,x)
@inline function allequal_3(x)
length(x) < 2 && return true
e1 = x[1]
i = 2
@inbounds for i=2:length(x)
x[i] == e1 || return false
end
return true
end
And the benchmark:
julia> using BenchmarkTools
julia> v = fill(1,10_000_000); # long vector of 1s
julia> allequal_1(v)
true
julia> allequal_3(v)
true
julia> @btime allequal_1($v);
9.573 ms (1 allocation: 16 bytes)
julia> @btime allequal_3($v);
6.853 ms (0 allocations: 0 bytes)
UPDATE: Another important case to benchmark is when there is a short-circuit opportunity. So (as requested in commment):
julia> v[100] = 2
2
julia> allequal_1(v),allequal_2(v),allequal_3(v)
(false, false, false)
julia> @btime allequal_1($v);
108.946 ns (1 allocation: 16 bytes)
julia> @btime allequal_3($v);
68.221 ns (0 allocations: 0 bytes)
All things being equal, a for
version should get to be allequal
in Base.