# Choosing how to choose with self-normalising weights

This is a development topic.

There have been discussions about having a way of conveniently normalising weights for random choice. Since the first option modifies a common method, it is discussed here.

Here is an updated collection of options.

Normalising them in `wchoose` is not good, because it will do this normalisation for each new random value, which is a waste of energy (though see 2b below).

Note that I have allowed myself to add/remove as a way to reap the results of the discussion, if youād like a particular option to appear here, please let me know. I always leave the numbers to keep the reference for the discussion intact.

``````// 1.
choose(unnormalizedWeights) // uses weights if not nil, then normalises
wchoose(weights) // stays as now, you have to normalise yourself
``````
• pro: no extra method / the common method is extended / simple / other languages do this / low friction from choose
• con: breaks with existing logic / suggests an inefficient method as default / needs explanation
``````// 1b.
// both normalise if flag is true, defaults differ
choose(weights, normalize=true) // without weights
wchoose(weights, normalize=false)// normalises if flag is true, off by default (like the TWChoose ugen)

``````

pro: separates concerns / symmetric
con: suggests an inefficient method as default

``````// 2.
choose // without weights
wchoose(weights) // stays as now, you have to normalise yourself
wchooseN(normalizedWeights) // normalises
``````

pro: separates concerns / logical and idiomatic / most efficient
con: extra method / two modification steps away from choose (front and end, alternative name: wnchoose is better, but less discoverable)

``````// 2b
choose // without weights
wchoose(normalizedWeights) ) // normalises
wchooseN(weights) you have to normalise yourself
``````

this assumes that normalisation is very efficient and only matters for very large arrays
pro: separates concerns / logical and idiomatic
con: extra method / may make some existing code less efficient or break for ear tuned pieces

``````
// 3.
choose // without weights
wchoose(weights, normalize=false) // normalises if flag is true, off by default (like the TWChoose ugen)
``````

pro: separates concerns / logical and idiomatic
con: not easy to read in code

Imhoā¦

1 would be fine if you could guarantee itās a FloatArray.

2 would be more methods and since itās just a single extra method call, seems unnecessary.

3 and 2 might be considered more from the users perspectiv?. If youāre in an ide and either 3 or 2 popup in suggestions itās quite obvious what you should do with themā¦ But if the argument for `wchoose` was named ānormalisedWeightsā I think youād get a similar experience, and less noise. You could use the ide/lsp to guide the correct usage, because the problem isnāt that itās hard to do, itās just hard to remember to do.

Iām also not a fan of having arguments as options where you only fill the argument you want. I donāt know of any other language that does this and I stumble every time I come across it.

A normal Array should be also fine, could be e.g. `[1, 2, 3]`. I think that it is fine to accept anything that responds to `normalizeSum` with something that responds to `windex`.

Over time, I have come to prefer adding new methods instead of more arguments. It is what functional languages do. The main thing is to get the names right ā e.g. in this case it could also be `wnchoose` or `whchoosen`. Easy to write and clear to understand. version 1 is a little confusing, because you may first wonder why you have a `wchoose` if you already have weights in `choose`. Then only through documentation you get the difference. With 3 methods, the logic is relatively clear, and the autocompletion response is also logical (if you know about wchoose already, the new option is almost self-explanatory).

It is a very good way to allow incremental specifications (and not unusual, e.g. python and ruby both have default arguments, lisp has optional arguments). But yes - they should not be used to switch between kinds of functionality too much ā I think it is nicer and even more concise to just use a different method name then.

In the end, it is about how expressive the code is that is actually written when using it.

I think the PR interface could be improved. Currently the PR implements

• If I just want to get a random element, I can use the `choose` method.
• If I want to use a custom distribution, I can use `wchoose`, short for weighted(?) choose. If the distribution passed is not a distribution (all elements >=0, sum equal to 1.0), the function will implicitly proceed with non-deterministic behavior.
• If I have an array of values that may not be a probability distribution, but can be transformed into such a distribution, I have to use `choose`, but now with arguments.

So based on what kind of ādistributionā I have, I need to choose between two functions and their arguments properly - seems like something I already have to look up.

Lets take a look at the equivalent Python interface `random.choices`, which was already mentioned

``````def random.choices(population, weights=None, *, cum_weights=None, k=1)
``````

You have a unified function where given weights are normalized. Instead of providing different functions with names you need to know, we can use arguments that can be displayed from within the IDE and make you memorize less, which I think is more user friendly, especially for beginners.

So, why not try to be a bit more radical here with the PR?

