Check if a record exists in a Julia array

Viewed 101

Say we have a matrix:

A = [1.0 2.0 3.0; 4.0 5.0 6.0] #2×3 Matrix{Float64}

and a record:

b = [1.0 2.0 3.0] #1×3 Matrix{Float64}

what is the most efficient way to check if record b exists in matrix A in Julia?

Doing b in A returns false.

And writing a nested for-loop when we may have a large matrix (many dimensions and many rows) to check seems inefficient.

4 Answers

For a 2D matrix like your example, the check is simple.

vec(b) in eachrow(A)
true

For large nD arrays, one can use

vec(b) in eachslice(A, dims=1)
true

If the rows in the matrix are unsorted I would just do:

findfirst(==(vec(b)), eachrow(A))

If the rows are sorted (which is recommended when you do the search many times) I would consider using searchsorted over a vector of views of array rows.

This answer simply augments and builds on top of suggestions provided by Przemyslaw Szufel and AboAmmar and is intended to provide an efficiency comparison for reference:

using BenchmarkTools

A = [1.0 2.0 3.0; 4.0 5.0 6.0]
b = [1.0 2.0 3.0]

function my_findfirst(A, b)
    if(findfirst(==(vec(b)), eachrow(A)) !== nothing)
        return true
    end
    return false
end



function my_eachslice(A, b)
    if vec(b) in eachslice(A, dims=1)
        return true
    end
    return false
end

function my_eachrow(A,b)
    if (vec(b) in eachrow(A))
        return true
    end
    return false
end

@btime my_findfirst($A, $b) #66.846 ns (2 allocations: 80 bytes)
@btime my_eachslice($A, $b) #305.164 ns (5 allocations: 144 bytes)
@btime my_eachrow($A, $b) # 66.846 ns (2 allocations: 80 bytes)

The cost of finding a row in a table depends greatly on exact circumstance. In the OP example, the table is tiny and the row is inside the table. Usually, tables are larger and the worst-case is when row isn't in the table. Essentially Databases are optimized for these operations and indexing is an important part of database query optimization.

The following is a simple variant of the other answers to this question. It uses the first column of matrix to filter candidate rows for further equality checking. In all but trivial cases, it will be faster. This is because accessing matrices by column is faster due to locality of memory access in Julia default matrix memory layout.

Takeaway point: Lots and lots of room for optimization, if it is necessary.

function my_scancolumnfirst(A, b)
  N = size(A,1)
  c = @view A[:,1]
  bv = vec(b)
  b1 = bv[1]
  @inbounds for i=1:N
    if c[i]==b1 && bv==@view A[i,:]
      return true
    end
  end
  return false
end

A sample benchmark:

A = rand(500,500);
b = A[350,:];

using BenchmarkTools

@btime my_findfirst($A, $b)
# 2.682 μs (0 allocations: 0 bytes)
# true

@btime my_scancolumnfirst($A, $b)
#  907.333 ns (0 allocations: 0 bytes)
# true

Custom version shows >2x improvement.

Related