6
\$\begingroup\$

I wrote a program to take a list of letters and from every permutation of them and check that against the dictionary and print out valid words. The constraints are that there is a control letter which means that letter must be in the word, and you can't repeat any letters.

Everything works, but the running time is way too long. I'm hoping to get some feedback on how to cut down my running time in O-notation. Also, if you know the running times of the built in function, that would be great. Also, comment if my code style is not what it should be for Python.

import itertools
from multiprocessing import Process, Manager

dictionary_file = '/usr/share/dict/words'
letter_list = ['t','b','a','n','e','a','c','r','o']
control_letter = 'e'

manager = Manager()
word_list = manager.list()

def new_combination(i, dictionary):
    comb_list = itertools.permutations(letter_list,i)
    for item in comb_list:
        item = ''.join(item)
        if(item in dictionary):
            word_list.append(item)
    return


def make_dictionary():
    my_list = []
    dicts = open(dictionary_file).readlines()
    for word in dicts:
        if control_letter in word:
            if(len(word) >3 and len(word)<10):
                word = word.strip('\n')
                my_list.append(word)
    return my_list

def main():
    dictionary = make_dictionary()
    all_processes = []
    for j in range(9,10):
        new_combo = Process(target = new_combination, args = (j,dictionary,))
        new_combo.start()
        all_processes.append(new_combo)
    while(all_processes):
        for proc in all_processes:
            if not proc.is_alive():
                proc.join()
        all_processes = [proc for proc in all_processes if proc.is_alive()]
        if(len(all_processes) == 0):
            all_processes = None

    print list(set(word_list))

if __name__ == '__main__':
    main()
\$\endgroup\$
  • \$\begingroup\$ This is a good question, thank you for taking the time to form it so that we can help show you the proper coding styles and techniques. We all look forward to seeing more of your posts! \$\endgroup\$ – Malachi Jul 8 '14 at 14:32
5
\$\begingroup\$
import itertools
from multiprocessing import Process, Manager

dictionary_file = '/usr/share/dict/words'
letter_list = ['t','b','a','n','e','a','c','r','o']
control_letter = 'e'

By convention, global constant should be named in ALL_CAPS

manager = Manager()
word_list = manager.list()

def new_combination(i, dictionary):
    comb_list = itertools.permutations(letter_list,i)
    for item in comb_list:
        item = ''.join(item)
        if(item in dictionary):

You don't need the parens. Also, dictionary in your code is a list. Checking whether an item is in a list is rather slow, use a set for fast checking.

            word_list.append(item)

Having a bunch of different processes constantly adding onto a single list, performance will be decreased. You are probably better off adding onto a seperate list and then using extend to combine them at the end.

    return

There is no point in an empty return at the end of a function

def make_dictionary():

I'd call this read_dictionary, since you aren't really making the dictionary

    my_list = []

Name variables for what they are for, not their types

    dicts = open(dictionary_file).readlines()
    for word in dicts:

Actually, you could just do for word in open(dictionary_file) for the same effect

        if control_letter in word:
            if(len(word) >3 and len(word)<10):
                word = word.strip('\n')

I recommend stripping before checking lengths, just to make it easier to follow what's going on

                my_list.append(word)
    return my_list

def main():
    dictionary = make_dictionary()
    all_processes = []
    for j in range(9,10):
        new_combo = Process(target = new_combination, args = (j,dictionary,))

You don't need that last comma

        new_combo.start()
        all_processes.append(new_combo)
    while(all_processes):

Parens unneeded

        for proc in all_processes:
            if not proc.is_alive():
                proc.join()
        all_processes = [proc for proc in all_processes if proc.is_alive()]

What happens if a process finishes between the last two lines? You'll never call proc.join() on it.

        if(len(all_processes) == 0):
            all_processes = None

an empty list is already considered false, so there is no point in this.

Actually, there is no reason for most of this loop. All you need is

for process in all_processes:
    process.join()

It'll take care of waiting for all the processes to finish. It'll also be faster since it won't busy loop.

    print list(set(word_list))

if __name__ == '__main__':
    main()

I've given a few suggestions for speed along the way. But what you should really do is invert the problem. Don't look at every combination of letters to see if its a word. Look at each word in the dictionary and see if you can form it out of your letters. That should be faster because there are many fewer words in the dictionary then possible combination of letters.

\$\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.