Dimsum is like head or tail, but pulls randomly from the entire file or stream

Post by neilk » Mon, Nov 26, 2012, 10:27 PM UTC

andrewcooke wrote: post #20

neilk wrote: post #16

This doesn't come with an elaborate test suite, but it does pretty much everything that does in a few dozen lines of Perl. https://github.com/neilk/misc/blob/master/randline I've had this script (or versions of it) around for more than a decade. I didn't know the technique had a name.

it was an example in the original camel book. [edit: i was going to delete this, but since you replied i'll leave it - it does appear (too?) in the camel book, on p 246 of my copy, but like you say, it's for a single line. hadn't opened that book in years, took me some time to find it...]

Post by philsnow » Mon, Nov 26, 2012, 11:39 PM UTC

minimax wrote: post #14

cgs1019 wrote: post #13

Earlier quoted context omitted.

Maybe I'm overlooking something obvious but wouldn't piping through awk 'rand()<.1{print}' give a decent streaming random sample of roughly 10% of input?

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).

Post by snoble » Tue, Nov 27, 2012, 3:55 AM UTC

neilk wrote: post #16

This doesn't come with an elaborate test suite, but it does pretty much everything that does in a few dozen lines of Perl. https://github.com/neilk/misc/blob/master/randline I've had this script (or versions of it) around for more than a decade. I didn't know the technique had a name.

Post by malcook » Tue, Nov 27, 2012, 6:25 PM UTC

snoble wrote: post #24

malcook wrote: post #22

Earlier quoted context omitted.

did you try "yes | dimsum -n 1"? In my hands, `top` shows resident memory increasing steadily too.... It is perhaps more instructive to compare output from, for example seq 1 1000000 | valgrind --time-unit=B --pages-as-heap=yes --trace-children=yes --tool=massif --massif-out-file=massif.dimsum.100000.out.%p dimsum -n 1 with seq 1 1000000 | valgrind --time-unit=B --pages-as-heap=yes --trace-children=yes --tool=massif…

sigh, memory leak. It's fixed in github. When camilo is around I'll get him to update the gem

Post by taltman1 » Tue, Nov 27, 2012, 11:51 PM UTC

cgs1019 wrote: post #13

andrewcooke wrote: post #2

uses reservoir sampling - http://en.wikipedia.org/wiki/Reservoir_sampling (so it presumably consumes the entire stream before giving any results; any alternative i can think of would not be "really random" unless you knew the length of the stream in advance).

Maybe I'm overlooking something obvious but wouldn't piping through awk 'rand()<.1{print}' give a decent streaming random sample of roughly 10% of input?

  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 && (current_random_int = random_int(NR))