## digitalmars.D - shuffling lines in a stream

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
The high traffic enjoyed by "random k-sample of a file" confirms that
plenty of people around here have idle cycles ready to be spent on fun

In that vein, here's another problem. Say you want to randomly shuffle
lines in a stream. You don't know the size beforehand, and one pass is
preferable. The stream can be larger than the working memory, but not an
unbounded amount of times larger. Also lines in the stream can be
unbounded, but it is guaranteed that at least a nonzero fraction of the
file fits in working memory.

You can use temporary files, but of course minimizing their total size
is recommended. Speed is of course important. Draft your solution and
explain why you think it's correct and advantageous.

In case you hate random stuff, just wait; the next problem won't have
any random element in it :o).

Andrei

Oct 09 2008
Reply to Andrei,

The high traffic enjoyed by "random k-sample of a file" confirms that
plenty of people around here have idle cycles ready to be spent on fun

In that vein, here's another problem. Say you want to randomly shuffle
lines in a stream. You don't know the size beforehand, and one pass is
preferable. The stream can be larger than the working memory, but not
an unbounded amount of times larger. Also lines in the stream can be
unbounded, but it is guaranteed that at least a nonzero fraction of
the file fits in working memory.

You can use temporary files, but of course minimizing their total size
is recommended. Speed is of course important. Draft your solution and
explain why you think it's correct and advantageous.

In case you hate random stuff, just wait; the next problem won't have
any random element in it :o).

Andrei

Um... I'm not following that.

Oct 09 2008
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
BCS wrote:

The high traffic enjoyed by "random k-sample of a file" confirms that
plenty of people around here have idle cycles ready to be spent on fun

In that vein, here's another problem. Say you want to randomly shuffle
lines in a stream. You don't know the size beforehand, and one pass is
preferable. The stream can be larger than the working memory, but not
an unbounded amount of times larger. Also lines in the stream can be
unbounded, but it is guaranteed that at least a nonzero fraction of
the file fits in working memory.

You can use temporary files, but of course minimizing their total size
is recommended. Speed is of course important. Draft your solution and
explain why you think it's correct and advantageous.

In case you hate random stuff, just wait; the next problem won't have
any random element in it :o).

Andrei

Um... I'm not following that.

Very simple: given a file, just randomly change the order of its lines
and output them. For example (assume read from standard input):

