c++17 removed random_shuffle

[hoodmane]

std::random_shuffle is used here:
https://github.com/matplotlib/matplotlib/blob/main/src/tri/_tri.cpp#L1469

It has been removed from c++17:
https://en.cppreference.com/w/cpp/algorithm/random_shuffle

The reason for removing std::random_shuffle in C++17 is that the iterator-only version usually depends on std::rand, which is now also discussed for deprecation. (std::rand should be replaced with the classes of the header, as std::rand is considered harmful.) In addition, the iterator-only std::random_shuffle version usually depends on a global state. The std::shuffle's shuffle algorithm is the preferred replacement, as it uses a URBG as its 3rd parameter.

[tybeller]

Would anyone mind if I worked on this? This would be my first contribution. From what I'm seeing it looks like it only needs to be replaced with the shuffle function, is that correct?

[hoodmane]

@tybeller thank you I would certainly appreciate that. I think the issue is exactly as you say. One concern is I'm not sure what the policy is for supporting old versions of c++ is, so there is a chance you'd need a precompiler conditional to use random_shuffle for old c++ versions.

[tybeller]

Sounds good, right now im looking at using the standard shuffle using a mersenne twister engine to serve as the URBG with a random device generating the seed, I see before the RandomNumberGenerator class took a seed 1234 and I was wondering if I should use that instead or if I could possibly have RandimNumberGenerator output a URBG instead.

[hoodmane]

My guess is that it doesn't matter that much how you do it. I think the shuffle is just supposed to make sure that the edges aren't in some bad order that would make the next algorithm perform really poorly. But I don't understand the domain logic very well so we'd need to hear from the matplotlib maintainers.

[ianthomas23]

It is absolutely fine to replace random_shuffle with shuffle. The bespoke RandomNumberGenerator can be removed too.

The shuffling needs to be deterministic hence the seed. If you create two TrapezoidMapTriFinder objects for the same triangulation on the same system, the output needs to be the same. If we had infinite precision it wouldn't need to be deterministic as the generated trapezoid map would be the same regardless of the random shuffling (which just determines the order of insertion of triangle edges), but because of finite precision the result can be slightly different. For example, if a test point resides exactly on or very near an internal edge, the algorithm may return one side or the other depending on the order of testing.

That is probably too much information! So, summary of what this involves:

1. Replace random_shuffle with shuffle.
2. Remove RandomNumberGenerator class.
3. The random number generator that you choose to use must be seeded.
4. You don't need any C++ version checking as shuffle has been available since C++11.
5. It needs a release note saying that the output of TrapezoidMapTriFinder may be slightly different, as may triangulation interpolation and refinement which use this class.

I am not classifying this as an API change. But because it may change the rending of a pixel or two in a typical output it could be so classified. If so, it would also require an API change note.

[hoodmane]

Thanks tybeller and others!

…

On Fri, Oct 28, 2022, 07:04 Thomas A Caswell ***@***.***> wrote: Closed #24010 <#24010> as completed via #24062 <#24062> . — Reply to this email directly, view it on GitHub <#24010 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACCVWKS34CWDZHWX3BB6DO3WFPMPZANCNFSM6AAAAAAQVKDGOE> . You are receiving this because you authored the thread.Message ID: ***@***.***>