Collect values in a dict

tp2750 · July 14, 2021, 10:01am

I have a list of pairs of dog-owners and dog-names.
The dog-names are non-unique, and I want to collect a dict keyed on the dog-names where the values are the owners having a dog of that name.

Here’s an example using numbers to make it simple:

Given this:


julia> l = [x => x%3 for x in 1:10]
10-element Vector{Pair{Int64, Int64}}:
  1 => 1
  2 => 2
  3 => 0
  4 => 1
  5 => 2
  6 => 0
  7 => 1
  8 => 2
  9 => 0
 10 => 1

I want this:

julia> d
Dict{Int64, Vector{Int64}} with 3 entries:
  0 => [3, 6, 9]
  2 => [2, 5, 8]
  1 => [1, 4, 7, 10]

Here’s a way to do it, but I find it complicated and hard to read:

l = [x => x%3 for x in 1:10]
d = Dict{Int, Vector{Int}}()

for e in l
    push!(d, e[2] => push!(get(d,e[2],Int[]), e[1]))
end

What is the “idiomatic” way of doing this?

Thanks a lot.

Per · July 14, 2021, 11:37am

Not sure if it is more “idiomatic”, but I find that get! is a very useful function for things like this:

for (x,y) in l
    v = get!(d, y) do
        Int[]
    end
    push!(v, x)
end

tp2750 · July 14, 2021, 1:52pm

Thanks @Per ,

The combination of get! and push! is indeed very nice.

I actually find it easier to read without the temporary v:

l = [x => x%3 for x in 1:10];
d = Dict{Int, Vector{Int}}();
for (x,y) in l
    push!(get!(d,y,Int[]), x)
end
d

Dict{Int64, Vector{Int64}} with 3 entries:
  0 => [3, 6, 9]
  2 => [2, 5, 8]
  1 => [1, 4, 7, 10]

Or even:

l = [x => x%3 for x in 1:10];
d = Dict{Int, Vector{Int}}()
[push!(get!(d,y,Int[]), x) for (x,y) in l];
d

Dict{Int64, Vector{Int64}} with 3 entries:
  0 => [3, 6, 9]
  2 => [2, 5, 8]
  1 => [1, 4, 7, 10]

I’ll wait a bit marking yours as Solution to see if others have alternatives.

bernhard · July 14, 2021, 2:19pm

I find your initial version quite concise already.
In your real example is l really a list or a dict? I guess it does not matter too much.

I will provide a ‘nastier’ (and probably slower) solution for the existing suggestion to shine

ldict = Dict(x => x%3 for x in 1:10)

    d = Dict{Int, Vector{Int}}()
    vals = collect(values(ldict))
    ks = collect(keys(ldict))
    for v in unique(vals)
        d[v] = ks[findall(isequal(v),vals)]
    end
    d

stevengj · July 14, 2021, 2:22pm

This version allocates a new empty Int[] array on every iteration regardless of whether it is actually needed.

If you don’t want to define a variable v, you can still do:

push(get!(d, y) do; Int[]; end, x)

or equivalently push(get!(() -> Int[], d, y), x) (skipping the do syntax).

stevengj · July 14, 2021, 2:23pm

In addition to allocating an Int[] array on each iteration, this version also allocates an array of the results of the comprehension (a list of push! results), even though you don’t need it. Don’t use comprehensions to write loops if you don’t want to construct an array of results.

yha · July 14, 2021, 4:17pm

I think it’s a bit nicer with a DefaultDict rather than explicit get!:

using DataStructures
d = DefaultDict(()->Int[])
for (k,v) in l
    push!(d[v], k)
end

kristoffer.carlsson · July 14, 2021, 4:46pm

Or (my favorite) push(get!(Vector{Int} , d, y), x)

tp2750 · July 15, 2021, 3:44pm

Thank you all!

For my current application this is not performance critical, but I guess this being Julia, the idiomatic way is the performant one .

So I benchmarked all of the proposed solutions (on 1000 elements in 20 classes).

The solutions fall into a number of categories:

The 3 solutions I proposed are all taking more than 50 µs and 1100 allocations
The solutions by @Per , @stevengj , @kristoffer.carlsson using a function to provide defaults, are the most efficient at 25 µs and 128 allocations
The solution by @yha using DefaultDict takes about the same time as mine, but half the allocations.
The solution by @bernhard using findall takes 92 µs and 188 allocations (and is similar to how I would probably have done in R),

I’ll try to remember the one by @kristoffer.carlsson , which looks “right” to me.

It of course also works in a comprehension, though that does have a bit of a bad smell:

