alg:ChooseX consider changing handling of 0 weight entries
Closed this issue · 4 comments
Oak should consider either creating a new set of functions for either choosing or stwheap itself to deal with 0 weights.
Problem: When attempting to perform UniqueChooseX from a weighted list and any entry is 0 weight it should never be selected. Today when converting from base weights to cumulative weights we end up with the state where the 0 value entry will be selected whenever the entry after it would be selected. This is annoying when tuning games if you do not want to remove 0 entries.
Decision point 1: Is this a bug and therefore ok to change without a major version change? Or do we need a new set or subset of methods.
Current thought is to have stwheap ignore/immediately pop 0 valuers and or in cumulative values function.
This may also be good time to revist the alg choosing and get better verifications and testing.
I think we can call it a bug if an element with input weight 0 is ever chosen-- we can write some simple tests and add some kind of filtering logic.
I can't replicate this based on the description; @Implausiblyfun Mind writing a failing test?
I wrote this, which passed
func TestUniqueChooseXZeroWeight(t *testing.T) {
t.Parallel()
rand.Seed(int64(time.Now().UTC().Nanosecond()))
for i := 0; i < testCt; i++ { // testCt is one million
weights, goodIndex := randomZeroWeightSlice()
chosen := UniqueChooseX(weights, 1)
if chosen[0] != goodIndex {
t.Fatalf("choose x chose an element with 0 weight")
}
}
}
func randomZeroWeightSlice() ([]float64, int) {
ct := rand.Intn(20) + 1
values := make([]float64, ct)
realVal := rand.Float64()
realValIndex := rand.Intn(ct)
values[realValIndex] = realVal
return values, realValIndex
}
Looking again, I think the bug was the calling code using UniqueChooseX
with CumulativeWeights
when that function is designed for WeightedChooseOne
.
Sorry about that should have followed up earlier. I had encountered this on Dashking and I think I mis-described the issue.
See the linked PR for what I think I was encountering in that instance.
I do want to take a bit more time to check this out and verify its the only oddity but I do think that the main issue that I was encountering where I was getting unexpected entries with 0 weights being selected.