shuf: use memory more efficiently when returning a subset
authorPádraig Brady <P@draigBrady.com>
Fri, 13 May 2011 17:41:42 +0000 (18:41 +0100)
committerPádraig Brady <P@draigBrady.com>
Sat, 14 May 2011 09:30:12 +0000 (10:30 +0100)
commit27873f1deb69745c79d403bbb8e1145bc18f55b8
treed3b752eed0035e9ce767ea73c07f3b8577deaead
parent9d152a1ed72968ae3624a76e155fe16b240348dc
shuf: use memory more efficiently when returning a subset

* gl/lib/randperm.c (randperm_new): When the number of items
to return H, is much smaller than the total number of items N,
use a hash to represent the sparse permutations of the set N.
This is currently enabled for N > 128K and N/H > 32.
* tests/misc/shuf: Ensure shuf can quickly return 2 numbers
from a large range.
* gl/modules/randperm: Depend on hash.
* NEWS: Mention the change.
NEWS
gl/lib/randperm.c
gl/modules/randperm
tests/misc/shuf