On 2017-05-17, at 18:18, Robin Vowels wrote:
>
>>> This takes O(n) time, as opposed to O(n log n) for Peter's
>>> "generate and sort" method. With only 99,999 numbers the extra CPU time
>>> may not be significant, depending on how often you need to generate
>>> a sequence.
>> Presuming that the table fits in main memory. On the first mainframes
>> I used, 99,999 wouldn't have fit.
>
> You don't need to store all the numbers.
> One buit for each number was sufficient.
>
Are you thinking of something like:
557 $ cat perm
/* Rexx */ signal on novalue; /*
Generate random pemutation of N objects.
*/
N = 99999 /* Size of list. */
Mark. = 1
Found = 0; do I = 1 /* I counts probes. */
R = random( 1, N )
if Mark.R then do
Found = Found + 1 /* Count successes. */
Mark.R = 0
say right( I, 11 ) right( Found, 6 ) right( R, 6 ); end
if Found>= N; then leave I; end I
return( 0 )
OK. I was afraid it would have an unacceptable quadratic behavior
https://en.wikipedia.org/wiki/Joel_Spolsky#Schlemiel_the_Painter.27s_algorithm
... but for 99,999 entries it's pretty good:
...
1025726 99997 70050
1042922 99998 86816
1287281 99999 20208
real 0m2.704s
user 0m2.031s
sys 0m0.281s
-- gil
