Re: new coreutil? shuffle - randomize file contents

[Frederik Eaton]

So, the prototype runs a little slower than I had expected - it's
currently using md5 hashes, I could also look into CRC or something
faster (but less secure, for those concerned). Anyway here is a
sample:

$ time ./sort -R < /usr/share/dict/words > /dev/null
./sort -R < /usr/share/dict/words > /dev/null  1.67s user 0.01s system 99% cpu 
1.684 total
$ time ./sort < /usr/share/dict/words > /dev/null   
./sort < /usr/share/dict/words > /dev/null  0.45s user 0.01s system 99% cpu 
0.462 total
$ time rl < /usr/share/dict/words > /dev/null       
rl < /usr/share/dict/words > /dev/null  0.07s user 0.01s system 99% cpu 0.074 
total
$ wc -l /usr/share/dict/words
96274 /usr/share/dict/words

'rl' is the executable from Arthur's randomize-lines. Of course, this
'sort'-based shuffle has the advantage of being independent of input
order

$ print -l g f e d c b a | ./sort -R | md5sum
dda0a6660319917afd6ed021f27fb452  -
$ print -l a b c d e f g | ./sort -R | md5sum
dda0a6660319917afd6ed021f27fb452  -

and being field-aware

$ print -l "a 1" "a 2" "b 2" "b 03" "c 1" "c 2" | ./sort -k 1,1R -k 2,2n
c 1
c 2
a 1
a 2
b 2
b 03

- whatever these are worth. I just wanted to make sure the slowness is
acceptable before proceeding.

Frederik

