Get an equal element of a set/get an equal key of a dictionary

General Usage
, , , ,
1

Suppose I have x and s::AbstractSet and I know x ∈ s. How to get the element of s, say e, such that x == e? I could iterate through all elements like this, but surely there should be a simpler and more efficient solution?

function get_equal_element(x, s)
    for e ∈ s
        if x == e
            return e
        end
    end
    throw(ArgumentError("x ∉ s"))
end

The same question could be asked about the keys of an AbstractDict dictionary. Or just about Set and Dict, at least.

2

The solution for Dict is getkey:

julia> getkey(Dict(7.0 => "seven"), 7, nothing)
7.0

The solution for Set should be simply get, however the relevant methods are missing. Not sure what to do with sets, though.

3

I’m confused - if x is in S, kind of by definition you already have e, since knowing x in S implies hash(x) == hash(e) (and by extension, barring hash collisions, isequal(x,e)). So at best the only thing left would be converting x to the element type of S, but then you’re looking for more than hash equality.

1 Like
4

I want the exact object that’s in the Set, though. That is, the return value of get_equal_element(x, s) must be identical (===) to the element of s that’s equal to x. I know that x == e, but conversion (oftype(e, x)) doesn’t cut it.

The specific use case is basically this: I have a certain data structure which has certain Vector objects at some places. Some of these Vectors are equal to some of the other ones, so my goal is to deduplicate them to maybe save memory and improve cache locality when using the data structure. This is my deduplication algorithm:

  • Step 1: push! each Vector value from the data structure into a newly-created Set, say s.
  • Step 2: for each Vector value, say x, in the data structure, replace it with get_equal_element(x, s).

I don’t really care about the performance of the deduplication itself, so I currently just use the implementation of get_equal_element as given above. If I cared about performance I would switch to using Dict{T, Nothing} directly instead of Set{T}, and then use getkey instead of get_equal_element.

5

You even know isequal(x, e).