15
\$\begingroup\$

I am trying to randomly pick a large word (7 letters or more in length) from a large text file of words.

I know that there has to be a better and more efficient way to do this.

def goalWord():
    with open("words.txt","r") as allWords:
        wordList = allWords.read()
        wordList = wordList.split()
        bigWords = []
        for word in wordList:
            if len(word) > 6:
                bigWords.append(word.upper())
        return random.choice(bigWords)

Here is the sample input:

A
a
aa
aal
aalii
aam
Aani
aardvark
aardwolf
Aaron
Aaronic
Aaronical
Aaronite
Aaronitic
Aaru
Ab
aba
Ababdeh
Ababua
abac
abaca
abacate
abacay

Output would be a random word from words.txt that is greater than 6 characters in length.

\$\endgroup\$
15
\$\begingroup\$

Comments

  • Python functions are written in snake_case.
  • You could use function parameters for word length and filename.
  • You could use iterators and generators to avoid loading the whole file into memory.
  • If you read the file line by line, you need to take care with the trailing newline character: len("test\n") is 5.

Refactoring

Here's a way to rewrite your function. Thanks to a generator, the script only loops once over every line:

import random


def goal_word(min_length=7, filename="words.txt"):
    with open(filename) as wordbook:
        words = (line.rstrip('\n') for line in wordbook)
        large_words = [word for word in words if len(word) >= min_length]
    return random.choice(large_words)

print(goal_word(7))
# evening
print(goal_word(15))
# circumnavigations

Optimization

@etchesketch commented that rstrip is called on every line even though it's only needed for one word. Here's a variation:

import random


def goal_word(min_length=7, filename="words.txt"):
    min_line_length = min_length + 1
    with open(filename) as wordbook:
        large_words = [line for line in wordbook if len(line) >= min_line_length]
    return random.choice(large_words).rstrip('\n')

print(goal_word(7))
# jauntily
print(goal_word(15))
# fundamentalists

On a dictionary of English words (/usr/share/dict/american-english), this function is 3 times faster than the previous one.

Exception handling

In the above examples, goal_word(30) fails with IndexError: Cannot choose from an empty sequence. There's no indication that the desired length is too long.

Before calling random.choice, the script could simply check that large_words isn't empty:

import random


def goal_word(min_length=7, filename="words.txt"):
    min_line_length = min_length + 1
    with open(filename) as wordbook:
        large_words = [line for line in wordbook if len(line) >= min_line_length]
    if large_words:
        return random.choice(large_words).rstrip('\n')
    else:
        raise ValueError("No word found with at least %s characters." % min_length)


print(goal_word(7))
# jauntily
print(goal_word(15))
# insurrectionist's
print(goal_word(30))
# ValueError: No word found with at least 30 characters.
\$\endgroup\$
  • 1
    \$\begingroup\$ Instead of looping twice it might make more sense to increment min_length by one to offset the \n and then do the rstrip() before returning. That way you will only loop through the words once and you won't waste time stripping out new lines from words that will never be returned. \$\endgroup\$ – etchesketch Dec 28 '17 at 20:06
  • \$\begingroup\$ @etchesketch theres only one loop here, thanks to generators. \$\endgroup\$ – Eric Duminil Dec 28 '17 at 20:08
  • 1
    \$\begingroup\$ Generators still confuse me--what is the advantage of using one here, given that you're intending to exhaust the set either way? \$\endgroup\$ – thumbtackthief Dec 28 '17 at 20:32
  • \$\begingroup\$ @thumbtackthief They can indeed be confusing. In this case, the generator is used to loop only once over every line and to avoid creating an extra list (words). \$\endgroup\$ – Eric Duminil Dec 28 '17 at 20:56
  • 5
    \$\begingroup\$ @EricDuminil it's not a big change but just doing min_length += 1 before the with statement, removing the line in wordbook command, and then adding .rstrip('\n') on the return should do it. \$\endgroup\$ – etchesketch Dec 28 '17 at 21:45
12
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ A small note: it should be randint(0, linenum) < 1 in the last snippet, so that it goes like randint(0, 0) for the first line, randint(0, 1) for the second one and so on. \$\endgroup\$ – kraskevich Dec 28 '17 at 21:17
  • \$\begingroup\$ @kraskevich Right -- I mixed myself up because $. in Perl starts at 1, but Python's enumerate() starts at 0. \$\endgroup\$ – rrauenza Dec 29 '17 at 4:58
5
\$\begingroup\$

If you use Python 3:

def pickBigWord(filename):
    # By default python open files in read mode
    # no need for "r"
    with open(filename) as handler:
        # handler is an iterator, let's use it
        chosen_words = [word for word in handler if len(word) >  6]
        return random.choice(chosen_words)

pickBigWord("words.txt")

In such a way you could avoid loading all the words in memory. Also notice that it could be reduced to one line in a (arguable) less readable form:

print(random.choice([word for word in open("words.txt") if len(word) > 6]))

Nota bene each line ends with a new line character (i.e. \n) so consider adding 1 to your condition or writing the list comprehension like this:

[word[:-1] for word in open("words.txt") if len(word[:-1]) > 6]
\$\endgroup\$
  • 1
    \$\begingroup\$ The first code is wrong, it also selects 6-letter words and has an IndentationError. The last code does the same operation twice and creates a useless string just to get len - 1. \$\endgroup\$ – Eric Duminil Dec 28 '17 at 21:30
