Add reusable counterpart of WeightedIndex

[maratik123]

Background

What is your motivation?
There is not any effective WeightedIndex implementation, that does not require new allocation on heap to replace all weighted index values. WeightedIndex::update_weights is only effective on updating small amount of weights.

What type of application is this?
Tasks such as Travelling salesman problem for their heuristic and approximation solutions (for example, via Ant colony optimization) require single sampling on each of multiple instances of WeightedIndex with different weights.

Feature request

In commited pull request #1460 I'm trying to add ReusableWeightedIndex with reusable storage to prevent unnecessary allocations

[dhardy]

Is there a reason this can't be a new method like WeightedIndex::replace_weights instead of a whole new distribution type?

The main limitations of adding this functionality to WeightedIndex that I can see:

• Construction with extra capacity must yield a valid distribution object (but it should be possible to do this in WeightedIndex)
• If, during fill, there is an error, then the result may be left in an invalid state. We would need to handle this somehow.

The biggest limitation of your current approach that I see:

• fill returns a temporary object referring to another object; this will be difficult to store in a struct (requiring ouroboros or similar)

[maratik123]

Is there a reason this can't be a new method like WeightedIndex::replace_weights instead of a whole new distribution type?

The main limitations of adding this functionality to WeightedIndex that I can see:

• If, during fill, there is an error, then the result may be left in an invalid state. We would need to handle this somehow.

Yes, this is the main blocker, why I decided to make new implementation. I can not see how to make replace_weights as cheap as possible with such restriction.

The biggest limitation of your current approach that I see:

• fill returns a temporary object referring to another object; this will be difficult to store in a struct (requiring ouroboros or similar)

I don't wait that this one-time object will require to store in other structs, because it's main target to create weighting fast, make one sampling and drop. If it is required to store object in other struct, then one can use WeightedIndex instead.

[dhardy]

Understood, however I have concerns:

• This is model fairly specialised for your application
• Having three variants of weighted-index samplers feels excessive — an indicator that we might want to rethink the API.

[vks]

Couldn't we just implement WeightedIndex::replace_weights(self, weights: I) -> Result<WeightedIndex> or similar?