What an annoying problem - choose between "not-guaranteed-terminating,
quick on average" to "asymptotically inefficient" solution. OTOH, it
seems to me the bug itself would be unimportant on non-tiny sets. Maybe
we should do B if the set is small, and the current implementation
otherwise?

I'm not sure what the limit number should be, not even sure how
inefficient B is for what size sets...

Daniel

Torge Husfeldt <torge.husfeldt at gmx.de> wrote:
> Hi Samir,
> On Thu, 26 Jun 2003 20:05:39 +0200, Samir Saidani <saidani at info.unicaen.fr> 
> wrote:
> 
> > Here is a little piece of code to reproduce the bug:
> >
> > |s a|
> > s_ Set new add: 'a'; add: 'b'; yourself.
> > a_Random new.
> > i_0.
> > 500 timesRepeat: [ ((s atRandom: a)='a') ifTrue:[ i_i+1 ]. ].
> > Transcript show: i; cr.
> 
> I have tow choices of a rewrite for Set>>atRandom:
> 
> (i) maybe abuses the Generator (asks for more than one random number)
> and is unneccessarily recursive (i will smooth it out if you prefer this 
> fix)
> atRandom: aGenerator
> 	"Answer a random element of the receiver.  Uses aGenerator which
> 	should be kept by the user in a variable and used every time. Use
> 	this instead of #atRandom for better uniformity of random numbers 	because 
> only you use the generator.  Causes an error if self has no 	elements."
> 	| answer |
> 	self emptyCheck.
> 	^(answer _ array at: (aGenerator nextInt: array size))
> 		ifNil:[self atRandom: aGenerator]
> 		ifNotNil:[answer]
> (ii)can be more time-comsuming because it always iterates the whole set.
> Especially in kryprographics this may be highly undesirable because
> it makes it easy (given the knowledge of the implementation) to guess
> the range of the random number from the time it took to produce it.
> atRandom: aGenerator
> 	"Answer a random element of the receiver.  Uses aGenerator which
> 	should be kept by the user in a variable and used every time. Use
> 	this instead of #atRandom for better uniformity of random numbers 	because 
> only you use the generator.  Causes an error if self has no 	elements."
> 	| rand |
> 	self emptyCheck.
> 	rand _ aGenerator nextInt: self size.
> 	self doWithIndex:[:each :ind |
> 		ind == rand ifTrue:[^each]]
> 	^ self errorEmptyCollection
> 
> HTH,
> Torge
> 
> >
> > Results (~100) show that you have 1/5 to have the first element.
> >
> > A workaround is to change a set as an array (probability is 1/2).
> >
> > |s a|
> > s_ Set new add: 'a'; add: 'b'; yourself.
> > a_Random new.
> > i_0.
> > 500 timesRepeat: [ ((s asArray atRandom: a)='a') ifTrue:[ i_i+1 ]. ].
> > Transcript show: i; cr.
> >
> > Don't have time for the moment to fix it, but certainly due to the
> > "array" representation of a set (Set(1,2) appears as an array of size
> > 5 #(nil 1 2 nil nil nil).
> >
> 
> 
> 
> -- 
> Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/