# Get first match in a dictionary of tuples

**URL:** <https://discourse.julialang.org/t/get-first-match-in-a-dictionary-of-tuples/6128>\
**Category:** General Usage\
**Created:** [September 28, 2017, 6:00am UTC](https://discourse.julialang.org/t/get-first-match-in-a-dictionary-of-tuples/6128 "2017-09-28T06:00:52Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![tuckermcclure](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tuckermcclure/32/1187_2.png) [@tuckermcclure](https://discourse.julialang.org/u/tuckermcclure)\
**Post date:** [September 28, 2017, 6:00am UTC](https://discourse.julialang.org/t/get-first-match-in-a-dictionary-of-tuples/6128/1 "2017-09-28T06:00:52Z")

</div>

I have a dictionary of tuples. Inside one of those tuples is one thing I care about. What’s the best way to find that one thing? How can I make it fast? I feel like I have some things to learn about associative collections.

Here’s a mockup of my code, where I have a dictionary of pet owners and their pets. I know there’s one and only one Cat, and I’d like to find that cat. I have some code to do it, but it feels really bulky compared to the rest of my code.

```julia
abstract type Pet end
struct Dog <: Pet; name::String; end
struct Cat <: Pet; name::String; end
struct Ox <: Pet; name::String; end

# Create an example dictionary.
pets = Dict("Cindy" => (Dog("Fido"), Cat("Captain Snuggly Pants")),
            "Tom" => (Ox("Socks"), Dog("Chewbacca")))

# Find the cat.
cat = Cat("empty cat") # Defined so that cat has global scope.
for these_pets in values(pets) # Get tuple of pets for each entry.
    cats = filter(e -> isa(e, Cat), these_pets) # Look for a Cat.
    if !isempty(cats) # If we found one, accept it and break.
        cat = first(cats)
        break
    end
end

```

I can definitely make the code _shorter_ by `vcat`ing all of those tuples together into a literal collection and then calling `first(filter(p -> isa(p, Cat), ...))` on it, but that seems hugely wasteful. Time is critical here; there will be many pet owners and many pets, the whole thing will need to run many times on different collections, and who wouldn’t want to find Captain Snuggly Pants as soon as possible?

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [September 28, 2017, 8:02am UTC](https://discourse.julialang.org/t/get-first-match-in-a-dictionary-of-tuples/6128/2 "2017-09-28T08:02:20Z")

</div>

How about (`cat` is a function in base, so I just changed it to `kat`):

```julia
kat = Cat("Nemo")
for val in values(pets)
    katind = findfirst(v->isa(v, Cat), val)
    !iszero(katind) && (kat = val[katind]; break)
end

```

Timing:

```julia
julia> @btime begin
       kat = Cat("Nemo")
       for val in values($pets)
           katind = findfirst(v->isa(v, Cat), val)
           !iszero(katind) && (kat = val[katind]; break)
       end
       end
  203.837 ns (0 allocations: 0 bytes)

```

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [September 28, 2017, 8:02am UTC](https://discourse.julialang.org/t/get-first-match-in-a-dictionary-of-tuples/6128/3 "2017-09-28T08:02:28Z")

</div>

Possibly something like

```julia
function first_matching(pred, iter)
    state = start(iter)
    while !done(iter, state)
        item, next_state = next(iter, state)
        pred(item) && return Nullable(item)
        state = next_state
    end
    return Nullable(state, false)
end

first_matching(p -> isa(p, Cat), Base.Iterators.flatten(values(pets)))

```

---

<div class="post-metadata">

**Author:** ![tuckermcclure](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tuckermcclure/32/1187_2.png) [@tuckermcclure](https://discourse.julialang.org/u/tuckermcclure)\
**Post date:** [September 28, 2017, 4:08pm UTC](https://discourse.julialang.org/t/get-first-match-in-a-dictionary-of-tuples/6128/4 "2017-09-28T16:08:30Z")

</div>

Thanks @DNF and @Tamas_Papp!

As written, @DNF’s answer is by far the fastest. However, it has more hard-coded stuff than @Tamas_Papp’s. Modifying Papp’s so as to compare apples to apples (building in the `flatten` and `isa(...)` and leaving out the Nullables), I have:

```julia
function first_matching(pets, pet_type)
    iter = Base.Iterators.flatten(pets)
    state = start(iter)
    while !done(iter, state)
        item, next_state = next(iter, state)
        isa(item, pet_type) && return item
        state = next_state
    end
    return pet_type("[empty pet]")
end

```

and in fact this modified version is the fastest so far. It comes in at 26us, where’s @DNF’s comes in at 32us. So you _both_ contributed to the fastest answer. (My original one comes in at a terrifying 700us and is sufficient evidence that I am still a beginner in Julia.)

Interestingly (to me), the `flatten` call has essentially no cost. I wrote another version where instead of using `flatten`, I used a loop `for iter in pets; (same as above); end;`, and this saved no time.

Thanks again, all. This is going to be one of the functions called most frequently by my program, and speed is critical!

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [September 28, 2017, 4:44pm UTC](https://discourse.julialang.org/t/get-first-match-in-a-dictionary-of-tuples/6128/5 "2017-09-28T16:44:11Z")

</div>

That’s odd. I timed mine at 200 _nanoseconds_.

---

<div class="post-metadata">

**Author:** ![ggggggggg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ggggggggg/32/265_2.png) [@ggggggggg](https://discourse.julialang.org/u/ggggggggg)\
**Post date:** [September 28, 2017, 5:06pm UTC](https://discourse.julialang.org/t/get-first-match-in-a-dictionary-of-tuples/6128/6 "2017-09-28T17:06:22Z")

</div>

I think this is a cleaner version of your answer, and I time it at about 1.3 us.

```julia
function first_matching_flatten(pets, PetType)
    for pet in Base.Iterators.flatten(pets)
        pet isa PetType && return pet
    end
    return PetType("none")
end
@btime first_matching_flatten($pets, Cat)

```

As for DNF’s example, I get roughly 200ns as well, but if I turn it into a function it is much slower 1.6 us instead. I don’t understand what is going on there.

```julia
println("DNF")
@btime begin
       kat = Cat("Nemo")
       for val in values($pets)
           katind = findfirst(v->isa(v, Cat), val)
           !iszero(katind) && (kat = val[katind]; break)
       end
end
println("DNF function")
function first_matching_dnf(pets, PetType)
    kat = PetType("none")
    for val in values(pets)
        katind = findfirst(v->isa(v, Cat), val)
        !iszero(katind) && (kat::PetType = val[katind]; break)
    end
    kat
end
@btime first_matching_dnf($pets, Cat)

```

In case you don’t know `@btime` comes from `BenchmarkTools.jl` and will give different timings from `@time`. The BenchmarkTools timings will generally avoid penalties associated with global scope.

---

<div class="post-metadata">

**Author:** ![tuckermcclure](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tuckermcclure/32/1187_2.png) [@tuckermcclure](https://discourse.julialang.org/u/tuckermcclure)\
**Post date:** [September 28, 2017, 5:11pm UTC](https://discourse.julialang.org/t/get-first-match-in-a-dictionary-of-tuples/6128/7 "2017-09-28T17:11:54Z")

</div>

Thanks for the `@btime` heads up. In fact, I _didn’t_ know and had just been using `@time`.

I would definitely be curious to understand why your timing changes when DNF’s answer is made into a function. I would think it would be faster as a function. Maybe something having to do with `pets` being `Any` in the function?

---

<div class="post-metadata">

**Author:** ![tuckermcclure](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tuckermcclure/32/1187_2.png) [@tuckermcclure](https://discourse.julialang.org/u/tuckermcclure)\
**Post date:** [September 28, 2017, 5:47pm UTC](https://discourse.julialang.org/t/get-first-match-in-a-dictionary-of-tuples/6128/8 "2017-09-28T17:47:11Z")

</div>

Using `@btime` from the BenchmarkTools, I see that there is a cost to that `flatten` and that this is in fact fastest so far:

```julia
function first_pet_of_type_3(pets, pet_type)
    for these_pets in values(pets)
        for pet in these_pets
            if pet isa pet_type
                return pet
            end
        end
    end
    return pet_type("[no pet]")
end

```

I’m getting 1.2us for this. Replacing the outer loop with `flatten(values(pets))` makes the function take 4.5us.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [September 28, 2017, 6:50pm UTC](https://discourse.julialang.org/t/get-first-match-in-a-dictionary-of-tuples/6128/9 "2017-09-28T18:50:47Z")

</div>

My timings are decidedly different:

```julia
function findcat(pets)
    for val in values(pets)
        katind = findfirst(v->isa(v, Cat), val)
        !iszero(katind) && return val[katind]
    end
    return Cat("Nemo")
end

```

```julia
julia> @btime findcat($pets)
  185.125 ns (0 allocations: 0 bytes)
Cat("Captain Snuggly Pants")

```

```julia
julia> @btime first_pet_of_type_3($pets, Cat)
  1.741 μs (4 allocations: 128 bytes)
Cat("Captain Snuggly Pants")

```

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [September 28, 2017, 7:00pm UTC](https://discourse.julialang.org/t/get-first-match-in-a-dictionary-of-tuples/6128/10 "2017-09-28T19:00:17Z")

</div>

BTW, I thought you wanted something less bulky in terms of code length, and presumed it would be inline, hence the hardcoding.

---

<div class="post-metadata">

**Author:** ![tuckermcclure](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tuckermcclure/32/1187_2.png) [@tuckermcclure](https://discourse.julialang.org/u/tuckermcclure)\
**Post date:** [September 28, 2017, 7:35pm UTC](https://discourse.julialang.org/t/get-first-match-in-a-dictionary-of-tuples/6128/11 "2017-09-28T19:35:24Z")

</div>

@DNF, right on all counts. Especially when the type (Cat) is hard-coded, the code is fastest. Making the type an input slows it down, but my tests are now showing your function above to be the fastest (twice as fast as it was earlier). Not sure what changed.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [September 28, 2017, 7:38pm UTC](https://discourse.julialang.org/t/get-first-match-in-a-dictionary-of-tuples/6128/12 "2017-09-28T19:38:36Z")

</div>

One thing I changed is to not pre-assign the output with the default (`Cat("Nemo")`). Then, if a cat is actually found, you avoid that assignment.