You don't need to read the whole file in at once nor use random.choice() if you use the reservoir-sampling algorithm. (This is the algorithm used in fortune on Unix!)
The algorithm is based on the idea that you select later samples based on a decreasing probability.
#!/usr/bin/python
import random
from itertools import ifilter
_MAX_LEN = 6
def goalword():
with open("words.txt") as fd:
for linenum, line in enumerate(ifilter(lambda x: len(x)-1 > _MAX_LEN, fd)):
if random.uniform(0, linenum+1) <= 1:
ret = line
return ret.strip()
print goalword()
I based this on the Perl implementation from Perl Faq #5, which I'm more familiar with:
srand;
rand($.) < 1 && ($line = $_) while <>;
Since in Perl 0 <= rand(X) < X, whereas in Python, 0 <= random(0, X) <= X "depending on floating-point rounding in the equation a + (b-a) * random()", I've made my comparison inclusive (<=) to make sure the first line is always true.
If you look at Wikipedia's sample implementation, they just use randint(), so here is a modification to do that:
#!/usr/bin/python
from itertools import ifilter
from random import randint
_MAX_LEN = 6
def goalword():
with open("words.txt") as fd:
for linenum, line in enumerate(ifilter(lambda x: len(x)-1 > _MAX_LEN, fd)):
if randint(0, linenum) < 1:
ret = line
return ret.strip()
print goalword()
Again, I make sure the first randint() is always true, otherwise a single line file might occasionally get no result.
For a reduce() implementation,
def goalword():
with open("words.txt") as fd:
return reduce(lambda old, (i, new): new if randint(0, i) < 1 else old,
enumerate(ifilter(lambda x: len(x)-1 > _MAX_LEN, fd))).strip()
print goalword()
Turns out, though, that reduce() isn't necessarily faster:
# for loop
print(timeit.timeit("goalword0()", setup="from __main__ import goalword0; import random; random.seed(42)", number=100, timer=time.clock))
# reduce
print(timeit.timeit("goalword1()", setup="from __main__ import goalword1; import random; random.seed(42)", number=100, timer=time.clock))
45.05 # for loop
49.17 # reduce
Note:
If you're picking more than one word from each execution, reading the whole file into a list will likely be more time efficient.
If you're just picking one word, however, this implementation is the most time and space efficient since you read the whole file once, but only retain one word in memory.
"In theory there is no difference between theory and practice. In practice there is."
I've tested this against a read-the-whole-file implementation:
def goalword():
with open("words.txt") as fd:
words = filter(lambda x: len(x)-1 > _MAX_LEN, fd)
return random.choice(words).strip()
It is significantly faster:
45.04 # For loop
7.14 # random.choice()
My word list is not insignificant:
$ curl -O https://raw.githubusercontent.com/dwyl/english-words/master/words.txt
$ wc -l words.txt
466544 words.txt
My guess this is due to the overhead of the extra python opcode operations in the for loop vs filter being implemented in native C. i.e., we stay out of the interpreter for more of the work in the random.choice() implementation.
So, while not necessarily always faster, if you need to avoid loading the whole list into memory, reservoir sampling is what you want.
