Approximate set intersection for floating point numbers

General Usage
1

I have two sets of numbers, say…

x = randn(1_000_000) |> Set
y = randn(1_000_000) |> Set

I’d like to find the approximate intersection of the two sets, to some tolerance. I could…

for xi in x
    for yi in y
        if isapprox(xi, yi; atol = 1e-8)
            print("Intersection at ...")
        end
    end
end

But this is super slow, since it’s O(n^2). Integer Set intersection is super fast. Are there any packages that have implemented approximate set intersection for floating point types?

2

Sort them both first and work through them both in order.

2 Likes