• make choose accept arguments
``````SequencableCollection.choose { |weights: nil, normalize: true|
if(weights.isNil, { ^this.at(this.size.rand) });
if(normalizeWeights, { weights = weights.normalizeSum });
^this.at(weights.windex);
}
``````
Normalize is true b/c only in the edge case of large arrays that are already scaled does it make sense to turn off this flag - this is advanced usage for users who know what they are doing in regards of performance.
• deprecate `wchoose` which will simply forward the call to `.choose(weights, normalize: false)` - normalize false in order to mimic the old behavior.

IMO this makes the code much more readable and one does not need to know the differences between `choose`/`wchoose`/`wchooseN`

``````(0..10).choose;

// looks "wrong", but IDE displays normalize: true as default argument
(0..10).choose(weights: (0..10));

// this looks strange in written code - could be a bug?
(0..10).choose(weights: (0..10), normalize: false);

// "advanced" usage - we are sure that the weights are a distribution
(0..10).choose(weights: (0..10)/(0..10).sum, normalize: false);
``````

All in all a good suggestion, even if I prefer to have more methods than more arguments. This is a little bit a cultural difference between python and haskell.

Please letās not do this, but in any case keep `wchoose` as it was. As I said in many use cases, it is a waste of energy to add and divide each time you need a random value. Deprecation is just not worth it.

Is there a problem with deprecating `wchoose` if the behavior is still available?

now:
`[1, 2, 3].wchoose([2, 2, 6].normalizeSum)`
using @dscheibaās suggestion becomes
`[1, 2, 3].choose([2, 2, 6])` //16 character benefit
and
`[1, 2, 3].wchoose([0.4, 0.4, 0.6])`
becomes
`[1, 2, 3].choose([0.4, 0.4, 0.6], false)` //5 character cost

I do think it would be nice to have a single method for choosing rather than 2 (as now) or 3!

FWIW the PR author had another solution: `choose(weights: nil, normalizedWeights: nil)`

My preferred solution would be changing the argument name of the existing methods to`normalisedWeights`. It should show up in the ide and be enough of a reminder to call `normalise`.

You know whatā¦ I have no idea what expressivity is in this context?!

quick Q:

`prArrayWindex` is already summing the weights if Iām reading it right? (Iām not exactly literate in C++ butā¦)

couldnāt prArrayWindex normalize the weights if their sum != 1 - so no performance hit with normalized weights, in which case we would just have:

`choose( weights = nil )` and be done?

well, I would say it is a matter of

• how well it is readable
• how much you have to change something to become something different
• how interesting it is when you learn it
• how beautiful code looks like

All of these criteria are idiomatic, so we are talking about aesthetics, with some objective and some subjective criteria.

deprecating means eventually removing. So yes, it generates a lot of work for many people. It also disintegrates the code base between old and new.

Yes, it is, but if you do normalizeSum first each time, you have to do it twice and divide once, for each random value. That is, you have at best a performance halving.

yes but if we change `prArrayWindex` to normalize when the sum !=1 then there is no performance hit when normalized weights are provided!

`wchoose([0.5, 0.5])` would still perform as `choose([0.5, 0.5])` - only `choose([1, 1]) would introduce the division. (no need to do the sum twice as we already have the value). or have I misunderstood?

Yes, right, we can save the division. But how do we find out if the sum ā  1 ? We have to add up a second time anyway. Or did you have another idea?

And: is there a threshold? With floating point numbers, it may be a decision to say if 0.9999 is ok.

ahh looking further at `prArrayWIndex` I see that I hadnāt quite understood.

the āsumā is just partial sums as part of the weighted selection algorithmā¦

so we are doing an average of n/2 additions and comparisons per call. if we sum first - check != 1 we are adding n additions and one comparison so yes this would be a little slower!

to normalize we would multiply the random number before finding the index as thatās faster than division. There might be a faster algorithm out there - build the integral of the weights, scale the rand, then do a binary search perhaps.

Iām in favor of #3

Pros

• separates concerns / logical and idiomatic (already mentioned)
• no new method
• the flag is a natural extension to current functionality (bonus in the new SC release!)

con: not easy to read in code

I donāt see this as a con, if `flag` is instead called `normalize`. Then it actually just becomes expressive (if you choose to simply tab-complete in the IDE to include the key)

The question is then how to handle the `normalize` arg.

Iād prefer this to be `true`āarguably the current behavior āfeels brokenā (hence the PR). So a default of `true` says ācall `normalizeSum` for me, Iāll take the performance hitā. For someone concerned with performance, theyāll go out of their way to set `false`.

But, thatās not backwards compatible, so it āhas to beā `false` (breaking change, anyone?).

This leaves the ābrokenā behavior by default . But, the flag is there to make the user consider why one might want to normalize, and either use the flag, or supply a pre-normalized distribution.

This sounds more complicated than it is, itās easily clarified in the docs. (BTW, why isnāt there already an example showing the use of `.normalizeSum`??)

My runner up choice is #2

`wchooseN(normalizedWeights) // normalises`

