Augmented libweighted tree that can only minimal fairshare value changes

[dongahn]

To further our ideas for minimum fairshare value update optimization: flux-framework/flux-core#3311 (comment)

[dongahn]

A could of things from our slack:

@SteVwonder:

@dahn and @milroy: I went down a rabbit hole after the coffee time. Looks like there is a way to find the minimum number of swaps required to sort an array. https://stackoverflow.com/questions/2987605/minimum-number-of-swaps-needed-to-change-array-1-to-array-2
It involves calculating/leveraging the permutation cycle: https://mathworld.wolfram.com/PermutationCycle.html
I haven't fully grok'd it, but its something to maybe come back to later on down the road.

Cool thing is that the calculation is O(n*logn)

[dongahn]

Interesting. We should probably think through... whether this will allow us to keep the intitial faireshare values as much as possible.

[dongahn]

When I thought about this a bit after the coffee hour, one potential solution could be perhaps to use "longest increasing sequence". https://en.wikipedia.org/wiki/Longest_increasing_subsequence.
You sort the users based on the new shares/usages. But then, you identify the longest increasing sequence based on the previous fairshare values from the newly sorted vector and then reuse these old fairshare values.
For only those who are not in the LIS set are assigned to new fshare values in a way still to hold proper ordering with these reused fairshare values.
The LIS algorithm could be expensive and the complexity would also be high so I'm not sure if this is worthy it.