Random number with weighting

This code has been declared by its author to be Public Domain code.

Random number with weighting by Warpy

2008

Suppose you want to make a random choice between a given set of options, but you want to make some options more likely than others.

I've included two methods here - a 'lazy' one that is fast for small numbers of options (<10) and a binary search method that is fast for large numbers of options.

Function picksomething(probabilities#[])
   p#=rnd(0,1)
   t#=0
   i=0
   while t<=p
      t:+probabilities[i]
      i:+1
   wend
   return i - 1 
End Function


Function picksomethingbinary(probabilities#[],sumprobabilities#[])
	l=Len(probabilities)

	p#=Rnd(0,1)
	i=l/2
	move=i
	While 1
		move:/2
		If move=0 Then move=1
		s#=sumprobabilities[i]
		If s<p
			i:+move
		ElseIf s-probabilities[i]>p
			i:-move
		Else
			Return i
		EndIf
	Wend
	Return i - 1 
End Function


'EXAMPLE 

Local probabilities#[5]
probabilities=[.1,.1,.1,.2,.5]

Local sumprobabilities#[5]
t#=0
For i=0 To 4
	t:+probabilities[i]
	sumprobabilities[i]=t
Next

ms=MilliSecs()
For i=1 To 100000
	number=picksomethingbinary(probabilities,sumprobabilities)
Next
diff=MilliSecs()-ms
Print "binary search method took "+String(diff)+"ms"

ms=MilliSecs()
For i=1 To 100000
	number=picksomething(probabilities)
Next
diff=MilliSecs()-ms
Print "lazy method took "+String(diff)+"ms"

Comments

None.

Code Archives Forum