Performance issue with `datasets_sets_distances`

[awage]

The function match_attractor_ids! becomes very slow when there are many attractors.

It takes more time to match the attractors than computing the basin fractions. For example, for 1000 initial conditions:

basins fractions: 222.9 s match_attractors_ids! : 895.9 s

It depends on the number of attractors to match. I will try to provide a reproducible example

[Datseris]

Please provide more information. Provide a MWE, a Minimal Working Example, a piece of code that Runs, Is as small as possible, and highlights the problem.

[awage]

The problem is in the number of attractors and the number of datapoints per attractors:

using Attractors
using Attractors.DynamicalSystemsBase, Attractors.DelayEmbeddings
using Random

d1 = Dict()
d2 = Dict()
N = 500 
dim = 30
np = 100

for k = 1:N 
    push!(d1, k => Dataset(rand(dim,np)))
    push!(d2, k => Dataset(rand(dim,np)))
end

@time match_attractor_ids!(d1, d2)
@time d = datasets_sets_distances(d1, d2)

I don't know if it can be optimized.

[Datseris]

Well, 99.9999% of the time is spent in datasets_sets_distances so the performance issue is there. I'll have a look, I'm sure things can get better, I see a lot of allocations in the profiling.

[Datseris]

yeah I am sure I can improve this performance. I'll open a PR at DelayEmbeddings.jl as this is where this function lives in. match_attractors_id! is as fast as possible when one has already computed the distances.

[Datseris]

Alright, here is the status quo. I've extensively tested and benchmarked the dataset_distance function and the sets_datasets_distances one. The latter has optimal performance, and calls the first version. So the performance of dataset_distance is all that matters. In conclusion:

• I've improved the performance of Hausdorff and StrictlyMinimumDistance by about 10%.
• We can't get higher performance. We just have to accept the fact that computing these distances is super expensive, because it practically means that for every point in one dataset we need to find its nearest neighbor in the other dataset, and we in fact have to repeat this process for every dataset at hand. It is costly. If we have 100 datasets each with 100 points, this becomes like 100^4 calculations.

@awage we have to test how well the RecurrencesSeededContinuation works with the new method I implemented here, the Centroid one. I will do this as part of my TODOs once I update Attractors.jl to the StateSpaceSets.jl package.

[awage]

Fantastic job! I will test it as soon as possible. Great!!