On Thu, Jun 02, 2005 at 02:16:10PM -0700, Frederik Eaton wrote:
> James> I think the consensus is that the functionality belongs in "sort".
> James> Beyond that things are a bit less clear.  However, Paul put forward a
> James> proposed usage which adapts the current -k option (see
> James> http://lists.gnu.org/archive/html/bug-coreutils/2005-05/msg00179.html).
> James> Nobody made any comments suggesting that that wasn't a good way of
> James> doing things.
> 
> I liked my proposal for co-opting "-s":
> 
> http://lists.gnu.org/archive/html/bug-coreutils/2005-05/msg00220.html
> 
> In other words, rather than having a "random" column, you'd have a
> "row number" column, which would turn into a random column under the
> hash operation. The documentation for '-s' would be changed to suggest
> that it was enabling a comparison based on input row number.
> 
> James> Last time this was discussed on this list there was some talk about
> James> selecting permutations with a seed.  This makes me uncomfortable since
> James> though doubtless it would be convenient.  The problem is that the
> James> number of permutations of the records of most files is larger than
> James> 2^64, and so representing the seed and making use of it would be very
> James> tricky.  I then had a look at Fascicle 2 of volume 4 of Knuth, but it
> James> concentrates on generating all permutations, and so wasn't directly
> James> much help.
> 
> This seems to be a common point of confusion which I think needs to be
> cleared up. The mapping from random seed to sample space is rarely
> surjective - in fact, whenever you sample more than a few numbers from
> a random number generator, it isn't. It only matters that the number
> of possible seeds is much larger than the number of samplings we would
> ever choose to perform, and if not 2^64 then definitely 2^128 will be
> sufficient for all eternity.
> 
> (Maybe some theoretical common ground is needed. A random variable is a
> function X from a measurable space with probability measure P to
> another measurable space such that X^{-1}(B) is measurable for every
> measurable B in the range of X. We can define a probability measure on
> the range of X by Q(B) = P(X^{-1}(B)), called the distribution of X.
> 
> Usually the domain of X is taken to be unspecified and uncountable,
> but since in practice we only ever sample a finite subset of it - and
> since we cannot calculate the inverse of X at arbitrary points - we
> can replace the domain with a suitably large finite set with discrete
> probability measure and still get good sample coverage, independently
> of the size of the range of X. This new domain is the seed domain.)
> 
> Phil> Paul's statement:
> Phil> > It's not as easy to implement as it sounds, I'm afraid; even if you
> Phil> > can assume /dev/random or /dev/urandom.
> Phil> 
> Phil> is a slight concern, but I imagine the problems are applicable to *any*
> Phil> shuffling utility. Is it that the app must guarantee all lines of a
> Phil> non-seekable stdin must have an equal chance of any sort order?
> 
> See my comment to James above. I think one need not make this
> guarantee, since only a tiny fraction of possible sort orders will be
> able to be tried by the user. However, I think it would be true for my
> proposal (and the one that James suggested to Davis) if one took the
> random number generator or hash function to be variable or unspecified
> during analysis of the algorithm. The fact that we ship with a
> particular RNG or hash function (of all uncountable possibilities,
> some unimplementable) hard-coded is not a problem since its resources
> are never exhausted.
> 
> Jim> It looks like there are some desirable features that can be
> Jim> provided only by a shuffle-enabled program that is key-aware.
> Jim> Key specification and the comparison code are already part of sort.
> Jim> Obviously, duplicating all of that in a separate program is not
> Jim> an option.  I don't relish the idea of factoring out sort's line-
> Jim> and key-handling code either, but it might be feasible.
> Jim> 
> Jim> However, I do like the idea of a new program that simply outputs
> Jim> a random permutation of its input records, and that does it well,
> Jim> and repeatably.  The Unix tool philosophy certainly does encourage
> Jim> the `perform one task and do it well' approach.  Since doing it
> Jim> well includes handling input larger than available virtual memory,
> Jim> this is not trivial -- and it is well suited to the coreutils,
> Jim> i.e., it's not easily implementable as a script.
> Jim> 
> Jim> Initially, I was inclined to say that adding both the new program
> Jim> (no key support) and related functionality to sort was desirable.
> Jim> Thinking of the limits of robustness of such a new program, I
> Jim> realized that if the input is sufficiently large and not seekable
> Jim> (e.g., from a pipe), then the program will have to resort to writing
> Jim> temporary files, much as sort already does.  More duplicated effort,
> Jim> determining how much memory to use (like sort's --buffer-size=SIZE
> Jim> option), managing the temporary files, ensuring that they're removed
> Jim> upon interrupt, etc.  But maybe not prohibitive.  The new program
> Jim> would also have to have an option like sort's -z, --zero-terminated
> Jim> option, and --temporary-directory=DIR, and --output=FILE.  In effect,
> Jim> it would need all of sort's options that don't relate to sorting.
> 
> I did have some sympathy for Davis' point that a specialized 'shuffle'
> can be implemented much more efficiently than one based on an
> algorithm tuned to mergesort... Although I don't see a problem with
> two utilities if someone wants to write the second one, and it is
> correct, I would tend to agree with you and prefer a key-aware version
> as a priority.
> 
> However, I just realized that the algorithm James suggested to Davis
> is wrong for the same reason that the original random patch I
> responded to is wrong:
> 
> http://lists.gnu.org/archive/html/bug-coreutils/2005-01/msg00145.html
> 
> I'm sorry for not noticing this earlier.
> 
> One possibility for an efficient random permutation of a large file is
> a program which scans the file once and records the location of each
> line in an index, then applies a uniformly distributed random
> permutation to this line index by stepping through it in order and
> swapping the current entry with an entry chosen at random from the set
> of later entries, and finally steps through the index again and
> dereferences each line entry and prints out the corresponding line in
> the original file.
> 
> Note that there is a randomize-lines package in Debian by Arthur de
> Jong, I've cc'ed him. It's much faster than 'sort' on small files, but
> doesn't handle large files at all.
> 
> Jim> So implementing a robust shuffle program, even one without key
> Jim> handling capabilities, would require much of the infrastructure
> Jim> already present in sort.c.
> Jim>
> Jim> It sure sounds like shuffle and sort should share a lot of code,
> Jim> one way or another, so why not have them share the line- and key-
> Jim> handling code, too?  I won't rule out adding a new program, like
> Jim> shuffle, but I confess I'm less inclined now than when I started
> Jim> typing this message.
> 
> Well, it would only be line-handling code, and whatever else, but no
> key-handling code since Davis' shuffle wouldn't be key-aware, unless
> you're talking about my proposal. And maybe common things could be put
> in a library, I don't know. I am against duplication but not against
> change.
> 
> Frederik
> 

-- 
http://ofb.net/~frederik/