Re: Generating pseudo-random integers

[Pádraig Brady]

On 05/02/11 14:13, Jim Meyering wrote:
> Pádraig Brady wrote:

>> Though on trying shuf to generate the numbers I notice:
>>
>> $ shuf -i0-$((2**31)) -n1
>> 1241475845
>> $ shuf -i0-$((2**31)) -n2
>> shuf: memory exhausted
> 
> For small N and large B-A, that code should be improved.
> It certainly doesn't need to allocate so much space.

I had a quick look this morning, and did a simple
sparse array implementation (attached) using the hash module.
It could be improved to have less dependence on malloc(),
but it gives a large improvement for the above case at least.

I tested with this:

for n in $(seq 2 32); do
  for h in $(seq 2 32); do
    test $h -gt $n && continue
    for s in o n; do
      test $s = o && shuf=shuf || shuf=./shuf
      num=$(env time -f "$s:${h},${n} = %e,%M" \
            $shuf -i0-$((2**$n-2)) -n$((2**$h-2)) | wc -l)
      test $num = $((2**$h-2)) || echo "$s:${h},${n} = failed" >&2
    done
  done
done

A interpretation of a part of the output is:

        log2(h) log2(n) time(s) mem(KiB)  notes
old     2       20      0.01    17728
new     2       20      0.00    2272      less mem, less time
old     13      20      0.01    17744
new     13      20      0.01    3024      time equivalent
old     14      20      0.02    17744
new     14      20      0.03    5344
old     15      20      0.03    17728
new     15      20      0.06    9360      half mem, half speed
old     16      20      0.05    17728
new     16      20      0.05    17792     back to non sparse

cheers,
Pádraig.

randperm.c.diff
Description: Text Data