random line from file

When you want a random line from a file, and don't know how many lines are in the file to start with, there's a neat trick to save the memory consumption of:

  proc random_line {chan} {
    while {![eof $chan]} {
      lappend l [gets $chan]
    }
    lindex $l [expr {rand()*[llength $l]}]
  }

I'm not sure who this algorithm comes from, and I hesitate to publish it without attribution -- perhaps it was Oleg Kiselyov or maybe even Knuth. I first learned of it as "choosing a random element from a linked list in a single traversal", so tend to think of it coming from a Schemer ... if anyone can find an authoritative reference, please insert it here!

Note that this routine will cost you additional calls to random .. but the goal is to save memory, so we can deal with that in this case.

  proc random_line {chan} {
    set i 0
    while {![eof $chan]} {
      set l [gets $chan]
      incr i
      if {rand()<1./$i} {
        set result $l
      }
    }
    set result
  }

.. the curious reader is encouraged to demonstrate to him/herself that all the elements of the input will be chosen with equal probability. Enjoy!