5 ms·
Dimsum is like head or tail, but pulls randomly from the entire file or stream
- neilk 14y agoThis 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 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.
- andrewcooke 14y agoit 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...]
- neilk 14y agoI believe it was an example in the Perl Cookbook, but for picking a single line only. (Ancient UseNet thread: http://bit.ly/Thd4eE http://bit.ly/Thd4eE)
- snoble 14y agothe code isn't special. but it's easy for anyone to install and use
- andrewcooke 14y agouses reservoir sampling -http://en.wikipedia.org/wiki/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).
- avibryant 14y agoYep, 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.
- deleted 14y ago[deleted]
- cgs1019 14y agoThis 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.
- wodow 14y agoIt could accept another signal (e.g. SIGUSR1) and have this clearly documented.
- neilk 14y agoI 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
- snoble 14y agothe magic of reservoir sampling is the memory footprint is the size of the output while being completely random. In this particular implementation the order of the output is slightly biased but each row has an equal chance of being in the output.
- snoble 14y agobut yes. it has to wait until the stream is done before producing any output.
- nullc 14y agouhhh. You mean like shuf -n NNNN ?
- bo1024 14y agoI wonder if the implementation of shuf would handle very large input efficiently? Reservoir sampling wouldn't need to keep the whole input in memory, which could be an advantage. But I don't know how shuf works.
- teraflop 14y agoDoesn'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.
- malcook 14y agodid 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 --massif-out-file=massif.shuf.100000.out.%p shuf -n 1 in my hands, shuf is faster and uses less memory for this task. How about you?
- patrick_grant 14y agoI 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