l = [x => x%3 for x in 1:10];
d = Dict{Int, Vector{Int}}()
[ push!(get!(Vector{Int} , d, y), x) for (x,y) in l ];
d

Thanks again, below is the code and benchmark numbers.

Code

using  DataStructures, BenchmarkTools

function f1(;cases=10, classes = 3)
    l = [x => x % classes for x in 1:cases];
    d = Dict{Int, Vector{Int}}();
    for e in l
        push!(d, e[2] => push!(get(d,e[2],Int[]), e[1]))
    end
    d
end

function f2(;cases=10, classes = 3)
    l = [x => x % classes for x in 1:cases];
    d = Dict{Int, Vector{Int}}();
    for (x,y) in l
         v = get!(d, y) do
             Int[]
         end
        push!(v, x)
    end
    d
end

function f3(;cases=10, classes = 3)
    l = [x => x % classes for x in 1:cases];
    d = Dict{Int, Vector{Int}}();
    for (x,y) in l
        push!(get!(d,y,Int[]), x)
    end
    d
end

function f4(;cases=10, classes = 3)
    l = [x => x % classes for x in 1:cases];
    d = Dict{Int, Vector{Int}}();
    [push!(get!(d,y,Int[]), x) for (x,y) in l];
    d
end

function f5(;cases=10, classes = 3)
ldict = Dict(x => x % classes for x in 1:cases)

    d = Dict{Int, Vector{Int}}()
    vals = collect(values(ldict))
    ks = collect(keys(ldict))
    for v in unique(vals)
        d[v] = ks[findall(isequal(v),vals)]
    end
    d
end

function f6(;cases=10, classes = 3)
    l = [x => x % classes for x in 1:cases];
    d = Dict{Int, Vector{Int}}();
    for (x,y) in l
        push!(get!(() -> Int[], d, y), x)
    end    
    d
end

function f7(;cases=10, classes = 3)
    l = [x => x % classes for x in 1:cases];
    d = DefaultDict(()->Int[])
    for (k,v) in l
        push!(d[v], k)
    end
    d
end


function f8(;cases=10, classes = 3)
    l = [x => x % classes for x in 1:cases];
    d = Dict{Int, Vector{Int}}();
    for (x,y) in l
        push!(get!(Vector{Int} , d, y), x)
    end    
    d
end




@info "Original solution"
@btime f1(cases = 1000; classes = 20)
@info "Per"
@btime f2(cases = 1000; classes = 20)
@info "tp2750 v2"
@btime f3(cases = 1000; classes = 20)
@info "tp2750 v3"
@btime f4(cases = 1000; classes = 20)
@info "berhard"
@btime f5(cases = 1000; classes = 20)
@info "stevengj"
@btime f6(cases = 1000; classes = 20)
@info "yha"
@btime f7(cases = 1000; classes = 20)
@info "kristoffer.carlsson"
@btime f8(cases = 1000; classes = 20)

[ Info: Original solution
  55.791 μs (1108 allocations: 117.09 KiB)
[ Info: Per
  24.631 μs (128 allocations: 40.53 KiB)
[ Info: tp2750 v2
  50.627 μs (1108 allocations: 117.09 KiB)
[ Info: tp2750 v3
  52.914 μs (1109 allocations: 125.03 KiB)
[ Info: berhard
  92.287 μs (188 allocations: 88.67 KiB)
[ Info: stevengj
  24.479 μs (128 allocations: 40.53 KiB)
[ Info: yha
  53.809 μs (617 allocations: 48.17 KiB)
[ Info: kristoffer.carlsson
  24.647 μs (128 allocations: 40.53 KiB)

yha · July 15, 2021, 5:33pm

The difference here is due to the DefaultDict being untyped, which is compared to a typed dict in the other benchmarks. If you use d = DefaultDict{Int,Vector{Int}}(()->Int[]) it performs the same as the get!-based solutions on my machine.
Surprisingly, I see that DefaultDict{Int,Vector{Int}}(Vector{Int}) performs worse, which doesn’t happen with get!(Vector{Int}...).

tp2750 · July 16, 2021, 3:53pm

Thank you for the clarification @yha

DefaultDict definitely gives the shortest and cleanest solution.

Topic		Replies	Views
Anybody can show me the grammer for dict's dict in julia General Usage question	8	5547	March 10, 2019
Values(dict) returns key-value pairs after sorting New to Julia dictionary	5	2420	August 11, 2019
How to collect keyword arguments in a Dict? General Usage	9	5318	April 13, 2020
Initializing a Dict, is there a more Julia way to do it? New to Julia	11	1653	August 2, 2021
Dict keys equality General Usage question	17	3551	June 2, 2017

Collect values in a dict

Related topics