I believe it was an example in the Perl Cookbook, but for picking a single line only. (Ancient UseNet thread: http://bit.ly/Thd4eE)

but yes. it has to wait until the stream is done before producing any output.

This breaks ctl-c in my opinion. When I ctl-c I want shit to stop, not dump (potentially large quantities of) output into my terminal.

Reservoir sampling allows you to return a specific number of samples regardless of the size of the input rather than a specific fraction of samples (which is what your awk script does).

As minimax stated, your awk code won't provide exactly k samples. Here's a bit of awk code that implements reservoir sampling (apologies in advance for any bugs) and prints the current sample to stdout, without needing to first process the entire stream. It simply prints the set of samples to stdout whenever the sample updates, with sets of samples separated by a distinct string. It is called as follows (of course, replace dmesg with any stream of your choosing):

  dmesg | gawk -f reservoir-sample.awk k=5 record_separator='==='


  #!/usr/bin/gawk -f

  ### reservoir-sample.awk
  ###
  ### Sample k random lines from a stream, without knowing the size of the stream.
  ###
  ### (Tomer Altman)

  ### Parameters: (set from command-line)
  ##
  ## k: number of lines to sample
  ## record_separator: string used to separate iterations of the sample in stdout.

  ## Define a function for returning a number between 1 and n:
  function random_int (n) { return 1 + int(rand() * n) }

  ## Initialize the PRNG seed:
  BEGIN { srand() }

  ## For the first k lines, initialize the sample array:

  NR <= k { sample[NR] = $0 }

  ## If we've initialized the sample array, and we pick an integer between one and the current record number that is less than or equal to k, update the sample array and print it to stdout:
  NR > k && (current_random_int = random_int(NR)) <= k {

    sample[current_random_int] = $0

    for (i in sample) print sample[i]
    
    print (record_separator != "") ? record_separator : "--"
  }

Doesn't look like it. I just tried running "yes | shuf -n 1" (using the latest version of GNU coreutils, 8.20) and its memory consumption increased steadily until I killed it.

It seems like this would be a really useful improvement, and I'm surprised that it doesn't already seem to have been requested on the coreutils issue tracker.

sort -R isn't actually a random permutation or shuffle like one would ordinarily expect from a 'random' output: if you read the man page very carefully, you'll notice it only speaks of 'random hash' which means that 2 lines which are identical (quite possible and common) will be hashed to the same value and placed consecutively in the output.

(This bit me once. Filed a bug about maybe clarifying the man page, but nope, apparently we're all supposed to recognize instantly the implication of a random hash.)