Filter array of CartesianIndex based on x-value

General Usage Performance
1

I have a vector of Cartesian indexes, for example:

temp = [CartesianIndex(3, 1), CartesianIndex(2, 2), CartesianIndex(6, 3), CartesianIndex(3, 4), 
        CartesianIndex(1, 5), CartesianIndex(5, 6), CartesianIndex(1, 7), CartesianIndex(1, 8), 
        CartesianIndex(4, 9), CartesianIndex(1, 10), CartesianIndex(2, 11), CartesianIndex(6, 12), 
        CartesianIndex(1, 13)]

I would like to split this vector into two vectors. The first vector collects all indexes on the first row, which is

v1 = [CartesianIndex(1, 5), CartesianIndex(1, 7), CartesianIndex(1, 8), CartesianIndex(1, 10), CartesianIndex(1, 13)]

Then, the second vector collects all the remaining indexes. How should I do it? Thank you very much.

2

Just write a loop that pushes each element ind to one vector or the other based on whether first(Tuple(ind)) == 1.

3 
julia> v1 = [x for x in temp if x.I[1]==1]
5-element Array{CartesianIndex{2},1}:
 CartesianIndex(1, 5)
 CartesianIndex(1, 7)
 CartesianIndex(1, 8)
 CartesianIndex(1, 10)
 CartesianIndex(1, 13)

or

julia> v1 = filter(x->x.I[1]==1, temp)
5-element Array{CartesianIndex{2},1}:
 CartesianIndex(1, 5)
 CartesianIndex(1, 7)
 CartesianIndex(1, 8)
 CartesianIndex(1, 10)
 CartesianIndex(1, 13)
1 Like
4

Thanks, this is exactly what I am looking for.

5 
function sort1(v)
    v1 = similar(v, 0)
    v2 = similar(v, 0)
    for ind in v
        if first(Tuple(ind)) == 1
            push!(v1, ind)
        else
            push!(v2, ind)
        end
    end
    return v1, v2
end

julia> v1, v2 = sort1(temp);

julia> v1
5-element Array{CartesianIndex{2},1}:
 CartesianIndex(1, 5)
 CartesianIndex(1, 7)
 CartesianIndex(1, 8)
 CartesianIndex(1, 10)
 CartesianIndex(1, 13)

julia> v2
8-element Array{CartesianIndex{2},1}:
 CartesianIndex(3, 1)
 CartesianIndex(2, 2)
 CartesianIndex(6, 3)
 CartesianIndex(3, 4)
 CartesianIndex(5, 6)
 CartesianIndex(4, 9)
 CartesianIndex(2, 11)
 CartesianIndex(6, 12)
6

I know this usage is super common, but I’m always uncomfortable with it. As far as I can tell, the field I isn’t actually part of the documented interface of CartesianIndex, which means it’s accessing an internal, undocumented field.

Did I miss where this is documented? or if not, why is x.I so widespread, when Tuple(x) seems more robust and idiomatic?

1 Like
7

This is slower then two filters. So it’s better to just filter or preallocate vectors of the size of original array, assign by index and resize at the end.

8

What? How can it be slower than two filters? That’s extremely surprising to me.

9 
julia> @btime filter(x->x.I[1]==1, $temp)
  37.096 ns (1 allocation: 288 bytes)

julia> @btime filter(x->first(Tuple(x))==1, $temp)
  38.611 ns (1 allocation: 288 bytes)

julia> @btime sort1($temp)
  69.938 ns (3 allocations: 304 bytes)

yeah, first(Tuple(idx)) is also good

10

I guess it’s all about the allocations. filter seems to allocate two full-size array, and then resizes them, which is just faster than push!, even with sizehint!.

Here’s the fastest solution I found, faster than filter:

function sortnew(v)
    v1, v2 = similar(v), similar(v)
    i0 = i1 = i2 = firstindex(v)
    @inbounds for i in eachindex(v)
        val = v[i]
        v1[i1] = v2[i2] = val
        isone = first(Tuple(val)) == 1
        i1 += isone
        i2 += !isone
    end
    resize!(v1, i1 - i0)
    resize!(v2, i2 - i0)
    return v1, v2
end
2 Likes