2
\$\begingroup\$

I tested the following loop strategy by generating a list of numbers between 0 and 1, and then randomly selecting a number from the list greater than a threshold. I found that as the threshold goes up, the time for the list comprehension strategy goes down, while the time for the loop strategy goes up. The cross-over tended to be at around threshold = .8 . So this suggests that if more than 20% of your word are "long", the loop strategy is faster. However, I didn't exactly replicate your use case in my tests, so the cross-over is likely different. Also, if you're going to sample repeatedly, it's probably faster to calculate the list comprehension once and then sample from it repeatedly.

while True:
     x = random.choice(wordList)
     if len(x) > 6:
         return(x)

Also note that if none of the words are "long", then the loop method will go into an infinite loop, while the other methods will return an error.

\$\endgroup\$
  • \$\begingroup\$ @rrauenza Edited \$\endgroup\$ – Acccumulation Dec 29 '17 at 15:18
2
\$\begingroup\$

a MUCH more efficient solution for VERY large files (at a cost of a bias to some words) would be as follows:

  1. Open the file.
  2. Seek to a random location in the file
  3. Discard the first "line", because you will probably start in the middle of a word.
  4. Find the first word from there on, which meets your criteria
  5. If you get to the end, seek to the start, and continue on
  6. If you get back to where you started, fail

How much randomness you lose depends on how many words there are, how many words do and do not match your criteria, and if they are grouped. For example, if your criteria is 6 letters, and your file contains 10,000 words of 5 letters each, and 2 of 6 letters, and the 6-letter ones are together, you will almost certainly get the first of those 2.

As mentioned before, there will be a bias - words immediately after a long list of short words will have a greater chance. A quick approximation over a wordlist I have here, indicates that "Baal's" has about 10 times the chance of being picked, compared to "abating", because none of the 66 characters before this word are the start of a 6 letter word. The happens frequently for the first 6-letter words starting with a new letter ('B' in this case).

This bias will get worse and worse if fewer and fewer words match your criteria. For 9 letter words, "wagonner's" is 38 times as likely as the minimum, and "Andrianampoinimerina's" is 24,000 times more likely than "electroencephalographs", when choosing a 22 letter (or greater) word.

You could alleviate this by various means - e.g. pick a random address; if you don't get a newline, followed by a word meeting the criteria IMMEDIATELY, pick another random address. Of course, if you're looking for a 22-letter word, this method will be VERY SLOW!

\$\endgroup\$
1
\$\begingroup\$

Depending on how often you do this, and how big the file is, it may be worth creating an index (probably a file).

Decide on a block size, (e.g. 1mb), and read the file from beginning to end; build up a dictionary where the key is your criteria (if there is more than one), and the value is a list of how many matches there are, before the END of that block (i.e. a running total). Words spanning blocks belong to the block before it.

When you want to pick a random entry, the steps would be:

  1. Find the dictionary for the criteria you want to use (if you have multiple criteria).
  2. Pick a number from >0, <=(last value in the list)
  3. Find the block number: The index of the last entry in the list which is < the number you picked.
  4. Seek to that block - seek(blocksize*index), discard the first line (partial word).
  5. subtract the lookup for this block from the number you picked
  6. While the counter>0, Read through the file; decrease the counter for each match
  7. When your counter hits 0, the last line you read was the one you want.

For example:

  1. index["6+"] = [0,0,3,4,7,9]. They are a running total, so will always increase. This means the first two blocks don't have any matches, the second has 3, the third has 1 more, and so forth. There are 9 matches in the entire file.
  2. I pick a random number from 1-9 (inclusive). I pick 8 (i.e the 8th word).
  3. The last entry < than my pick (8) is index["6+"][4] (which is 7). The number I want is somewhere in block 4.
  4. I seek to (blocksize*4), and read one (partial) line, which is really part of the previous block.
  5. The number of words I've already skipped is index["6+"][4], (which is 7). I subtract that from my picked random number, leaving 1.
  6. I read the file, counting down for each match.
  7. The match that makes my counter go to 0 (the first one in this case) is the one I want.

This way, you only have to read the index, plus (on average) half a block. Bigger blocks = smaller index, but more for the final search. Smaller blocks = bigger index, but you have less data to search through sequentially. Make sure the word list hasn't been changed since you made the index.

\$\endgroup\$
1
\$\begingroup\$

2 more options to consider. I suspect these aren't relevant here (though nothing in your post rules it out), but they are worth keeping in mind.

Put your data in a database, have all the work done for you. Databases are REALLY GOOD at what they do. If you think a database has too much overhead, consider sqlite - tiny footprint, all the advantages of a database, and if you want to move to a different database later, it's easy.

If you're always looking for 7 letter words, extract those into a file. Then all the words you don't want, don't have to be processed. Optionally, you can make your target file fixed length records (at least the size of the longest word!). For example, if your longest word is 23 bytes, pad all your words out to 23 bytes with spaces. Adding a new line (optional) would increase this to 24 characters. Then, if your file is 2,400 bytes long, you know you have 100 records; pick a number from 0 to 99, seek to that position * 24, and read your word. Don't forget to trim(), and beware of the difference between letters and bytes in multi-byte encoding!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.