Efficient way to get indices of true elements from BitArray

New to Julia
1

I usually use the following:

x = rand(Bool, 10)
(1:length(x))[x]

Result:

julia> x = rand(Bool, 10)
10-element Vector{Bool}:
 0
 1
 0
 0
 0
 1
 1
 0
 0
 0

julia> (1:length(x))[x]
3-element Vector{Int64}:
 2
 6
 7

But i think this is inefficient and slow, is there better way?

2

findall is how I’d do this and where I’d expect an optimization to appear if one existed… but there’s not a BitArray specific optimization there now.

2 Likes
3

Why do you think it’s slow? I agree with Matt that it’s a slightly unusual way to write findall, but it seems to give the same performance.

julia> x = rand(Bool, 1_000_000);

julia> using BenchmarkTools

julia> @btime findall($x);
  4.927 ms (2 allocations: 3.81 MiB)

julia> @btime (1:length($x))[$x];
  4.479 ms (2 allocations: 3.81 MiB)
4

Side note: this is not a BitArray, it is a Vector{Bool}, where each element takes up one byte.

If you want an actual BitArray, with 8 elements per byte, you can do

rand(10) .< 0.5

or, probably more efficiently:

using Random
bitrand(10)
2 Likes
5

What you’re benchmarking there is Vector{Bool}. I had thought there might be some performance left on the table without a BitArray-specific bit fiddling method… but this looks pretty good: the BitArray is beating a Vector{Bool} by 10x.

julia> using BenchmarkTools

julia> x = rand(Bool, 1_000_000);

julia> y = BitArray(x);

julia> @btime findall($x);
  4.126 ms (2 allocations: 3.82 MiB)

julia> @btime findall($y);
  460.060 μs (2 allocations: 3.82 MiB)
1 Like
6

I don’t see quite such a large discrepancy (more like 5x, might be CPU dependent?), but I do see findall outperforming the index-into-a-range solution for BitArray:

julia> @btime (1:length($y))[$y];
  905.300 μs (2 allocations: 3.82 MiB)

julia> @btime findall($y);
  687.100 μs (2 allocations: 3.82 MiB)
3 Likes