[kw-pm] Last Wednesday's meeting

[Abram Hindle]

On the topic of twitter I discussed tircd a tiny bit:

http://github.com/abramhindle/tircd-plus-search/tree/master
http://code.google.com/p/tircd/

We did a golf challenge from:
http://kw.pm.org/wiki/index.cgi?GolfChallenge

    * Choose 1 uniformly randomly

Write a perl script to select 1 element from a stream of unknown length
uniformly randomly. The algorithm usually is read an element in, choose
a number between 0 and 1, if it is less than 1/n then keep that new
element, otherwise keep your old one. So first element is 1/1 to keep,
second element is 1/2 to keep, third element is 1/3 to keep. Via
induction you can work it out that this algorithm is uniformly random.

^^ I "proved" this on the board via hand waving.


Here's my awk/bash version (bash seeds awk because gawk is bad at
seeding itself)
#!/bin/bash
awk "BEGIN {srand($RANDOM + $RANDOM)} {c = (rand() < (1.0 / FNR))?\$0:c}
END { print c }" $*

Daniel wrote a tiny perl version (37 chars?) and max wrote a relatively
small (87 chars?) python version.

If Daniel or Max could share their code with the list that'd be great.

abram

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 260 bytes
Desc: OpenPGP digital signature
URL: <http://mail.pm.org/pipermail/kw-pm/attachments/20090618/e093350a/attachment.bin>