$./shuffle a b c ^D b a c$ ./shuffle
a
b
c
^D
b
c
a
$_ Andrei  Oct 09 2008 BCS <ao pathlink.com> writes: Reply to Andrei, You don't know the size beforehand, and one pass is preferable. The stream can be larger than the working memory, but not an unbounded amount of times larger. Also lines in the stream can be unbounded, but it is guaranteed that at least a nonzero fraction of the file fits in working memory. I got the bit about the end effect. The above is what I didn't get.  Oct 09 2008 Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes: BCS wrote: Reply to Andrei, You don't know the size beforehand, and one pass is preferable. The stream can be larger than the working memory, but not an unbounded amount of times larger. Also lines in the stream can be unbounded, but it is guaranteed that at least a nonzero fraction of the file fits in working memory. I got the bit about the end effect. The above is what I didn't get. Don't worry about that for now. Andrei  Oct 09 2008 BCS <ao pathlink.com> writes: Reply to Andrei, BCS wrote: Reply to Andrei, You don't know the size beforehand, and one pass is preferable. The stream can be larger than the working memory, but not an unbounded amount of times larger. Also lines in the stream can be unbounded, but it is guaranteed that at least a nonzero fraction of the file fits in working memory. Andrei cache the whole file into a tmp file store slice data on the way through (start/length of each line) shuffle that set lseek/read/write each slice in order Quick'n'dirty The only fun part is how to shuffle the deck. What I think might be easiest to do would be to qsort it with rand as the compare function. I don't think there is any way to avoid storing the whole file because for a uniform sort there is a possibility that the last line will come out first.  Oct 09 2008 Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes: BCS wrote: Reply to Andrei, BCS wrote: Reply to Andrei, You don't know the size beforehand, and one pass is preferable. The stream can be larger than the working memory, but not an unbounded amount of times larger. Also lines in the stream can be unbounded, but it is guaranteed that at least a nonzero fraction of the file fits in working memory. Andrei cache the whole file into a tmp file store slice data on the way through (start/length of each line) shuffle that set lseek/read/write each slice in order Quick'n'dirty The only fun part is how to shuffle the deck. What I think might be easiest to do would be to qsort it with rand as the compare function. I don't think there is any way to avoid storing the whole file because for a uniform sort there is a possibility that the last line will come out first. I agree with the last paragraph, but lseeking seems overly inefficient. Could you avoid that? Andrei  Oct 09 2008 BCS <ao pathlink.com> writes: Reply to Andrei, BCS wrote: I don't think there is any way to avoid storing the whole file because for a uniform sort there is a possibility that the last line will come out first. inefficient. Could you avoid that? Andrei algorithmically, I don't think the lseek will matter, as to I/O and cache effects, I'll leave that to someone else.  Oct 10 2008 Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes: BCS wrote: Reply to Andrei, BCS wrote: I don't think there is any way to avoid storing the whole file because for a uniform sort there is a possibility that the last line will come out first. inefficient. Could you avoid that? Andrei algorithmically, I don't think the lseek will matter, I think it does. Essentially you impose random access on the input, or copy to a medium that offers it. gunzip --stdout bigfile.gz | shuffle You'll have to compulsively store a copy of the input. Besides, random access is kind of a dicey proposition on large files. Of course, only measurement will show... Andrei  Oct 10 2008 BCS <ao pathlink.com> writes: Reply to Andrei, BCS wrote: Reply to Andrei, BCS wrote: I don't think there is any way to avoid storing the whole file because for a uniform sort there is a possibility that the last line will come out first. inefficient. Could you avoid that? Andrei copy to a medium that offers it. gunzip --stdout bigfile.gz | shuffle You'll have to compulsively store a copy of the input. You have to anyway, or is that not what you agread with above? Besides, random access is kind of a dicey proposition on large files. Of course, only measurement will show... Is that not an I/O effect? as to I/O and cache effects, I'll leave that to someone else. Andrei  Oct 10 2008 Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes: BCS wrote: Reply to Andrei, BCS wrote: Reply to Andrei, BCS wrote: I don't think there is any way to avoid storing the whole file because for a uniform sort there is a possibility that the last line will come out first. inefficient. Could you avoid that? Andrei copy to a medium that offers it. gunzip --stdout bigfile.gz | shuffle You'll have to compulsively store a copy of the input. You have to anyway, or is that not what you agread with above? Well I agree things can be coded such that you make the copy only if the file is too large anyway. But one lseek call per line is a complete disaster, whether you call it I/O effect or whatnot. I'd go as far as saying I'd never even try such a solution, especially since there exists a forward-pass algorithm. Of course measuring would be a great way to prove me wrong. Andrei  Oct 10 2008 BCS <ao pathlink.com> writes: Reply to Andrei, Well I agree things can be coded such that you make the copy only if the file is too large anyway. But one lseek call per line is a complete disaster, whether you call it I/O effect or whatnot. I'd go as far as saying I'd never even try such a solution, especially since there exists a forward-pass algorithm. Of course measuring would be a great way to prove me wrong. Andrei I think Big-O on mine is n. I don't think that can be beat. (Maybe I was being not at all clear that I was only looking at that aspect, the rest doesn't interest me as a puzzle)  Oct 10 2008 Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes: BCS wrote: Reply to Andrei, Well I agree things can be coded such that you make the copy only if the file is too large anyway. But one lseek call per line is a complete disaster, whether you call it I/O effect or whatnot. I'd go as far as saying I'd never even try such a solution, especially since there exists a forward-pass algorithm. Of course measuring would be a great way to prove me wrong. Andrei I think Big-O on mine is n. I disagree. Big-O with lseek under the rug? That's a non-solution because it essentially redefines the problem into "if I had a random-access operator then this is pretty much like array shuffling". If you have a random-access operator there is no problem to think about. Andrei  Oct 10 2008 BCS <ao pathlink.com> writes: Reply to Andrei, BCS wrote: Reply to Andrei, Well I agree things can be coded such that you make the copy only if the file is too large anyway. But one lseek call per line is a complete disaster, whether you call it I/O effect or whatnot. I'd go as far as saying I'd never even try such a solution, especially since there exists a forward-pass algorithm. Of course measuring would be a great way to prove me wrong. Andrei because it essentially redefines the problem into "if I had a random-access operator then this is pretty much like array shuffling". If you have a random-access operator there is no problem to think about. Andrei In that case this isn't a problem /I/ am intersted in trying to solve.  Oct 10 2008 Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes: Andrei Alexandrescu wrote: The high traffic enjoyed by "random k-sample of a file" confirms that plenty of people around here have idle cycles ready to be spent on fun tasks. In that vein, here's another problem. Say you want to randomly shuffle lines in a stream. You don't know the size beforehand, and one pass is preferable. The stream can be larger than the working memory, but not an unbounded amount of times larger. Also lines in the stream can be unbounded, but it is guaranteed that at least a nonzero fraction of the file fits in working memory. You can use temporary files, but of course minimizing their total size is recommended. Speed is of course important. Draft your solution and explain why you think it's correct and advantageous. In case you hate random stuff, just wait; the next problem won't have any random element in it :o). Andrei Forgot to mention a desirable property. It would be nice if the algorithm would naturally subscale, e.g. if ran on a short file, it would produce a shuffled file with the speed competitive with an algorithm conceived for shorter files. Andrei  Oct 09 2008 Robert Fraser <fraserofthenight gmail.com> writes: Andrei Alexandrescu wrote: The high traffic enjoyed by "random k-sample of a file" confirms that plenty of people around here have idle cycles ready to be spent on fun tasks. In that vein, here's another problem. Say you want to randomly shuffle lines in a stream. You don't know the size beforehand, and one pass is preferable. The stream can be larger than the working memory, but not an unbounded amount of times larger. Also lines in the stream can be unbounded, but it is guaranteed that at least a nonzero fraction of the file fits in working memory. You can use temporary files, but of course minimizing their total size is recommended. Speed is of course important. Draft your solution and explain why you think it's correct and advantageous. In case you hate random stuff, just wait; the next problem won't have any random element in it :o). Andrei I know it's been suggested before, but we really need digitalmars.d.offtopic  Oct 09 2008 Bruno Medeiros <brunodomedeiros+spam com.gmail> writes: Robert Fraser wrote: I know it's been suggested before, but we really need digitalmars.d.offtopic Word. -- Bruno Medeiros - Software Developer, MSc. in CS/E graduate http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D  Oct 16 2008 BLS <nanali nospam-wanadoo.fr> writes: Andrei Alexandrescu schrieb: The high traffic enjoyed by "random k-sample of a file" confirms that plenty of people around here have idle cycles ready to be spent on fun tasks. In that vein, here's another problem. Say you want to randomly shuffle lines in a stream. You don't know the size beforehand, and one pass is preferable. The stream can be larger than the working memory, but not an unbounded amount of times larger. Also lines in the stream can be unbounded, but it is guaranteed that at least a nonzero fraction of the file fits in working memory. You can use temporary files, but of course minimizing their total size is recommended. Speed is of course important. Draft your solution and explain why you think it's correct and advantageous. In case you hate random stuff, just wait; the next problem won't have any random element in it :o). Andrei Just in general I would use a memory mapped file. Map data in chunks, say 4MB. Chunks are unmapped as necessary ~LRU, means implement a LRUCache. This is how some "in memory database-engines" solve that sort of problems. Also possible : I miss the real problem :( Bjoern  Oct 09 2008 Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes: BLS wrote: Andrei Alexandrescu schrieb: The high traffic enjoyed by "random k-sample of a file" confirms that plenty of people around here have idle cycles ready to be spent on fun tasks. In that vein, here's another problem. Say you want to randomly shuffle lines in a stream. You don't know the size beforehand, and one pass is preferable. The stream can be larger than the working memory, but not an unbounded amount of times larger. Also lines in the stream can be unbounded, but it is guaranteed that at least a nonzero fraction of the file fits in working memory. You can use temporary files, but of course minimizing their total size is recommended. Speed is of course important. Draft your solution and explain why you think it's correct and advantageous. In case you hate random stuff, just wait; the next problem won't have any random element in it :o). Andrei Just in general I would use a memory mapped file. Map data in chunks, say 4MB. Chunks are unmapped as necessary ~LRU, means implement a LRUCache. This is how some "in memory database-engines" solve that sort of problems. Also possible : I miss the real problem :( I think I overspecified it. Pure and simple you must randomize lines in a file that may not fit in memory. Note that memory mapping may help the speed of whichever implementation, but gives zero indication on how you would actually tackle the problem. Please add [OT] to the title when answering, as I did, so people can filter it out. I think these are cool things to discuss nonetheless in D's context because it gives us ideas on language features and libraries. Andrei  Oct 10 2008 Sergey Gromov <snake.scaly gmail.com> writes: Thu, 09 Oct 2008 23:42:47 -0500, Andrei Alexandrescu wrote: The high traffic enjoyed by "random k-sample of a file" confirms that plenty of people around here have idle cycles ready to be spent on fun tasks. In that vein, here's another problem. Say you want to randomly shuffle lines in a stream. You don't know the size beforehand, and one pass is preferable. The stream can be larger than the working memory, but not an unbounded amount of times larger. Also lines in the stream can be unbounded, but it is guaranteed that at least a nonzero fraction of the file fits in working memory. You can use temporary files, but of course minimizing their total size is recommended. Speed is of course important. Draft your solution and explain why you think it's correct and advantageous. Well, my temporary file contains the whole stream. Because there is a probability that the last line of the stream goes first. module shuffle; import std.cstream: din, dout; import std.stream: BufferedFile, FileMode; import std.file: remove, exists; import std.random: Random, uniform, unpredictableSeed, randomShuffle; import std.stdio: writeln; void main() { auto gen = Random(unpredictableSeed); enum tempName = "temp.$";
if (exists(tempName))
remove(tempName);
auto temp = new BufferedFile(tempName,
FileMode.In | FileMode.OutNew);

ulong[] cache;

foreach (char[] s; din)
{
cache ~= temp.position;
temp.writeLine(s);
}

randomShuffle(cache, gen);

foreach (pos; cache)
{
temp.position = pos;
}

temp.close();
}

Oct 10 2008
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Sergey Gromov wrote:
Thu, 09 Oct 2008 23:42:47 -0500,
Andrei Alexandrescu wrote:
The high traffic enjoyed by "random k-sample of a file" confirms that
plenty of people around here have idle cycles ready to be spent on fun

In that vein, here's another problem. Say you want to randomly shuffle
lines in a stream. You don't know the size beforehand, and one pass is
preferable. The stream can be larger than the working memory, but not an
unbounded amount of times larger. Also lines in the stream can be
unbounded, but it is guaranteed that at least a nonzero fraction of the
file fits in working memory.

You can use temporary files, but of course minimizing their total size
is recommended. Speed is of course important. Draft your solution and
explain why you think it's correct and advantageous.

Well, my temporary file contains the whole stream.  Because there is a
probability that the last line of the stream goes first.

Yes, that probability exists, but that doesn't imply you must load the
entire file in memory.

Andrei

Oct 10 2008
Sergey Gromov <snake.scaly gmail.com> writes:
Fri, 10 Oct 2008 07:55:38 -0500,
Andrei Alexandrescu wrote:
Sergey Gromov wrote:
Thu, 09 Oct 2008 23:42:47 -0500,
Andrei Alexandrescu wrote:
The high traffic enjoyed by "random k-sample of a file" confirms that
plenty of people around here have idle cycles ready to be spent on fun

In that vein, here's another problem. Say you want to randomly shuffle
lines in a stream. You don't know the size beforehand, and one pass is
preferable. The stream can be larger than the working memory, but not an
unbounded amount of times larger. Also lines in the stream can be
unbounded, but it is guaranteed that at least a nonzero fraction of the
file fits in working memory.

You can use temporary files, but of course minimizing their total size
is recommended. Speed is of course important. Draft your solution and
explain why you think it's correct and advantageous.

Well, my temporary file contains the whole stream.  Because there is a
probability that the last line of the stream goes first.

Yes, that probability exists, but that doesn't imply you must load the
entire file in memory.

This implies though that I cannot start output before I read all the
lines from the stream.  Therefore I must store those lines somewhere.

Oct 10 2008
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Sergey Gromov wrote:
Fri, 10 Oct 2008 07:55:38 -0500,
Andrei Alexandrescu wrote:
Sergey Gromov wrote:
Thu, 09 Oct 2008 23:42:47 -0500,
Andrei Alexandrescu wrote:
The high traffic enjoyed by "random k-sample of a file" confirms that
plenty of people around here have idle cycles ready to be spent on fun

In that vein, here's another problem. Say you want to randomly shuffle
lines in a stream. You don't know the size beforehand, and one pass is
preferable. The stream can be larger than the working memory, but not an
unbounded amount of times larger. Also lines in the stream can be
unbounded, but it is guaranteed that at least a nonzero fraction of the
file fits in working memory.

You can use temporary files, but of course minimizing their total size
is recommended. Speed is of course important. Draft your solution and
explain why you think it's correct and advantageous.

probability that the last line of the stream goes first.

entire file in memory.

This implies though that I cannot start output before I read all the
lines from the stream.  Therefore I must store those lines somewhere.

Creating temporary files is fine as long as you never need to store the
entire input in memory.

Andrei

Oct 10 2008
KennyTM~ <kennytm gmail.com> writes:
Andrei Alexandrescu wrote:
Sergey Gromov wrote:
Fri, 10 Oct 2008 07:55:38 -0500,
Andrei Alexandrescu wrote:
Sergey Gromov wrote:
Thu, 09 Oct 2008 23:42:47 -0500,
Andrei Alexandrescu wrote:
The high traffic enjoyed by "random k-sample of a file" confirms
that plenty of people around here have idle cycles ready to be

In that vein, here's another problem. Say you want to randomly
shuffle lines in a stream. You don't know the size beforehand, and
one pass is preferable. The stream can be larger than the working
memory, but not an unbounded amount of times larger. Also lines in
the stream can be unbounded, but it is guaranteed that at least a
nonzero fraction of the file fits in working memory.

You can use temporary files, but of course minimizing their total
size is recommended. Speed is of course important. Draft your
solution and explain why you think it's correct and advantageous.

a probability that the last line of the stream goes first.

the entire file in memory.

This implies though that I cannot start output before I read all the
lines from the stream.  Therefore I must store those lines somewhere.

Creating temporary files is fine as long as you never need to store the
entire input in memory.

Andrei

So HDD (or any file system) is not counted as memory? Then just store
all temporary variables to HDD.

Oct 10 2008
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
KennyTM~ wrote:
Andrei Alexandrescu wrote:
Sergey Gromov wrote:
Fri, 10 Oct 2008 07:55:38 -0500,
Andrei Alexandrescu wrote:
Sergey Gromov wrote:
Thu, 09 Oct 2008 23:42:47 -0500,
Andrei Alexandrescu wrote:
The high traffic enjoyed by "random k-sample of a file" confirms
that plenty of people around here have idle cycles ready to be

In that vein, here's another problem. Say you want to randomly
shuffle lines in a stream. You don't know the size beforehand, and
one pass is preferable. The stream can be larger than the working
memory, but not an unbounded amount of times larger. Also lines in
the stream can be unbounded, but it is guaranteed that at least a
nonzero fraction of the file fits in working memory.

You can use temporary files, but of course minimizing their total
size is recommended. Speed is of course important. Draft your
solution and explain why you think it's correct and advantageous.

is a probability that the last line of the stream goes first.

the entire file in memory.

This implies though that I cannot start output before I read all the
lines from the stream.  Therefore I must store those lines somewhere.

Creating temporary files is fine as long as you never need to store
the entire input in memory.

Andrei

So HDD (or any file system) is not counted as memory? Then just store
all temporary variables to HDD.

This takes us back to one lseek per line. You can create temporary
files. They behave as files usually do - they are better accessed in
sequential patterns and not too many times.

Andrei

Oct 10 2008
Sergey Gromov <snake.scaly gmail.com> writes:
Fri, 10 Oct 2008 09:20:44 -0500,
Andrei Alexandrescu wrote:
Sergey Gromov wrote:
Fri, 10 Oct 2008 07:55:38 -0500,
Andrei Alexandrescu wrote:
Sergey Gromov wrote:
Well, my temporary file contains the whole stream.  Because there is a
probability that the last line of the stream goes first.

Yes, that probability exists, but that doesn't imply you must load the
entire file in memory.

This implies though that I cannot start output before I read all the
lines from the stream.  Therefore I must store those lines somewhere.

Creating temporary files is fine as long as you never need to store the
entire input in memory.

Ok, let me re-formulate the task then, since the creation of a temporary
file containing all the lines seems inevitable.  You basically want to
uniformly shuffle lines in a very large file.

The idea is this.  Let N be number of lines in the file, which you know
after storing it.  There are two passes, forward and backward.  They are
symmetric.  On a forward pass you read as many lines as you can fit in
memory, let it be m.  Shuffle them.  Then choose a number, k which is
0 < k < m and is somehow based upon the m and N, like k = m * m/N.
Write the k first lines back into the file and discard them from memory.
Append as many new lines to your memory array as possible.  Shuffle.
Choose k.  Write.  Repeat.  The reverse pass is exactly the same but you
start from the end of file.

The tricky part is how to choose k.  It obviously needs to take number
of discarded lines, q, into account like in k = m * m/(N-q).  But my
math-fu is almost non-existent so I'm unable to prove if this approach
can give an uniform distribution.  I feel like it can though.

Oct 10 2008
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Sergey Gromov wrote:
Fri, 10 Oct 2008 09:20:44 -0500,
Andrei Alexandrescu wrote:
Sergey Gromov wrote:
Fri, 10 Oct 2008 07:55:38 -0500,
Andrei Alexandrescu wrote:
Sergey Gromov wrote:
Well, my temporary file contains the whole stream.  Because there is a
probability that the last line of the stream goes first.

entire file in memory.

lines from the stream.  Therefore I must store those lines somewhere.

entire input in memory.

Ok, let me re-formulate the task then, since the creation of a temporary
file containing all the lines seems inevitable.  You basically want to
uniformly shuffle lines in a very large file.

The idea is this.  Let N be number of lines in the file, which you know
after storing it.  There are two passes, forward and backward.  They are
symmetric.  On a forward pass you read as many lines as you can fit in
memory, let it be m.  Shuffle them.  Then choose a number, k which is
0 < k < m and is somehow based upon the m and N, like k = m * m/N.
Write the k first lines back into the file and discard them from memory.
Append as many new lines to your memory array as possible.  Shuffle.
Choose k.  Write.  Repeat.  The reverse pass is exactly the same but you
start from the end of file.

The tricky part is how to choose k.  It obviously needs to take number
of discarded lines, q, into account like in k = m * m/(N-q).  But my
math-fu is almost non-existent so I'm unable to prove if this approach
can give an uniform distribution.  I feel like it can though.

Feeling doesn't qualify.

Andrei

Oct 10 2008
Christopher Wright <dhasenan gmail.com> writes:
Sergey Gromov wrote:
Fri, 10 Oct 2008 09:20:44 -0500,
Andrei Alexandrescu wrote:
Sergey Gromov wrote:
Fri, 10 Oct 2008 07:55:38 -0500,
Andrei Alexandrescu wrote:
Sergey Gromov wrote:
Well, my temporary file contains the whole stream.  Because there is a
probability that the last line of the stream goes first.

entire file in memory.

lines from the stream.  Therefore I must store those lines somewhere.

entire input in memory.

Ok, let me re-formulate the task then, since the creation of a temporary
file containing all the lines seems inevitable.  You basically want to
uniformly shuffle lines in a very large file.

The idea is this.  Let N be number of lines in the file, which you know
after storing it.  There are two passes, forward and backward.  They are
symmetric.  On a forward pass you read as many lines as you can fit in
memory, let it be m.  Shuffle them.  Then choose a number, k which is
0 < k < m and is somehow based upon the m and N, like k = m * m/N.
Write the k first lines back into the file and discard them from memory.
Append as many new lines to your memory array as possible.  Shuffle.
Choose k.  Write.  Repeat.  The reverse pass is exactly the same but you
start from the end of file.

The tricky part is how to choose k.  It obviously needs to take number
of discarded lines, q, into account like in k = m * m/(N-q).  But my
math-fu is almost non-existent so I'm unable to prove if this approach
can give an uniform distribution.  I feel like it can though.

You have to continually alter k to maintain a random distribution, but
you have an invariant 0 <= k <= m. Those bounds mean you can't use this
approach.

Oct 11 2008
Sean Kelly <sean invisibleduck.org> writes:
It would be slower than the seeking option, but something like a
randomized mergesort would work as well.  If the program can buffer k
lines in a file containing n lines, then read the first k lines into
memory, shuffle them, and write them out to a temporary file.  Repeat
until the input is exhausted.  Now randomly pick two of the temporary
files and randomly merge them.  Repeat until two temporary files remain,
then output the result of the final random merge to the screen.

For small files (ie. where n<k) the file would be read, shuffled in
memory, and printed to the screen, assuming the proper checks were in place.

Sean

Oct 10 2008
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Sean Kelly wrote:
It would be slower than the seeking option, but something like a
randomized mergesort would work as well.  If the program can buffer k
lines in a file containing n lines, then read the first k lines into
memory, shuffle them, and write them out to a temporary file.  Repeat
until the input is exhausted.  Now randomly pick two of the temporary
files and randomly merge them.  Repeat until two temporary files remain,
then output the result of the final random merge to the screen.

For small files (ie. where n<k) the file would be read, shuffled in
memory, and printed to the screen, assuming the proper checks were in
place.

Sweet! This is even better than my solution. (And it's much faster than
seeking.)

Andrei

Oct 10 2008
Christopher Wright <dhasenan gmail.com> writes:
Andrei Alexandrescu wrote:
Sean Kelly wrote:
It would be slower than the seeking option, but something like a
randomized mergesort would work as well.  If the program can buffer k
lines in a file containing n lines, then read the first k lines into
memory, shuffle them, and write them out to a temporary file.  Repeat
until the input is exhausted.  Now randomly pick two of the temporary
files and randomly merge them.  Repeat until two temporary files
remain, then output the result of the final random merge to the screen.

For small files (ie. where n<k) the file would be read, shuffled in
memory, and printed to the screen, assuming the proper checks were in
place.

Sweet! This is even better than my solution. (And it's much faster than
seeking.)

Andrei

You can reduce the number of passes by using more temporary files per
iteration. For instance, with O(log n) files per iteration, you'll get a
time complexity of O(n log* n) rather than O(n log n). However, using
more files makes the disk cache unhappy.

Oct 11 2008
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Sean Kelly wrote:
It would be slower than the seeking option, but something like a
randomized mergesort would work as well.  If the program can buffer k
lines in a file containing n lines, then read the first k lines into
memory, shuffle them, and write them out to a temporary file.  Repeat
until the input is exhausted.  Now randomly pick two of the temporary
files and randomly merge them.  Repeat until two temporary files remain,
then output the result of the final random merge to the screen.

For small files (ie. where n<k) the file would be read, shuffled in
memory, and printed to the screen, assuming the proper checks were in
place.

I think I found a problem with your solution. Consider you break the
file in three chunks: a, b, c. Then you pick at random b and c and
randomly merge them. The problem is, you make early the decision that
nothing in a will appear in the first two thirds of the result. So the
quality of randomness suffers. How would you address that?

Andrei

Oct 10 2008
Sergey Gromov <snake.scaly gmail.com> writes:
Fri, 10 Oct 2008 15:54:18 -0500,
Andrei Alexandrescu wrote:
Sean Kelly wrote:
It would be slower than the seeking option, but something like a
randomized mergesort would work as well.  If the program can buffer k
lines in a file containing n lines, then read the first k lines into
memory, shuffle them, and write them out to a temporary file.  Repeat
until the input is exhausted.  Now randomly pick two of the temporary
files and randomly merge them.  Repeat until two temporary files remain,
then output the result of the final random merge to the screen.

For small files (ie. where n<k) the file would be read, shuffled in
memory, and printed to the screen, assuming the proper checks were in
place.

I think I found a problem with your solution. Consider you break the
file in three chunks: a, b, c. Then you pick at random b and c and
randomly merge them. The problem is, you make early the decision that
nothing in a will appear in the first two thirds of the result. So the
quality of randomness suffers. How would you address that?

After merging b and c you end up with a and bc.  Then you randomly merge
these two files and lines from a have all the chances to appear anywhere
within result.

When randomly merging, the probability of picking a line from a file
should be proportional to a number of lines left in that file.

Oct 10 2008
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Sergey Gromov wrote:
Fri, 10 Oct 2008 15:54:18 -0500,
Andrei Alexandrescu wrote:
Sean Kelly wrote:
It would be slower than the seeking option, but something like a
randomized mergesort would work as well.  If the program can buffer k
lines in a file containing n lines, then read the first k lines into
memory, shuffle them, and write them out to a temporary file.  Repeat
until the input is exhausted.  Now randomly pick two of the temporary
files and randomly merge them.  Repeat until two temporary files remain,
then output the result of the final random merge to the screen.

For small files (ie. where n<k) the file would be read, shuffled in
memory, and printed to the screen, assuming the proper checks were in
place.

file in three chunks: a, b, c. Then you pick at random b and c and
randomly merge them. The problem is, you make early the decision that
nothing in a will appear in the first two thirds of the result. So the
quality of randomness suffers. How would you address that?

After merging b and c you end up with a and bc.  Then you randomly merge
these two files and lines from a have all the chances to appear anywhere
within result.

When randomly merging, the probability of picking a line from a file
should be proportional to a number of lines left in that file.

How do you "randomly merge"? Describe the process.

Andrei

Oct 10 2008
Sergey Gromov <snake.scaly gmail.com> writes:
Fri, 10 Oct 2008 16:10:29 -0500,
Andrei Alexandrescu wrote:
Sergey Gromov wrote:
Fri, 10 Oct 2008 15:54:18 -0500,
Andrei Alexandrescu wrote:
Sean Kelly wrote:
It would be slower than the seeking option, but something like a
randomized mergesort would work as well.  If the program can buffer k
lines in a file containing n lines, then read the first k lines into
memory, shuffle them, and write them out to a temporary file.  Repeat
until the input is exhausted.  Now randomly pick two of the temporary
files and randomly merge them.  Repeat until two temporary files remain,
then output the result of the final random merge to the screen.

For small files (ie. where n<k) the file would be read, shuffled in
memory, and printed to the screen, assuming the proper checks were in
place.

file in three chunks: a, b, c. Then you pick at random b and c and
randomly merge them. The problem is, you make early the decision that
nothing in a will appear in the first two thirds of the result. So the
quality of randomness suffers. How would you address that?

After merging b and c you end up with a and bc.  Then you randomly merge
these two files and lines from a have all the chances to appear anywhere
within result.

When randomly merging, the probability of picking a line from a file
should be proportional to a number of lines left in that file.

How do you "randomly merge"? Describe the process.

a[] and b[] are files to merge.  ab[] is the result.  a.length and
b.length are number of lines left in either file.

while (a.length || b.length)
{
if (uniform(gen, 0, a.length + b.length) < a.length)
{
a.next();
}
else
{
b.next();
}
}

Oct 10 2008
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Sergey Gromov wrote:
Fri, 10 Oct 2008 16:10:29 -0500,
Andrei Alexandrescu wrote:
Sergey Gromov wrote:
Fri, 10 Oct 2008 15:54:18 -0500,
Andrei Alexandrescu wrote:
Sean Kelly wrote:
It would be slower than the seeking option, but something like a
randomized mergesort would work as well.  If the program can buffer k
lines in a file containing n lines, then read the first k lines into
memory, shuffle them, and write them out to a temporary file.  Repeat
until the input is exhausted.  Now randomly pick two of the temporary
files and randomly merge them.  Repeat until two temporary files remain,
then output the result of the final random merge to the screen.

For small files (ie. where n<k) the file would be read, shuffled in
memory, and printed to the screen, assuming the proper checks were in
place.

file in three chunks: a, b, c. Then you pick at random b and c and
randomly merge them. The problem is, you make early the decision that
nothing in a will appear in the first two thirds of the result. So the
quality of randomness suffers. How would you address that?

these two files and lines from a have all the chances to appear anywhere
within result.

When randomly merging, the probability of picking a line from a file
should be proportional to a number of lines left in that file.

a[] and b[] are files to merge.  ab[] is the result.  a.length and
b.length are number of lines left in either file.

while (a.length || b.length)
{
if (uniform(gen, 0, a.length + b.length) < a.length)
{
a.next();
}
else
{
b.next();
}
}

This should work. Use of ranges noted :o).

