Sorting nested dictionary

Hii there,

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

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

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!

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. This would also mean you could implement your own rules for ordering for this specific type.

Is something like this what you had in mind?

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!

If I remember right Dicts in Julia are not sorted as they are implemented as hash tables. The DataStructures package has a SortedDict type that might be what you want. You would yet need to implement a struct or isless method for your specific ordering, however.

1 Like

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 :stuck_out_tongue:
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”.

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)

It seems like this should do what you want:

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.

1 Like

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).

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> 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)
3 Likes

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 Servers 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.

1 Like

This seems to do exactly what I want, thanks!

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!

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

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.

1 Like

I see, thanks for the explanation :slight_smile: