Faster way to do this?

[Freddie]

Paul Rubin <http://phr.cx@NOSPAM.invalid> wrote:
> Well, if you only want to run the program on one word, generating that
> list is probably slower than linearly searching the dictionary.  If
> you want to run it on lots of words, then yes, precomputation can help
> you.

'Skip Montanaro' sent me an e-mail with a way (I think) of generating the 
list of words, and it's actually a lot faster, for _small input lengths_. As 
the length of the input increases, my version's run time seems to increase 
fairly linearly, while Skip's increases quite scarily. Some timings, mine all 
using my method2():

4 letters: 'hell'
mine - found 2 words in 0.26s
Skip - found 2 words in 0.01 seconds

5 letters: 'hello'
mine - found 6 words in 0.39s
Skip - found 6 words in 0.02 seconds

6 letters: 'hellos'
mine - found 17 words in 0.62s
Skip - found 17 words in 0.09 seconds

7 letters: 'hellosi'
mine - found 34 words in 0.93s
Skip - found 34 words in 0.56 seconds

8 letters: 'hellosig'
mine - found 50 words in 1.22s
Skip - found 50 words in 4.21 seconds

8 letters: 'hellosigz'
mine - found 51 words in 1.49s
Skip - found 51 words in 36.71 seconds


BEGIN Skip code
---------------
start = time.time()

dictionary = {}
wf = open(WORD_FILE, 'r')
for line in wf:
    dictionary[line.strip()] = True
print "loaded %d words into dictionary in %.2f seconds" % (len(dictionary),
                                                           time.time()-start)

def findwords(dictionary, letters, prefix="", seen={}):
	for i in range(len(letters)):
		newprefix = prefix+letters[i]
		if newprefix in dictionary and newprefix not in seen:
			print newprefix
			seen[newprefix] = True
		findwords(dictionary, letters[0:i]+letters[i+1:], newprefix, seen)

if __name__ == "__main__":
	start = time.time()
	findwords(dictionary, sys.argv[1].lower())
	print "found matches in %.2f seconds" % (time.time()-start)


--------------------------------------------------------------
Remove the z's from my e-mail address if you really want to