Andrei

Oct 10 2008
Sergey Gromov <snake.scaly gmail.com> writes:
Fri, 10 Oct 2008 16:27:03 -0500,
Andrei Alexandrescu wrote:
Sergey Gromov wrote:
Fri, 10 Oct 2008 16:10:29 -0500,
Andrei Alexandrescu wrote:
Sergey Gromov wrote:
Fri, 10 Oct 2008 15:54:18 -0500,
Andrei Alexandrescu wrote:
Sean Kelly wrote:
It would be slower than the seeking option, but something like a
randomized mergesort would work as well.  If the program can buffer k
lines in a file containing n lines, then read the first k lines into
memory, shuffle them, and write them out to a temporary file.  Repeat
until the input is exhausted.  Now randomly pick two of the temporary
files and randomly merge them.  Repeat until two temporary files remain,
then output the result of the final random merge to the screen.

For small files (ie. where n<k) the file would be read, shuffled in
memory, and printed to the screen, assuming the proper checks were in
place.

file in three chunks: a, b, c. Then you pick at random b and c and
randomly merge them. The problem is, you make early the decision that
nothing in a will appear in the first two thirds of the result. So the
quality of randomness suffers. How would you address that?

these two files and lines from a have all the chances to appear anywhere
within result.

When randomly merging, the probability of picking a line from a file
should be proportional to a number of lines left in that file.

