Fix for Set atRandom: I'd make it a changeset but I don't know how to make a changeset with a single entry. I told it to save a ChangeSet and it saved out 26 megabytes.
Since Sets never shrink, it does make sense to have the relatively prime scanning for large capacity, nearly empty sets.
Note that there is a possible optimization for generating relatively prime numbers. If the Set is a power of two in length, then any odd number will do. Unfortunately Set's class method "sizeFor" makes it impossible to make a set a power of two in length.
So, this version checks, and does the optimization if it will do any good.
If you want that optimization of an optimazation to be enabled for new Sets then change sizeFor as well.
sizeFor: nElements "Large enough size to hold nElements with some slop (see fullCheck)" nElements <= 0 ifTrue: [^ 1]. ^ nElements*2
atRandom: aGenerator | ind entry i span foundrelativeprime | self emptyCheck. entry _ nil. i_1. "try 30 times with random samples" [ entry == nil and: [i<30] ] whileTrue: [ ind _ aGenerator nextInt: array size. entry _ array at: ind. i _ i+1 ]. entry == nil ifTrue: [ "failed 30 random samples - the array must be almost empty" "pick a random, relatively prime span and scan every entry"
"Special case for Sets that are powers of two in size. " "If you make a Set that's a power of two in size > 1 then it will" "always be a power of two in size"
(array size bitAnd: ((array size) - 1)) = 0 ifTrue: [ span _ (aGenerator nextInt: (((array size) + 1) // 2)) * 2 - 1. ] ifFalse: [ "not a power of two - find any number that's relatively prime" foundrelativeprime _ false. [ foundrelativeprime] whileFalse: [ span _ 1 + (aGenerator nextInt: ((array size)-1)). foundrelativeprime _ (1 = ((array size) gcd: span)). ]. ]. i _ array size. [i > 1] whileTrue: [ ind _ (ind+span-1) \ (array size) + 1. entry _ array at: ind. entry == nil ifFalse:[^entry]. i _ i-1. ]. self errorEmptyCollection. ]. ^entry.
On Mon, 29 Nov 2004 10:10:31 -0800, "Joshua Scholar" jscholar@access4less.net said:
Fix for Set atRandom: I'd make it a changeset but I don't know how to make a changeset with a single entry. I told it to save a ChangeSet and it saved out 26 megabytes.
Hm, haven't seen that one before. Are you sure your atRandom change isn't wreaking havoc? ;-)
But anyway, to save a changeset, just do this: http://minnow.cc.gatech.edu/squeak/785
You should be able to create a new changeset (in a changesorter window), make your change in a browser, then file out your changeset in the changesorter (which will include the single change).
Or, even simpler is to bring up the pop-up menu in the (upper-right) method list pane in a browser (with your atRandom: method selected) and choose "fileOut".
- Doug
squeak-dev@lists.squeakfoundation.org