❌ Linting issues

This PR is introducing linting issues. Here's a summary of the issues. Note that you can avoid having linting issues by enabling pre-commit hooks. Instructions to enable them can be found here.

You can see the details of the linting issues under the lint job here

cython-lint

cython-lint detected issues. Please fix them locally and push the changes. Here you can see the detected issues. Note that the installed cython-lint version is cython-lint=0.18.0.

/home/runner/work/scikit-learn/scikit-learn/sklearn/cluster/_hdbscan/_tree.pyx:786:19: unnecessary set + generator (just use a set comprehension)

_{Generated for commit: d59abf5. Link to the linter CI: here}

Even in draft mode, could you fill in a few details in the top comment already? In particular referencing the relevant other PRs/issues. I think it helps keep track of things. No full explanation, proof, etc needed.

@cakedev0 if you want to run the tests on CUDA interactively, you can use https://gist.github.com/EdAbati/ff3bdc06bafeb92452b3740686cc8d7c

Benchmarks

For one quantile, it's ~3x faster than the unstable-sort version of the current code.

It would be great to do benchmarks for 1, 5, 10 quantiles for int(1e5), int(1e6), int(1e7) data points with uniform and heavy tailed data and weights, both on numpy CPU and torch CUDA.

I made some benchmarks with varying shapes (n, d) for the input array and with nq quantiles (1, 3, 9).

For d=1 and nq=1, the gain is clear for numpy (3x) and the loss is very limited for torch.
For nq > 1, the gain is clear in most cases, but significant gains could also be reached by just looping over quantiles inside the function (once the sort is done), and not outside.
For d > 1, and esp. d >> 1 (like 100), it's not great. I think it's because of the the over-head of looping over the dimensions, and making a lot of calls xp.some_func(...).

Conclusion: maybe let's just go with the simple loop over quantiles inside the current implementation? This would be a clear and easy gain for some of the current use-cases in sklearn.

The algorithm I propose here might have its place to be implemented in Cython/C/C++ somewhere in numpy and/or scipy. Such an implementation would make the gain significant for any d and nq= 1 (or nq=2, 3 too). nq=1 being a common use-case, that might be interesting.
I'm not familiar with those ecosystems so any advice/insight will be appreciated!

Note: I found a way to mitigate the perf loss with d>>1 (I just pushed it), I'll give proper detailed benchmark results if you think it's still worth pursuing.

I give up for now on the O(n) algorithm, so I'm closing this PR.

Conclusion: maybe let's just go with the simple loop over quantiles inside the current implementation? This would be a clear and easy gain for some of the current use-cases in sklearn.

I agree, this is a good first step with a net improvement. Once merged we, can always reexplore later to compare this new stronger baseline. But maybe it's not worth investing too much effort if this function is not reported as the computational bottleneck of any user actual workload.