a[] and b[] are files to merge.  ab[] is the result.  a.length and
b.length are number of lines left in either file.

while (a.length || b.length)
{
if (uniform(gen, 0, a.length + b.length) < a.length)
{
a.next();
}
else
{
b.next();
}
}

This should work.

I just rigorously proved that probability of line from a getting into
output position 0 is equal to probability of line from a getting into
position 1 and is equal to a.length/(a.length+b.length).  I need to
recollect TeX to write this proof down for electronic use.

Use of ranges noted :o).

Except that a.length and b.length should be stored in files somehow.

Oct 10 2008
Sergey Gromov <snake.scaly gmail.com> writes:
Fri, 10 Oct 2008 16:27:03 -0500,
Andrei Alexandrescu wrote:
while (a.length || b.length)
{
if (uniform(gen, 0, a.length + b.length) < a.length)
{
a.next();
}
else
{
b.next();
}
}

This should work. Use of ranges noted :o).

Actually I felt an urge to write:

if (uniform(gen, 0, a.length + b.length) < a.length)
ab.put(a.next);
else
ab.put(b.next);

I had to really get hold of myself.  ;)

Oct 10 2008
Sean Kelly <sean invisibleduck.org> writes:
Andrei Alexandrescu wrote:
Sergey Gromov wrote:
Fri, 10 Oct 2008 15:54:18 -0500,
Andrei Alexandrescu wrote:
Sean Kelly wrote:
It would be slower than the seeking option, but something like a
randomized mergesort would work as well.  If the program can buffer
k lines in a file containing n lines, then read the first k lines
into memory, shuffle them, and write them out to a temporary file.
Repeat until the input is exhausted.  Now randomly pick two of the
temporary files and randomly merge them.  Repeat until two temporary
files remain, then output the result of the final random merge to
the screen.