for the pros already mentioned, and it will show up in auto-complete if you know about `wchoose`, and docs will clarify the differences if itās not obvious.
Note though the arg would be just `weights`, (`normalizedWeights` implies theyāre pre-normalized).

`wchoose(weights, normalizedWeights) `

A couple more thoughts:

I didnāt do a dive into `prArrayWIndex`, but Iām rooting for @semiquaver to find an efficient solution That would be cool.

Andā¦ hereās an unconventional idea: what about a āsoftā deprecation? i.e. extend `choose` as @dscheiba suggested:

``````SequencableCollection.choose { |weights: nil, normalize: true|
``````

essentially superseding `wchoose` without deprecating it, and letās us default to `normalize: true` without breaking backward compatibility

because actually deprecating that method will surely eventually annoy users / break old code.

(Not convinced of this myself, just throwing it out thereā¦)

2 Likes

Hi! The PR author here.
As @semiquaver indicated here, I actually suggested extending `.choose` in the issue preceding the PR, inspired by the interface of `random.choices` in Python. That would make the code more readable; a view that @dscheiba expressed here. It would look something like this:

``````	choose { arg weights, norm_weights;
^case
{not(norm_weights.isNil)} {this.wchoose(norm_weights)}
{not(weights.isNil)} {this.wchoose(weights.normalizeSum)}
{this.at(this.size.rand)}
}
``````

I also think that a normalize flag with a default of `false` is not a good idea. Not normalizing is the advanced need of an user seeking better performance; normalizing is the arguably expected behavior of a weighted choosing function, and it is what the Python, Haskell, and Max/MSP bach library implementations do.

Hi, thanks for one more suggestion. Iāve integrated it to the list in the beginning of the page.
To me it is not clear that it is the best solution. It combines both advantages and disadvantages of other variants.

In particular, it needs to be explained and documented that it is wrong to write:

`[1, 2, 3].choose([10, 2, 1], [0.1, 0.5, 0.4])`

It is at least unusual that arguments canāt be combined, and more idiomatic to use separate methods for separate behaviours.

Just so I can understand better: can you explain a bit what is the disadvantage of just simply having a separate method?

One of the joys of SC is rapid iteration. I might think ālets choose between two synthsā:

``````[\harp, \dogBark].choose
``````

after listening I think: "Iād like to hear `\harp` twice as often!. Now I must do three things: change the method name to `wchoose` (which I have to remember) then add the argument `[2, 1]` and remember to call `normalizeSum` (or what I usually write is `[2, 1] / 3` ā and I am usually annoyed by this moment of friction)

if `choose` was capable, Iād much rather just insert an argument `[2, 1]` and be done! - having a flag that defaults to `true` for `normalize` would be best and quickest. Later, if I were seeking to improve performance I could always change `[2, 1]` to `[0.66, 0.34]` and the flag from `true` to `false`.

Reserving `wchoose` for the case where arguments have been normalized is suboptimal since the name `wchoose` does not suggest this distinction.

Iād mention that there are very very many methods for `Array` and I often forget exactly which is which - the IDE can show us the flag and optional method, but it canāt suggest an alternate method which we might not remember. So I favor @dscheibaās suggestion with @mikeās `soft deprecation`. This would leave `wchoose` available but steer users to the new idiom. I agree that the mutually exclusive arguments in @Asmatzaileās version is unidiomatic.

2 Likes

For those curious about the efficiency aspect:

``````(
var numIter = 50e3.asInteger;
var arrSize = 5e3.asInteger;
var array = arrSize.collect{ rrand(0, 1.0) };
var weights = arrSize.collect({ rrand(0, 1.0) });

"Non-normalized:\n\t".post;
bench {
numIter.do{
array.wchoose(weights)
}
};

"Normalized:\n\t".post;
bench {
numIter.do{
array.wchoose(weights.normalizeSum)
}
}; ""
)
``````

Once you hit an `arrSize` of ~1000, the hit is more than an order of magnitude, and really climbs for larger sizes. (perhaps a useful benchmark for future docs)

I tend to agree with @semiquaver 's framing here! (Pls. share piece with harp + dog on the forum)

1 Like

Well put
If the mutually exclusive arguments version is unidiomatic, I am also comfortable with that solution!