[FIX][BUG] Set>>atRandom: is not random
Daniel Vainsencher
danielv at netvision.net.il
Sun Jun 29 00:04:49 UTC 2003
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/
More information about the Squeak-dev
mailing list
|