For small files (ie. where n<k) the file would be read, shuffled in
memory, and printed to the screen, assuming the proper checks were
in place.

file in three chunks: a, b, c. Then you pick at random b and c and
randomly merge them. The problem is, you make early the decision that
nothing in a will appear in the first two thirds of the result. So
the quality of randomness suffers. How would you address that?

After merging b and c you end up with a and bc.  Then you randomly
merge these two files and lines from a have all the chances to appear
anywhere within result.

When randomly merging, the probability of picking a line from a file
should be proportional to a number of lines left in that file.

How do you "randomly merge"? Describe the process.

while( a.hasMore || b.hasMore )
{
if( rand % 2 )
else
}
while( a.hasMore )
while( b.hasMore )

The downside to randomly choosing two files is that it's possible you
could end up always choosing a small and a large file, thus increasing
the chance that the large file will have a bunch of lines left over
which are essentially appended.

The easy way around this would be to maintain a list of files so only
equal-sized files are merged (similar to how mergesort works).  However,
I think a better way would be to use some sort of bias for the random
check above so that different-sized files are on equal footing.  Perhaps
write out the file with the first 4 bytes containing the number of lines
in that file and use that to construct the bias.  I'll leave those with
better math-fu than I to come up with a formula which would be fair.

Sean

Oct 10 2008
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Sean Kelly wrote:
Andrei Alexandrescu wrote:
Sergey Gromov wrote:
Fri, 10 Oct 2008 15:54:18 -0500,
Andrei Alexandrescu wrote:
Sean Kelly wrote:
It would be slower than the seeking option, but something like a
randomized mergesort would work as well.  If the program can buffer
k lines in a file containing n lines, then read the first k lines
into memory, shuffle them, and write them out to a temporary file.
Repeat until the input is exhausted.  Now randomly pick two of the
temporary files and randomly merge them.  Repeat until two
temporary files remain, then output the result of the final random
merge to the screen.

