# Sorting nested dictionary

**URL:** <https://discourse.julialang.org/t/sorting-nested-dictionary/24182>\
**Category:** General Usage\
**Tags:** question, sort, dictionary\
**Created:** [May 13, 2019, 4:31pm UTC](https://discourse.julialang.org/t/sorting-nested-dictionary/24182 "2019-05-13T16:31:02Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![FinlayDaG33k](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/finlaydag33k/32/8440_2.png) [@FinlayDaG33k](https://discourse.julialang.org/u/FinlayDaG33k)\
**Post date:** [May 13, 2019, 4:31pm UTC](https://discourse.julialang.org/t/sorting-nested-dictionary/24182/1 "2019-05-13T16:31:02Z")

</div>

Hii there,

I’m new to the world of Julia (I’m mostly a web dev) so please be patient 🙂  
Let’s talk about my issue shall we?

I have a dictionary, which in terms contain dictionaries as well:

```nohighlight
servers = Dict(
    "1" => Dict(
        "votes" => 0,
        "age" => 1
    ),
    "2" => Dict(
        "votes" => 0,
        "age" => 0
    ), 
    "3" => Dict(
        "votes" => 1,
        "age" => 0
    ),
    "4" => Dict(
        "votes" => 0,
        "age" => 1
    ),
    "5" => Dict(
        "votes" => 1
        "age" => 1
    )
);

```

I need to sort this dictionary according to a few rules:  
It needs to be sorted in this order: votes (desc) → age (desc) → key (asc)  
So in this case I would get the following:

1. both `3` and `5` have `1` vote (the rest has none), however, `5` has a higher `age` so it goes first, followed by `3`.
2. `1`, `2` and `4` have `0` votes but `1` and `4` both have an age of `1`. since `1` is lower than `4`, `1` goes first, then goes `4` and then goes `2`.

I hope this makes any sense?  
So my question here is, how would I write something like this in Julia?

Cheers!

---

<div class="post-metadata">

**Author:** ![simeonschaub](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/simeonschaub/32/216566_2.png) [@simeonschaub](https://discourse.julialang.org/u/simeonschaub)\
**Post date:** [May 13, 2019, 7:26pm UTC](https://discourse.julialang.org/t/sorting-nested-dictionary/24182/2 "2019-05-13T19:26:51Z")

</div>

Hi there,  
it would probably be helpful if you could tell us a bit more about what exactly your application is, so we can help you a bit better. I’m not entirely sure a `Dict` is the best fit here. Are you sure you want to index the outer dict with strings and don’t want an array instead? For the inner dict you also might want to have a look at the [documentation for structs](https://docs.julialang.org/en/v1/manual/types/#Composite-Types-1). This would also mean you could implement your own rules for ordering for this specific type.

---

<div class="post-metadata">

**Author:** ![simeonschaub](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/simeonschaub/32/216566_2.png) [@simeonschaub](https://discourse.julialang.org/u/simeonschaub)\
**Post date:** [May 13, 2019, 7:39pm UTC](https://discourse.julialang.org/t/sorting-nested-dictionary/24182/3 "2019-05-13T19:39:34Z")

</div>

Is something like this what you had in mind?

```julia
struct Server
    votes::Int
    age::Int
end

function Base.isless(a::Server, b::Server)
    if a.votes == b.votes
        return a.age < b.age
    else
        return a.votes < b.votes
    end
end

servers = [Server(0, 1), Server(0, 0), Server(1, 0), Server(1, 1)]

```

Then you can just call `sort(servers)`, which will sort your array accordingly. If that’s important, you can also add a field `id` to the struct, or you can also use `sortperm(servers)` to get the sorted indices. Hope this helps!

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [May 13, 2019, 8:31pm UTC](https://discourse.julialang.org/t/sorting-nested-dictionary/24182/4 "2019-05-13T20:31:03Z")

</div>

If I remember right Dicts in Julia are not sorted as they are implemented as hash tables. The [DataStructures](https://github.com/JuliaCollections/DataStructures.jl) package has a [SortedDict](http://juliacollections.github.io/DataStructures.jl/latest/sorted_containers.html) type that might be what you want. You would yet need to implement a struct or isless method for your specific ordering, however.

---

<div class="post-metadata">

**Author:** ![FinlayDaG33k](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/finlaydag33k/32/8440_2.png) [@FinlayDaG33k](https://discourse.julialang.org/u/FinlayDaG33k)\
**Post date:** [May 13, 2019, 8:31pm UTC](https://discourse.julialang.org/t/sorting-nested-dictionary/24182/5 "2019-05-13T20:31:52Z")

</div>

> [@simeonschaub](#):
>
> if you could tell us a bit more about what exactly your application is

While I’d love to, I unfortunately can’t really explain it…  
Not due to secrecy but because I don’t know how to explain it yet 😛  
It’s mainly a concept for a blockchain-based decentralized DNS system.  
Not really something most of you might use Julia for but considering I want to learn Julia and this might be a nice thing to do (I already made some crypto related scripts) as I can get some practical experience.

The reason why I added these indexes (though they where not made to be strings on purpose, they can be Integers too) is to is because later I want to use them to refer back to the server by adding some data to a “block” saying which specific “server” has added this block to the “chain”.

```jl
blocks = Dict(
    "1" => Dict(
        "server" => 1, # This will refer back to the "servers"
        "parent" => "GENESIS",
        "cmds" => [
            "ADD www.bob.hype ADDR 1.1.1.1",
            "ADD www.alice.hype ADDR 2.1.1.1"
        ]
    )
);

```

So currently, the solution you gave me doesn’t work out as it doesn’t take the structure of the data into account the way I want it to be :\ (obviously, I do appreciate the help)

---

<div class="post-metadata">

**Author:** ![simeonschaub](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/simeonschaub/32/216566_2.png) [@simeonschaub](https://discourse.julialang.org/u/simeonschaub)\
**Post date:** [May 13, 2019, 8:57pm UTC](https://discourse.julialang.org/t/sorting-nested-dictionary/24182/6 "2019-05-13T20:57:35Z")

</div>

It seems like this should do what you want:

```julia
struct Server
    id::Int
    votes::Int
    age::Int
end

isless_by_key(a, b, ::Tuple{}) = false

function isless_by_key(a, b, keys)
    if getproperty(a, first(keys)) == getproperty(b, first(keys))
        return isless_by_key(a, b, Base.tail(keys))
    else
        return getproperty(a, first(keys)) < getproperty(b, first(keys))
    end
end

function Base.isless(a::Server, b::Server)
    return isless_by_key(a, b, (:votes, :age, :id))
end

get_server_by_id(servers, id) = findfirst(x -> x.id == id, servers)

servers = [Server(1, 0, 1), Server(2, 0, 0), Server(3, 1, 0), Server(4, 1, 1)]

```

You can sort everything like before and it will now also look at the ids. You can also get a specific server by id by calling `get_server_by_id(servers, id)`. For more information, you can check out some more of Julia’s great documentation, it’s definitely worth a look.

---

<div class="post-metadata">

**Author:** ![FinlayDaG33k](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/finlaydag33k/32/8440_2.png) [@FinlayDaG33k](https://discourse.julialang.org/u/FinlayDaG33k)\
**Post date:** [May 14, 2019, 6:34am UTC](https://discourse.julialang.org/t/sorting-nested-dictionary/24182/7 "2019-05-14T06:34:55Z")

</div>

Is there a specific reason why I should not use a dictionary?  
Because I’ve chosen a dictionary because it can hold more arbitrary data if I need to add more later down the road (eg. maybe I need to add “public keys” later down the road, and I wanted to keep that possibility open).

---

<div class="post-metadata">

**Author:** ![GunnarFarneback](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gunnarfarneback/32/1827_2.png) [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)\
**Post date:** [May 14, 2019, 7:04am UTC](https://discourse.julialang.org/t/sorting-nested-dictionary/24182/8 "2019-05-14T07:04:20Z")

</div>

There are definite advantages to using a `struct` but if you want to stay with dictionaries and are not too concerned about performance or having the code look nice, you can do something like

```julia
julia> using OrderedCollections

julia> servers = OrderedDict(
           "1" => Dict(
               "votes" => 0,
               "age" => 1
           ),
           "2" => Dict(
               "votes" => 0,
               "age" => 0
           ), 
           "3" => Dict(
               "votes" => 1,
               "age" => 0
           ),
           "4" => Dict(
               "votes" => 0,
               "age" => 1
           ),
           "5" => Dict(
               "votes" => 1,
               "age" => 1
           )
       )
OrderedDict{String,Dict{String,Int64}} with 5 entries:
  "1" => Dict("votes"=>0,"age"=>1)
  "2" => Dict("votes"=>0,"age"=>0)
  "3" => Dict("votes"=>1,"age"=>0)
  "4" => Dict("votes"=>0,"age"=>1)
  "5" => Dict("votes"=>1,"age"=>1)

julia> sort!(servers, by = key -> (-servers[key]["votes"], -servers[key]["age"], key))
OrderedDict{String,Dict{String,Int64}} with 5 entries:
  "5" => Dict("votes"=>1,"age"=>1)
  "3" => Dict("votes"=>1,"age"=>0)
  "1" => Dict("votes"=>0,"age"=>1)
  "4" => Dict("votes"=>0,"age"=>1)
  "2" => Dict("votes"=>0,"age"=>0)

```

---

<div class="post-metadata">

**Author:** ![c42f](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/c42f/32/52842_2.png) [@c42f](https://discourse.julialang.org/u/c42f)\
**Post date:** [May 14, 2019, 7:41am UTC](https://discourse.julialang.org/t/sorting-nested-dictionary/24182/9 "2019-05-14T07:41:04Z")

</div>

A custom `struct` has the advantage that you can give custom behavior to that type by adding method overloads. For example, if you wanted to print your `Server` objects in a particular way so that they’re easy to work with, you can override `Base.show(::IO, ::Server)` and your `Server`s will always be printed that way in the REPL. You can’t do this in a useful way for a generic type like `Dict`.

Also…

- A struct with known fields is far more efficient than a Dict
- It has nicer syntax: `server.id` rather than `server["id"]`
- The data model of your program is clear by inspection of the definition of `Server`, rather than by having to look at every place that a server is used; a new field may be added at any time to a `Dict`.

Those are just a few reasons, I’m sure there’s more.

---

<div class="post-metadata">

**Author:** ![FinlayDaG33k](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/finlaydag33k/32/8440_2.png) [@FinlayDaG33k](https://discourse.julialang.org/u/FinlayDaG33k)\
**Post date:** [May 14, 2019, 10:57am UTC](https://discourse.julialang.org/t/sorting-nested-dictionary/24182/10 "2019-05-14T10:57:29Z")

</div>

> [@GunnarFarneback](#):
>
> you can do something like

This seems to do exactly what I want, thanks!

> [@c42f](#):
>
> A struct with known fields is far more efficient than a Dict

This is because Julia can compile the struct more efficient since it doesn’t have to take “generic” types in considerations right?

I understand that going with a struct might be more desirable when performance counts but considering this is more of a demo thing rather than an actual “useful” thing, I’m not as concerned with performance.  
I’ve got it to work using @GunnarFarneback’s comment, thanks for the help!

---

<div class="post-metadata">

**Author:** ![c42f](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/c42f/32/52842_2.png) [@c42f](https://discourse.julialang.org/u/c42f)\
**Post date:** [May 14, 2019, 11:42pm UTC](https://discourse.julialang.org/t/sorting-nested-dictionary/24182/11 "2019-05-14T23:42:51Z")

</div>

> [@FinlayDaG33k](#):
>
> This is because Julia can compile the struct more efficient since it doesn’t have to take “generic” types in considerations right

Not exactly, you can have a struct with flexible field types:

```julia
struct Server
    id
    votes
    age
end

```

is equivalent to declaring all the fields here as `Any` in which case you could initialize `Server("hello", 10, 10.3)`, and `Server("Surprise", [3,2,1], ["What"])`. Declaring specific types for the fields does make things much more efficient. But `struct` is useful for structuring your code regardless of that.

---

<div class="post-metadata">

**Author:** ![FinlayDaG33k](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/finlaydag33k/32/8440_2.png) [@FinlayDaG33k](https://discourse.julialang.org/u/FinlayDaG33k)\
**Post date:** [May 15, 2019, 8:08am UTC](https://discourse.julialang.org/t/sorting-nested-dictionary/24182/12 "2019-05-15T08:08:55Z")

</div>

I see, thanks for the explanation 🙂