# Is something like reversed Dict? findall(x -\> x=="house", cc) is to slow:/

**URL:** <https://discourse.julialang.org/t/is-something-like-reversed-dict-findall-x-x-house-cc-is-to-slow/16443>\
**Category:** General Usage\
**Created:** [October 17, 2018, 2:20pm UTC](https://discourse.julialang.org/t/is-something-like-reversed-dict-findall-x-x-house-cc-is-to-slow/16443 "2018-10-17T14:20:45Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![programista](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/programista/32/5372_2.png) [@programista](https://discourse.julialang.org/u/programista)\
**Post date:** [October 17, 2018, 2:20pm UTC](https://discourse.julialang.org/t/is-something-like-reversed-dict-findall-x-x-house-cc-is-to-slow/16443/1 "2018-10-17T14:20:45Z")

</div>

```julia
Dict can find one val by key
> julia> D=Dict("a"=>1,"b"=>1,"c"=>2)
> Dict{String,Int64} with 3 entries:
> "c" => 2
> "b" => 1
> "a" => 1
> 
> julia> get(D,"a",false)
> 1

```

I need something fast in oposite side:  
somethink like findforme(1,D)  
output is [“a”,“b”]  
findall is to slow  
findall(x → x==“house”, cc)  
my collect cc has more then 10^ values and any serch during over 2 sek 😕  
Some hints?  
Paul

---

<div class="post-metadata">

**Author:** ![ExpandingMan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/expandingman/32/866_2.png) [@ExpandingMan](https://discourse.julialang.org/u/ExpandingMan)\
**Post date:** [October 17, 2018, 2:27pm UTC](https://discourse.julialang.org/t/is-something-like-reversed-dict-findall-x-x-house-cc-is-to-slow/16443/2 "2018-10-17T14:27:10Z")

</div>

I seem to recall that a while ago some of us discussed adding a bidirectional dict to [DataStructures.jl](http://juliacollections.github.io/DataStructures.jl/latest/) but no one ever did so. Might still be nice to have.

Fortunately, in Julia it’s extremely easy to create the reverse dictionary, behold!

```julia
dict = Dict(rand(Int, 10^5) .=> rand(Int, 10^5))
rdict = Dict(values(dict) .=> keys(dict))

```

Once it is created you can look up in constant time to your heart’s content.

I just realized that you have repeat values. This is more complicated, and the way of dealing with it will depend on what you are trying to achieve.

---

<div class="post-metadata">

**Author:** ![bennedich](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bennedich/32/4894_2.png) [@bennedich](https://discourse.julialang.org/u/bennedich)\
**Post date:** [October 17, 2018, 2:42pm UTC](https://discourse.julialang.org/t/is-something-like-reversed-dict-findall-x-x-house-cc-is-to-slow/16443/3 "2018-10-17T14:42:13Z")

</div>

Like ExpandingMan says above, the way to solve this is to create a _separate dictionary_ with keys and values reversed. In your case, since you have repeated values, it sounds like you want to map ints to either an array or a set of strings (depending on if you need them ordered and how you’ll access them).

---

<div class="post-metadata">

**Author:** ![programista](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/programista/32/5372_2.png) [@programista](https://discourse.julialang.org/u/programista)\
**Post date:** [October 17, 2018, 3:14pm UTC](https://discourse.julialang.org/t/is-something-like-reversed-dict-findall-x-x-house-cc-is-to-slow/16443/4 "2018-10-17T15:14:45Z")

</div>

Maybe Dict of tuples? This way can be fast ?

```julia
> julia> D=Dict(1=>("a", "b",), 2=> ("c",), 3=>("a","b","d",))
> Dict{Int64,Tuple{String,Vararg{String,N} where N}} with 3 entries:
> 2 => ("c",)
> 3 => ("a", "b", "d")
> 1 => ("a", "b")
> julia> get(D,1,"")
> ("a", "b")
> 
> 
> julia> for i in get(D,2,"")
> println(i)
> end
> c
> 
> julia> for i in get(D,1,"")
> println(i)
> end
> a
> b

```

Paul

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [October 17, 2018, 3:24pm UTC](https://discourse.julialang.org/t/is-something-like-reversed-dict-findall-x-x-house-cc-is-to-slow/16443/5 "2018-10-17T15:24:19Z")

</div>

For the millionth time, can you PLEASE quote your code?

---

<div class="post-metadata">

**Author:** ![jandehaan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jandehaan/32/6805_2.png) [@jandehaan](https://discourse.julialang.org/u/jandehaan)\
**Post date:** [October 17, 2018, 4:04pm UTC](https://discourse.julialang.org/t/is-something-like-reversed-dict-findall-x-x-house-cc-is-to-slow/16443/6 "2018-10-17T16:04:14Z")

</div>

```julia
julia> D=Dict(1=>(“a”, “b”,), 2=> (“c”,), 3=>(“a”,“b”,“d”,))
Dict{Int64,Tuple{String,Vararg{String,N} where N}} with 3 entries:
2 => (“c”,)
3 => (“a”, “b”, “d”)
1 => (“a”, “b”)

julia> get(D,1,"")
(“a”, “b”)

julia> for i in get(D,2,"")
               println(i)
         end
c

julia> for i in get(D,1,"")
              println(i)
         end
a
b

```

---

<div class="post-metadata">

**Author:** ![bennedich](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bennedich/32/4894_2.png) [@bennedich](https://discourse.julialang.org/u/bennedich)\
**Post date:** [October 17, 2018, 4:21pm UTC](https://discourse.julialang.org/t/is-something-like-reversed-dict-findall-x-x-house-cc-is-to-slow/16443/7 "2018-10-17T16:21:24Z")

</div>

Tuples seem like a poor choice since they’re immutable and IMO not a good fit for this problem. How would you construct such a dictionary programmatically? As I said, I think an array or a set is a better choice.

Read up on data structures and read the sample code in this link: [Collections and Data Structures · The Julia Language](https://docs.julialang.org/en/v1.0/base/collections/)

---

<div class="post-metadata">

**Author:** ![programista](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/programista/32/5372_2.png) [@programista](https://discourse.julialang.org/u/programista)\
**Post date:** [October 17, 2018, 4:29pm UTC](https://discourse.julialang.org/t/is-something-like-reversed-dict-findall-x-x-house-cc-is-to-slow/16443/8 "2018-10-17T16:29:49Z")

</div>

I can remove tuples , Arrays seems more slower …  
Paul

W dniu 2018-10-17 o 18:26, Max Bennedich pisze:

---

<div class="post-metadata">

**Author:** ![bennedich](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bennedich/32/4894_2.png) [@bennedich](https://discourse.julialang.org/u/bennedich)\
**Post date:** [October 18, 2018, 6:53am UTC](https://discourse.julialang.org/t/is-something-like-reversed-dict-findall-x-x-house-cc-is-to-slow/16443/9 "2018-10-18T06:53:26Z")

</div>

> [@programista](#):
>
> I can remove tuples , Arrays seems more slower …

Do you have a benchmark showing this?

By all means use tuples if they work for you, but I suspect that you’ll find them harder to work with.

---

<div class="post-metadata">

**Author:** ![programista](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/programista/32/5372_2.png) [@programista](https://discourse.julialang.org/u/programista)\
**Post date:** [October 18, 2018, 2:40pm UTC](https://discourse.julialang.org/t/is-something-like-reversed-dict-findall-x-x-house-cc-is-to-slow/16443/10 "2018-10-18T14:40:42Z")

</div>

I did it, is very usefull.  
serchng time ± 0.000015 seconds in Array was 2 sec. !!

```julia
@time get(replslow,"ptaszek","")
   0.000015 seconds (4 allocations: 160 bytes)
("PTASZKOWI", "PTASZKOWI", "ptaszka", "Ptaszek")

replslow
Dict{String,Tuple} with 371432 entries: more then 13*10^6 words

```

---

<div class="post-metadata">

**Author:** ![Juan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juan/32/7657_2.png) [@Juan](https://discourse.julialang.org/u/Juan)\
**Post date:** [October 18, 2018, 3:41pm UTC](https://discourse.julialang.org/t/is-something-like-reversed-dict-findall-x-x-house-cc-is-to-slow/16443/11 "2018-10-18T15:41:58Z")

</div>

But you created the reversed dictionary by hand.  
How would you you make it programatically from the original dictionary?

---

<div class="post-metadata">

**Author:** ![bennedich](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bennedich/32/4894_2.png) [@bennedich](https://discourse.julialang.org/u/bennedich)\
**Post date:** [October 18, 2018, 3:43pm UTC](https://discourse.julialang.org/t/is-something-like-reversed-dict-findall-x-x-house-cc-is-to-slow/16443/12 "2018-10-18T15:43:03Z")

</div>

> [@programista](#):
>
> I did it, is very usefull.  
> serchng time ± 0.000015 seconds in Array was 2 sec. !!

No, you didn’t understand what I wrote. _A dictionary mapping strings to an array or a set of strings._

If what you’ve implemented solves your problem, then by all means go for it, but as you can see in your example, and the examples you removed with your edit, your tuples are full of duplicates, which should not be possible given the problem description in your OP (since you can’t have duplicate keys in a dictionary). It suggests that either your problem is not as described in your OP, your implementation is incorrect, and/or a set would be a better choice than tuples (which removes duplicates).

---

<div class="post-metadata">

**Author:** ![jandehaan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jandehaan/32/6805_2.png) [@jandehaan](https://discourse.julialang.org/u/jandehaan)\
**Post date:** [October 18, 2018, 7:20pm UTC](https://discourse.julialang.org/t/is-something-like-reversed-dict-findall-x-x-house-cc-is-to-slow/16443/13 "2018-10-18T19:20:08Z")

</div>

I merely quoted Paul @programista’s code (surrounded it by ``` characters) to make it easier to read.  
One possible answer to your question was given by @ExpandingMan

```julia
dict = Dict(rand(Int, 10^5) .=> rand(Int, 10^5))
rdict = Dict(values(dict) .=> keys(dict))

```

---

<div class="post-metadata">

**Author:** ![programista](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/programista/32/5372_2.png) [@programista](https://discourse.julialang.org/u/programista)\
**Post date:** [October 18, 2018, 7:40pm UTC](https://discourse.julialang.org/t/is-something-like-reversed-dict-findall-x-x-house-cc-is-to-slow/16443/14 "2018-10-18T19:40:06Z")

</div>

THX , it was only , of course no duplicateson righ side . Thank for Your hint about maping !  
Paul

---

<div class="post-metadata">

**Author:** ![ExpandingMan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/expandingman/32/866_2.png) [@ExpandingMan](https://discourse.julialang.org/u/ExpandingMan)\
**Post date:** [October 18, 2018, 7:49pm UTC](https://discourse.julialang.org/t/is-something-like-reversed-dict-findall-x-x-house-cc-is-to-slow/16443/15 "2018-10-18T19:49:27Z")

</div>

Here’s a not particularly performant example of a way to deal with the non-injectiveness problem:

```julia
function revdict(dict::AbstractDict{K,V}) where {K,V}
    o = Dict{V,Vector{K}}()
    for (k, v) ∈ dict
        v ∈ keys(o) ? push!(o[v], k) : (o[v] = [k])
    end
    o
end

```

(I originally used `sizehint!` but that’s probably stupid since it’s using dynamically allocated arrays anyway.)

---

<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:** [October 19, 2018, 6:15am UTC](https://discourse.julialang.org/t/is-something-like-reversed-dict-findall-x-x-house-cc-is-to-slow/16443/16 "2018-10-19T06:15:20Z")

</div>

Using `get!` (`foreach` is orthogonal, `for` is fine):

```julia
function revdict2(dict::AbstractDict{K,V}) where {K,V}
    o = Dict{V,Vector{K}}()
    foreach(((k, v),) -> push!(get!(() -> Vector{K}(), o, v), k), dict)
    o
end

```

---

<div class="post-metadata">

**Author:** ![ExpandingMan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/expandingman/32/866_2.png) [@ExpandingMan](https://discourse.julialang.org/u/ExpandingMan)\
**Post date:** [October 19, 2018, 1:24pm UTC](https://discourse.julialang.org/t/is-something-like-reversed-dict-findall-x-x-house-cc-is-to-slow/16443/17 "2018-10-19T13:24:58Z")

</div>

> [@Tamas\_Papp](#):
>
> ( `foreach` is orthogonal, `for` is fine):

Julia gives you so many ways to write things in as few lines as possible, it’s always a fun challenge to see how few lines you can write your function in! 😄

Come to think of it, this is a reason why broadcasting is one of my favorite features of Julia. It gives you so many more options for writing succinct but also perfectly comprehensible expressions (granted it’s not really applicable here because we’re not dealing with arrays).

Although, no offense @Tamas_Papp but your second line here confuses the hell out of me 😆.

---

<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:** [October 19, 2018, 1:36pm UTC](https://discourse.julialang.org/t/is-something-like-reversed-dict-findall-x-x-house-cc-is-to-slow/16443/18 "2018-10-19T13:36:55Z")

</div>

> [@ExpandingMan](#):
>
> your second line here confuses the hell out of me

Too much time spent working in Common Lisp, I guess 😉

The loop version would be

```julia
for (k, v) in dict
    push!(get!(() -> Vector{K}(), o, v), k)
end

```

`get!` is a particularly handy accessor for accumulating in `Dict`s, inserting the result of the function (first argument, creates a `Vector{K}`) if the key is not found.

---

<div class="post-metadata">

**Author:** ![ExpandingMan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/expandingman/32/866_2.png) [@ExpandingMan](https://discourse.julialang.org/u/ExpandingMan)\
**Post date:** [October 19, 2018, 1:45pm UTC](https://discourse.julialang.org/t/is-something-like-reversed-dict-findall-x-x-house-cc-is-to-slow/16443/19 "2018-10-19T13:45:17Z")

</div>

> [@Tamas\_Papp](#):
>
> push!(get!(() -\> Vector{K}(), o, v), k)

Incidentally, it was this part that I had to stare at for a few minutes to understand what it was doing., not the `foreach` (though the combination of course takes a bit longer to parse).

On a related note, is there some reason that the function argument to `get!` doesn’t take the key as an argument? That seems like a missed opportunity.

---

<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:** [October 20, 2018, 5:43am UTC](https://discourse.julialang.org/t/is-something-like-reversed-dict-findall-x-x-house-cc-is-to-slow/16443/20 "2018-10-20T05:43:56Z")

</div>

On the contrary, I think the purpose of `get!` is to deal with the _same_ key twice if necessary, but save the additional lookup.

[Next page](https://discourse.julialang.org/t/is-something-like-reversed-dict-findall-x-x-house-cc-is-to-slow/16443.md?page=2)