For small files (ie. where n<k) the file would be read, shuffled in
memory, and printed to the screen, assuming the proper checks were
in place.

file in three chunks: a, b, c. Then you pick at random b and c and
randomly merge them. The problem is, you make early the decision
that nothing in a will appear in the first two thirds of the result.
So the quality of randomness suffers. How would you address that?

After merging b and c you end up with a and bc.  Then you randomly
merge these two files and lines from a have all the chances to appear
anywhere within result.

When randomly merging, the probability of picking a line from a file
should be proportional to a number of lines left in that file.

How do you "randomly merge"? Describe the process.

while( a.hasMore || b.hasMore )
{
if( rand % 2 )
else
}
while( a.hasMore )
while( b.hasMore )

The downside to randomly choosing two files is that it's possible you
could end up always choosing a small and a large file, thus increasing
the chance that the large file will have a bunch of lines left over
which are essentially appended.

Yah, Sergey got me thinking too. What if you have a large file that
doesn't fit in memory by exactly one line?

Then I shuffle (n - 1) lines at random, and there remains the last line
to write. If I choose from either fragment with probability 0.5, the
last line will be with high probability among the first in the result!

The easy way around this would be to maintain a list of files so only
equal-sized files are merged (similar to how mergesort works).  However,
I think a better way would be to use some sort of bias for the random
check above so that different-sized files are on equal footing.  Perhaps
write out the file with the first 4 bytes containing the number of lines
in that file and use that to construct the bias.  I'll leave those with
better math-fu than I to come up with a formula which would be fair.

