;; random-line : (U string path) -> string ;; ;; Returns a random line from the given file, using only a single pass through the file. ;; Each line has an equal chance of being chosen. (define (random-line/stdin) (let reader ([chance 1] ; chance that a line becomes the new result [result ""]) ; current result if there are no more lines (cond [(eof-object? (peek-char)) result] ; end of file, return current result [(zero? (random chance)) ; this line is the new result (reader (add1 chance) (read-line (current-input-port) 'any))] ; continue [else (read-line (current-input-port) 'any) ; discard a line (reader (add1 chance) result)]))) ; continue (define (random-line filename) (with-input-from-file filename random-line/stdin))
resultin the implementation above. This technique can be used to sample from any data structure that can be sequentially iterated. For example, the same technique could be used to sample an element from a tree using only a single pass through the tree. It is also possible to sample from a non-uniform distribution, though the details are beyond the scope of this article.
with-input-from-file, making it more robust against errors. It is also worth noting that reserviour sampling can be used for many other situations. For example, I've used it draw random sub-trees from a tree. I was first shown this trick by OlegK. -- NoelWelsh - 11 Dec 2006 Thanks for your comments. I'm a little busy due to exams tomorrow, but I'll try to implement the rest of your suggestions soon. UPDATE: I used
with-input-from-file, as requested. GordonWeakliem - 13 Aug 2004 -- BrianJ - 11 Dec 2006