Sorting Dictionary in Julia

user_13545283 0
Viewed 169

I have a dictionary in Julia that I want to sort by values. I found a couple of ways to do it. For instance

dict = Dict(i => sqrt(i*rand()) for i = 1:20)
dict= sort(dict;byvalue = true) # method 1
dict = OrderedDict(i => sqrt(i*rand()) for i = 1:20) #method 2 using ordereddict package [https://github.com/JuliaCollections/DataStructures.j][1]
# I don't want to use collect() method as I do not want the tuples of dictionary.

However, sometimes these two methods do lose their orders down the line when they are passed from functions to functions. Are there any other methods where the ordered dictionary is immutable in Julia?

julia dictionary sorting
2 Answers

As by the docs, for OrderedDict

order refers to insertion order.

I don't know how this can "lose its order down the line", but maybe you are just mutating stuff?

Probably what you want is closer to a SortedDict; however, this sorts by keys, not values. A dictionary sorted by values is a bit of an unusual application.

If you want a mutable data structure with fast lookup by key and iteration sorted by value, you could emulate this by a two-level approach: a normal dict for storing a mapping between original keys and tokens, and a second SortedMultiDict{ValueType, Nothing} to emulate a sorted multiset into which the tokens index. Then you define your own mechanism for indirect lookup through tokens somehow like this:

function insert!(d::ValueSortedDict, k, v) 
    _, token = insert!(d.values, v, nothing)
    d.keys[k] = token
end

getindex(d::ValueSortedDict, k) = deref_key((d.values, d.keys[k]))

And accordingly for other get/set style functions. (I didn't test this, it's just read off the docs.)

OTOH, if you never intend to mutate things, you can just do a very similar thing where you store a Dict{KeyType, Int} and a Vector{ValueType} together and sort! the vector once at the beginning. (Dictionaries.jl, described in @mcabbot's answer, is basically implementing this.)

user_13462760

You might be interested in Dictionaries.jl:

julia> dict = Dict(i => (i/10 + rand(1:99)) for i = 1:7)
Dict{Int64, Float64} with 7 entries:
  5 => 16.5
  4 => 23.4
  6 => 98.6
  7 => 56.7
  2 => 7.2
  3 => 58.3
  1 => 85.1

julia> using Dictionaries

julia> sort(Dictionary(dict))
7-element Dictionary{Int64, Float64}
 2 │ 7.2
 5 │ 16.5
 4 │ 23.4
 7 │ 56.7
 3 │ 58.3
 1 │ 85.1
 6 │ 98.6

julia> map(sqrt, ans)
7-element Dictionary{Int64, Float64}
 2 │ 2.6832815729997477
 5 │ 4.06201920231798
 4 │ 4.8373546489791295
 7 │ 7.52994023880668
 3 │ 7.635443667528429
 1 │ 9.22496612459905
 6 │ 9.929753269845127
user_137067350
Related