(In similar situations I've put the number of lines right in the name of
the temporary file. I kid you not! And it's O(1) too!)

It looks like any fragment should be chosen from with a probability
proportional to its length. The lingering question for me is whether
that probability needs to be updated, or can be fixed at the beginning
of merging. I think fixed doesn't quite work unless special measures are
taken at whenever a range is done.

Again many thanks to all participants for your illuminating insights.

Andrei

Oct 10 2008
Sergey Gromov <snake.scaly gmail.com> writes:
Fri, 10 Oct 2008 17:45:28 -0500,
Andrei Alexandrescu wrote:
Sean Kelly wrote:
Andrei Alexandrescu wrote:
Sergey Gromov wrote:
Fri, 10 Oct 2008 15:54:18 -0500,
Andrei Alexandrescu wrote:
Sean Kelly wrote:
It would be slower than the seeking option, but something like a
randomized mergesort would work as well.  If the program can buffer
k lines in a file containing n lines, then read the first k lines
into memory, shuffle them, and write them out to a temporary file.
Repeat until the input is exhausted.  Now randomly pick two of the
temporary files and randomly merge them.  Repeat until two
temporary files remain, then output the result of the final random
merge to the screen.

For small files (ie. where n<k) the file would be read, shuffled in
memory, and printed to the screen, assuming the proper checks were
in place.

file in three chunks: a, b, c. Then you pick at random b and c and
randomly merge them. The problem is, you make early the decision
that nothing in a will appear in the first two thirds of the result.
So the quality of randomness suffers. How would you address that?

After merging b and c you end up with a and bc.  Then you randomly
merge these two files and lines from a have all the chances to appear
anywhere within result.

When randomly merging, the probability of picking a line from a file
should be proportional to a number of lines left in that file.

How do you "randomly merge"? Describe the process.

while( a.hasMore || b.hasMore )
{
if( rand % 2 )
else
}
while( a.hasMore )
while( b.hasMore )

The downside to randomly choosing two files is that it's possible you
could end up always choosing a small and a large file, thus increasing
the chance that the large file will have a bunch of lines left over
which are essentially appended.

Yah, Sergey got me thinking too. What if you have a large file that
doesn't fit in memory by exactly one line?

Then I shuffle (n - 1) lines at random, and there remains the last line
to write. If I choose from either fragment with probability 0.5, the
last line will be with high probability among the first in the result!

The easy way around this would be to maintain a list of files so only
equal-sized files are merged (similar to how mergesort works).  However,
I think a better way would be to use some sort of bias for the random
check above so that different-sized files are on equal footing.  Perhaps
write out the file with the first 4 bytes containing the number of lines
in that file and use that to construct the bias.  I'll leave those with
better math-fu than I to come up with a formula which would be fair.

(In similar situations I've put the number of lines right in the name of
the temporary file. I kid you not! And it's O(1) too!)

It looks like any fragment should be chosen from with a probability
proportional to its length. The lingering question for me is whether
that probability needs to be updated, or can be fixed at the beginning
of merging. I think fixed doesn't quite work unless special measures are
taken at whenever a range is done.

Again many thanks to all participants for your illuminating insights.

Here's my little proof.  Paste this into wikipedia to see formulas.

Probability of a line from $a$ getting into the first line of
result:

$p_a^1=\frac{n_a}{n_a+n_b}$

Likewise for $b$:

$p_b^1=\frac{n_b}{n_a+n_b}$

Probability of a line from $a$ becoming a second line of the
output, $p_a^2$, is:

$p_a^2=p_a^2\Big|_{a_1} + p_a^2\Big|_{b_1}$

where $p_a^2\Big|_{a_1}$ and $p_a^2\Big|_{b_1}$
are probabilities of a line from $a$ getting into position
$2$ when the first line is from $a$ and from
$b$ respectively.

$p_a^2\Big|_{a_1} = \frac{n_a}{n_a+n_b}\cdot\frac{n_a-1}{n_a-1+n_b} = \frac{n_a(n_a-1)}{(n_a+n_b)(n_a+n_b-1)}$

$p_a^2\Big|_{b_1} = \frac{n_b}{n_a+n_b}\cdot\frac{n_a}{n_a+n_b-1} = \frac {n_a n_b}{(n_a+n_b)(n_a+n_b-1)}$

Therefore

$p_a^2 = \frac{n_a(n_a-1)}{(n_a+n_b)(n_a+n_b-1)}+\frac{n_a n_b}{(n_a+n_b) (n_a+n_b-1)} = \frac{n_a(n_a+n_b-1)}{(n_a+n_b)(n_a+n_b-1)} = \frac{n_a} {n_a+n_b}$

So at least $p_a^1=p_a^2$.  Induce anyone?

Oct 10 2008
Sean Kelly <sean invisibleduck.org> writes:
Andrei Alexandrescu wrote:
Sean Kelly wrote:
It would be slower than the seeking option, but something like a
randomized mergesort would work as well.  If the program can buffer k
lines in a file containing n lines, then read the first k lines into
memory, shuffle them, and write them out to a temporary file.  Repeat
until the input is exhausted.  Now randomly pick two of the temporary
files and randomly merge them.  Repeat until two temporary files
remain, then output the result of the final random merge to the screen.

For small files (ie. where n<k) the file would be read, shuffled in
memory, and printed to the screen, assuming the proper checks were in
place.

I think I found a problem with your solution. Consider you break the
file in three chunks: a, b, c. Then you pick at random b and c and
randomly merge them. The problem is, you make early the decision that
nothing in a will appear in the first two thirds of the result. So the
quality of randomness suffers. How would you address that?

When a is merged with (b&c) then its lines will be interleaved randomly
in the result.

Sean

Oct 10 2008
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Sean Kelly wrote:
Andrei Alexandrescu wrote:
Sean Kelly wrote:
It would be slower than the seeking option, but something like a
randomized mergesort would work as well.  If the program can buffer k
lines in a file containing n lines, then read the first k lines into
memory, shuffle them, and write them out to a temporary file.  Repeat
until the input is exhausted.  Now randomly pick two of the temporary
files and randomly merge them.  Repeat until two temporary files
remain, then output the result of the final random merge to the screen.

For small files (ie. where n<k) the file would be read, shuffled in
memory, and printed to the screen, assuming the proper checks were in
place.

I think I found a problem with your solution. Consider you break the
file in three chunks: a, b, c. Then you pick at random b and c and
randomly merge them. The problem is, you make early the decision that
nothing in a will appear in the first two thirds of the result. So the
quality of randomness suffers. How would you address that?

When a is merged with (b&c) then its lines will be interleaved randomly
in the result.

I think that works with Sergey's appropriate crooking of the dice. For
the record, my solution involved generating k shuffled sub-files, and
then roll a fair k-sided dice and write one line in the chosen file to
the output, until all files are exhausted. Sergey showed that my
solution is wrong unless it so happens the last fragment is equal to all
others. Thanks!

Well are we ready for the next puzzle, or bored?

Andrei

Oct 10 2008
Russell Lewis <webmaster villagersonline.com> writes:
I've read most of the responses (not all) and haven't yet seen a
duplicate of my algorithm, so here it is.  You can debate whether the
cost of opening many little files is as bad as lseek or not...I don't know.

BEGIN CODE

void main()
{
CreateAnEmptyTmpDirectoryAndChdirToIt();

while(!feof(stdin))
{
char[] name = Random8CharacterFilename();

if(!file_exists(name))
else
{
if(CoinFlip())
else
{
rename(name, "junk");
}

// shuffle "junk" to some non-duplicate name.  chains of
// renames are allowed so as to prevent any biasing of
// the odds towards lines earlier in the file.
name = Random8CharacterFilename();
while(file_exists(name))
{
if(CoinFlip())
{
rename(name, "tmp");
rename("junk", name);
rename("tmp", "junk")
}
name = Random8CharacterFilename();
}
}
}

char[][] names = GetSortedFilenames();
foreach(name; names)
{
PrintFileContents(name);
}

DestroyTmpDir();
}

END CODE

Andrei Alexandrescu wrote:
The high traffic enjoyed by "random k-sample of a file" confirms that
plenty of people around here have idle cycles ready to be spent on fun

In that vein, here's another problem. Say you want to randomly shuffle
lines in a stream. You don't know the size beforehand, and one pass is
preferable. The stream can be larger than the working memory, but not an
unbounded amount of times larger. Also lines in the stream can be
unbounded, but it is guaranteed that at least a nonzero fraction of the
file fits in working memory.

You can use temporary files, but of course minimizing their total size
is recommended. Speed is of course important. Draft your solution and
explain why you think it's correct and advantageous.

In case you hate random stuff, just wait; the next problem won't have
any random element in it :o).

Andrei


Oct 13 2008