Hi,
I am trying to define a dictionary structure where I use a 2 element tuple as a key.
A = Dict{Tuple{Int64, Int64}, Float64}();
A[(1,2)] = 7.0
The catch is, I don’t care for the order of the tuple.
Therefore,
A[(1,2)]
A[(2,1)]
should provide the value 7.0.
Does anyone know the data structure I should use for the key and how to implement it?
Any help would be appreciated.
Perhaps use a Set as the key?
julia> d = Dict([Set((1,2)) => 1])
Dict{Set{Int64},Int64} with 1 entry:
Set([2, 1]) => 1
julia> d
Dict{Set{Int64},Int64} with 1 entry:
Set([2, 1]) => 1
julia> d[Set((2,1))]
1
Or does the key have to be a Tuple for some reason?
If you are specifically using 2-element tuples of integers, a high-performance solution is to use the minmax function as follows:
julia> A = Dict{Tuple{Int, Int}, Float64}();
julia> A[1,2] = 7.0;
julia> A[minmax(1,2)...], A[minmax(2,1)...]
(7.0, 7.0)
If you’d like to extend to longer tuples and/or unordered elements, I don’t know an allocation-free option. Sets are a good suggestion by @hendri54 .
Thank you for the help!
Just to expand on your question which I should have raised initially.
It would be nice to keep it a Tuple.
As in, the order I insert the values is the main order but if I enter the reverse order, it will still return the dictionary value.
If I run the following code
C = Dict{Set{Int64}, Float64}();
C[Set([1,2])] = 1;
C[Set([1,3])] = 5;
collect(keys(C))
The keys are in reverse order.
I would like them to have the order I entered them in.
Again, thank you for your help.
Then it would seem that the minmax solution solves your problem (as long as you are OK with keys always being sorted in the Dict). Or is there anything the minmax solution does not satisfy?
If keys are not always sorted, it would make sense to define a struct that wraps the Dict with functions that add and retrieve values. Then one would have to think about what do to when a user tries to add the key (2,1) when (1,2) already exists.
Your requirements are ambiguous, this is one of the problem. For example, if you create following records
dict[(1, 2)] = 1.0
dict[(2, 1)] = 2.0
what should return collect(keys(dict))? It can be [(1, 2)], [(2, 1)] or [(1, 2), (2, 1)] depending on the requirements of your original problem. So, there will be no single solution, and therefore one of the way to proceed is to roll out your own implementation.
There are multiply way to do it, but you should be careful, since Dict has lots of methods and they should be carefully implemented with regards to the problem setup. One way to speed it up is by using Lazy.jl
using Lazy
struct TupleDict{K, V} <: AbstractDict{K, V}
d::Dict{K, V}
end
TupleDict{K, V}() where K where V = TupleDict{K, V}(Dict{K, V}())
TupleDict(kv...) = TupleDict(Dict(kv...)) # careful though, it is not checking for duplicated entries
@forward TupleDict.d Base.iterate, Base.isempty, Base.length, Base.keys, Base.empty!, Base.sizehint!
Base.:haskey(d::TupleDict, k) = haskey(d.d, k) | haskey(d.d, reverse(k))
function Base.:setindex!(d::TupleDict, v, k)
if haskey(d.d, reverse(k))
d.d[reverse(k)] = v
else
d.d[k] = v
end
end
function Base.:getindex(d::TupleDict, k)
haskey(d.d, k) && return d.d[k]
haskey(d.d, reverse(k)) && return d.d[reverse(k)]
throw(KeyError(k))
end
This prototype should be close to what you want
dd = TupleDict{Tuple{Int, Int}, Float64}()
dd[(2, 3)] = 5.0
dd[(3, 2)] # 5.0
dd[(2, 4)] = 1.0
dd[(4, 2)] = 2.0
dd[(2, 4)] # 2.0
collect(keys(dd))
# 2-element Array{Tuple{Int64,Int64},1}:
# (2, 3)
# (2, 4)
If you want other behavior of the keys you should define setindex! appropriately.
Sorry for the slow reply.
This answer seems very cool. I will try to play with your answer over the weekend!
Thank you so much again for your help.
Also, I agree with you. What I asked was very ambiguous. Need to practice asking better questions here…
Also, minmax solved my particular issue in this case.
Therefore I think I will mark it as the solution.
Once again, Thank you!