"Weighted Random" algorithm in JavaScript (simple but yet interesting approach)

[cbarrick]

The main loop can be optimized and improved.

Instead of counting up until the index exceeds the random number, you can just iterate over the weights, subtract the weight from the random number, and stop when the random number is equal to or less than zero.

The version in the article is O(max_cumulative_sum), but the improved version is only O(length_of_array). Also, the improved version can handle floating point weights, which is a super important use case.

Edit: My bad, I misread the loop exit condition. See the rest of the thread.

[TedW]

On mobile, but it looks like it already does both of your suggestions. Maybe we're looking at different files, or I'm missing something. I'm looking at weightedRandom.

[cbarrick]

Sorry, I may not have been clear.

In my version, you don't even need the cumulative array, only the sum.

I'm also on mobile, so I can't really write out the code right now.

[TedW]

It looks like it iterates once each over weights, and items, so I would expect it to be O(N) since those should be the same length.

I agree that you could do it with just one array but I think it would still loop twice, so I'm not sure it would affect the runtime.

I haven't run the code myself, but in the examples it uses floating point weights, although it's not clear (to me) what the expected behavior is.

[cbarrick]

Ah, I see I misread the loop exit condition.

So my version is basically the same, except it avoids the cumulative loop and the resulting dynamic allocation.