Pádraig Brady wrote: > I've attached an updated version where I > abstracted a sparse_map ADT so we may more > easily change in future if required. > I've also added a test and a NEWS entry. ... > Subject: [PATCH] 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.
Thanks for doing that. It looks perfect, though "Improvement" is more descriptive than mere "Change" ;-) It sounds a little better to avoid "will" in the NEWS entry. diff --git a/NEWS b/NEWS index 8b4c707..7a7f761 100644 --- a/NEWS +++ b/NEWS @@ -12,10 +12,10 @@ GNU coreutils NEWS -*- outline -*- Note the use of single quotes, not double quotes. That creates files named xaa.xz, xab.xz and xac.xz. -** Changes in behavior +** Improvements - shuf will more efficiently output small subsets of large permutations. - For example `shuf -i1-$((2**32-1)) -n2` will no longer exhaust memory. + shuf outputs small subsets of large permutations much more efficiently. + For example `shuf -i1-$((2**32-1)) -n2` no longer exhausts memory. * Noteworthy changes in release 8.12 (2011-04-26) [stable]
