Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

blog.noblemail.ca

Post reply on HN
Print view View original

11–20 of 31 posts

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

#11

Post by cgs1019 »

avibryant wrote: post #3
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).

Yep, though a feature request I've put in is to respond to a ctl-c by producing the results from the stream so far... that way if it's taking a while on a large file you can interrupt and still get something useful.

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.

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

#12

Post by gwern »

nburger wrote: post #8
nullc wrote: post #6

uhhh. You mean like shuf -n NNNN ?

or "sort -R"...

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

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

#13

Post by cgs1019 »

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?

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

#14

Post by minimax »

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?

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

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

#15

Post by wodow »

cgs1019 wrote: post #11
avibryant wrote: post #3

Earlier quoted context omitted.

Yep, though a feature request I've put in is to respond to a ctl-c by producing the results from the stream so far... that way if it's taking a while on a large file you can interrupt and still get something useful.

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.

It could accept another signal (e.g. SIGUSR1) and have this clearly documented.

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

#16

Post by neilk »

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.

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

#18

Post by neilk »

wodow wrote: post #15
cgs1019 wrote: post #11

Earlier quoted context omitted.

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.

It could accept another signal (e.g. SIGUSR1) and have this clearly documented.

I just added the SIGUSR1 feature to my hacky perl script (see my other comment).

e.g.

    $ (while true; do cat /usr/share/dict/words; done;) | ./randline 3 &
    [2] 93937
    
    $ kill -s SIGUSR1 93937
    declinograph
    brotheler
    woolpack

    $ kill -s SIGUSR1 93937
    lustrify
    brotheler
    bromophenol

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

#19

Post by snoble »

patrick_grant wrote: post #17

I really don't like how this behaves for populating the array initially, and how it behaves for small inputs... $ seq 15 | dimsum -n 10 14 12 3 4 5 6 7 8 9 10

yup, the order is biased. definitely worth a couple of minutes to fix that

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

#20

Post by andrewcooke »

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 reply on HN