# Perform a multi-column, multi-dimensional search quickly

**URL:** <https://discourse.julialang.org/t/perform-a-multi-column-multi-dimensional-search-quickly/75113>\
**Category:** Performance\
**Tags:** question, performance, broadcast\
**Created:** [January 24, 2022, 11:51am UTC](https://discourse.julialang.org/t/perform-a-multi-column-multi-dimensional-search-quickly/75113 "2022-01-24T11:51:28Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![Hikaru\_Matsuoka](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/hikaru_matsuoka/32/32263_2.png) [@Hikaru\_Matsuoka](https://discourse.julialang.org/u/Hikaru_Matsuoka)\
**Post date:** [January 24, 2022, 11:51am UTC](https://discourse.julialang.org/t/perform-a-multi-column-multi-dimensional-search-quickly/75113/1 "2022-01-24T11:51:28Z")

</div>

I would like to perform a multi-column search from a multi-dimensional matrix like the one below, is there a fast way to do this? (In the example below, I want to get the rows next to -5.0 3.0 2.0)

Test\_matrix =  
[-5.0 4.0 2.0  
-5.0 3.0 2.0  
-5.0 3.0 3.0  
-5.0 3.0 1.0  
-4.0 3.0 2.0  
-6.0 3.0 2.0  
-5.0 3.0 2.0  
5.0 -9.0 0.0  
5.0 -3.0 0.0  
5.0 -3.0 2.0]

In the example above, we want to get the columns 2 ,7,10.

This is why I wrote the following.  
result\_index\_can = (Test\_matrix[:,[1]]. == -5). \*(Test\_matrix[:,[2]]. == 3). \*(Test\_matrix[:,[3]]. == 2).

but in the real data, the speed of the search is a bottleneck due to the large matrix(over 1000000). Does anyone have a good solution for this?

---

<div class="post-metadata">

**Author:** ![rafael.guerra](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rafael.guerra/32/216610_2.png) [@rafael.guerra](https://discourse.julialang.org/u/rafael.guerra)\
**Post date:** [January 24, 2022, 12:10pm UTC](https://discourse.julialang.org/t/perform-a-multi-column-multi-dimensional-search-quickly/75113/2 "2022-01-24T12:10:30Z")

</div>

One way of writing this is:

```julia
eachrow(Test_matrix) .== Ref([-5, 3, 2])

```

Another is:

```julia
findall(==([-5, 3, 2]), eachrow(Test_matrix))

```

_NB: enclose your whole code inside triple backticks for proper display in discourse, which also enables the copy button_

---

<div class="post-metadata">

**Author:** ![Hikaru\_Matsuoka](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/hikaru_matsuoka/32/32263_2.png) [@Hikaru\_Matsuoka](https://discourse.julialang.org/u/Hikaru_Matsuoka)\
**Post date:** [January 24, 2022, 12:36pm UTC](https://discourse.julialang.org/t/perform-a-multi-column-multi-dimensional-search-quickly/75113/3 "2022-01-24T12:36:56Z")

</div>

Thank you for your beautiful codes!  
But , index\_can = eachrow(Test\_matrix) .== Ref([-5, 3, 2])  
is slower than  
result\_index\_can = (Test\_matrix[:,[1]]. == -5). \*(Test\_matrix[:,[2]]. == 3). \*(Test\_matrix[:,[3]]. == 2).

---

<div class="post-metadata">

**Author:** ![nilshg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nilshg/32/2283_2.png) [@nilshg](https://discourse.julialang.org/u/nilshg)\
**Post date:** [January 24, 2022, 12:58pm UTC](https://discourse.julialang.org/t/perform-a-multi-column-multi-dimensional-search-quickly/75113/5 "2022-01-24T12:58:49Z")

</div>

Is this missing interpolation, or the very small size of the MWE? I see:

```julia
julia> f1(x) = (x[:, 1] .== -5.0) .* (x[:, 2] .== 3.0) .* (x[:, 3] .== 2.0);

julia> f2(x) = eachrow(x) .== Ref([-5.0, 3.0, 2.0]);

julia> f3(x) = findall(==([-5.0, 3.0, 2.0]), eachrow(x));

julia> @btime f1($x);
  10.526 ms (10 allocations: 23.01 MiB)

julia> @btime f2($x);
  18.738 ms (8 allocations: 38.27 MiB)

julia> @btime f3($x);
  16.527 ms (1000008 allocations: 76.32 MiB)

```

consistent with what @Hikaru_Matsuoka says.

---

<div class="post-metadata">

**Author:** ![nilshg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nilshg/32/2283_2.png) [@nilshg](https://discourse.julialang.org/u/nilshg)\
**Post date:** [January 24, 2022, 1:02pm UTC](https://discourse.julialang.org/t/perform-a-multi-column-multi-dimensional-search-quickly/75113/6 "2022-01-24T13:02:17Z")

</div>

Btw is your example wrong? You say you want rows 2, 7, 10, but row 10 has 5 and -3 instead of -5 and 3? All the methods discussed so far wouldn’t return row 10 of `Test_matrix`

---

<div class="post-metadata">

**Author:** ![nilshg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nilshg/32/2283_2.png) [@nilshg](https://discourse.julialang.org/u/nilshg)\
**Post date:** [January 24, 2022, 1:07pm UTC](https://discourse.julialang.org/t/perform-a-multi-column-multi-dimensional-search-quickly/75113/7 "2022-01-24T13:07:42Z")

</div>

On my machine for the 1e6 example I find this to be an order of magnitude faster:

```julia
julia> function f4(x)
           res = Int64[]
           for i ∈ 1:size(x, 1)
               @inbounds if x[i, 1] == -5 && x[i, 2] == 3.0 && x[i, 3] == 2.0
                   push!(res, i)
               end
           end
           res
       end
f4 (generic function with 1 method)

julia> @btime f4($x);
  1.694 ms (6 allocations: 21.86 KiB)

```

Note that `f3` and `f4` above return only the integer indices of the matching rows (i.e. roughly a length 1,000,000/11^3 ≈ 751 vector for the example above with 11 randomly chosen integers from -5 to 5), while versions 1, and 2 give you a `size(x, 1)`-lenght vector of booleans.

To get such a vector with the speed of `f4` you can do:

```julia
julia> function f5(x)
           res = fill(false, size(x, 1))
           for i ∈ 1:size(x, 1)
               @inbounds if x[i, 1] == -5 && x[i, 2] == 3.0 && x[i, 3] == 2.0
                   res[i] = true
               end
           end
           res
       end
f5 (generic function with 1 method)

julia> @btime f5($x);
  1.686 ms (2 allocations: 976.67 KiB)

```

---

<div class="post-metadata">

**Author:** ![rafael.guerra](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rafael.guerra/32/216610_2.png) [@rafael.guerra](https://discourse.julialang.org/u/rafael.guerra)\
**Post date:** [January 24, 2022, 1:16pm UTC](https://discourse.julialang.org/t/perform-a-multi-column-multi-dimensional-search-quickly/75113/8 "2022-01-24T13:16:56Z")

</div>

Thanks @nilshg, using @benchmark without interpolation seems to work most of the time (similar results to @btime with interpolation). It works alright for my two expressions but not for OP’s…

---

<div class="post-metadata">

**Author:** ![nilshg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nilshg/32/2283_2.png) [@nilshg](https://discourse.julialang.org/u/nilshg)\
**Post date:** [January 24, 2022, 1:22pm UTC](https://discourse.julialang.org/t/perform-a-multi-column-multi-dimensional-search-quickly/75113/9 "2022-01-24T13:22:49Z")

</div>

Yeah I’ve never quite understood when you’re okay not to interpolate, so I just always do it (I always thought the issue was access to global variables, which I would have expected to affect all three expressions similarly, but clearly not!)

I should also add that while I tend to always sprinkle `@inbounds` into performance sensitive loops, this doesn’t actually seem to have any effect here - the compiler might be smart enough to eliminate the boundscheck for this simple loop.

And finally if one of the actual experts stops by and proposes some sort of `@tturbo` solution that runs in 50ns or something, maybe they could also explain why `fill(false, size(x, 1)` is two allocations?

---

<div class="post-metadata">

**Author:** ![rafael.guerra](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rafael.guerra/32/216610_2.png) [@rafael.guerra](https://discourse.julialang.org/u/rafael.guerra)\
**Post date:** [January 24, 2022, 2:45pm UTC](https://discourse.julialang.org/t/perform-a-multi-column-multi-dimensional-search-quickly/75113/10 "2022-01-24T14:45:40Z")

</div>

> [@Hikaru\_Matsuoka](#):
>
> But , index\_can = eachrow(Test\_matrix) .== Ref([-5, 3, 2])  
> is slower than  
> result\_index\_can = (Test\_matrix[:,[1]]. == -5). \*(Test\_matrix[:,[2]]. == 3). \*(Test\_matrix[:,[3]]. == 2).

Indeed, your code without loops is already fast.  
As a side note, we normally use less brackets to index a matrix:

```julia
(x[:,1] .== -5) .& (x[:,2] .== 3) .& (x[:,3] .== 2)  

```

And here are some other simple options, using comprehensions, which are faster than your original code and only slightly slower than Nils’ solution above:

```julia
# outputs only matching integer indices:
[i for i in axes(x,1) if x[i,1]==-5 && x[i,2]==3 && x[i,3]==2]

# outputs all indices, as Vector{Bool} with 0 or 1:
[x[i,1] == -5 && x[i,2] == 3 && x[i,3] == 2 for i in axes(x,1)]

```

---

<div class="post-metadata">

**Author:** ![rocco\_sprmnt21](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rocco_sprmnt21/32/20127_2.png) [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)\
**Post date:** [April 30, 2022, 8:22pm UTC](https://discourse.julialang.org/t/perform-a-multi-column-multi-dimensional-search-quickly/75113/11 "2022-04-30T20:22:04Z")

</div>

a slight variant of the solution of @rafael.guerra

```julia
[i for i in axes($x,1) if ($x[i,1]==-5 * $x[i,2]==3 * $x[i,3]==2)==1]

```