3
\$\begingroup\$

I was redirected from StackOverflow to your community in hope to get some help and improve my script.

The script receives letters as input and generates possible words, then extracts readable words from comparing my list items with file containing English words.

For example when I enter as input : eys

this will generate a list like:

["esy", "eys", "sey", "sye", "yes", "yse"] and return the correct readable word "yes" as a final result.

The problem is when the length of input is greater than 8 characters it takes much time and I want to use Threading or Multiprocessing to reduce the latency.

My script

'''Create script that generate readable english words from given letters'''

from math import factorial
from itertools import permutations
from time import time, ctime
from threading import Thread
import multiprocessing as mp

class GetReadableWords:

    def __init__(self, letters):
        self.letters = letters

    def prob_words(self):
        
        self.comb = factorial(len(self.letters))
        print('Nomber of combinitions that we have is : ', self.comb)

        self.prob = [''.join(ltr) for ltr in permutations(self.letters)]
        return self.prob

    def chek_word(self):

        result = []

        for word in set(self.prob_words()):

            with open('corncob_lowercase.txt', 'r') as f:

                for line in f.readlines():
                    line = line.rstrip()

                    if word == line:
                        result.append(word)

                    else:
                        continue

                f.close()

        return result

    '''def run(self):
        with mp.Pool() as pool:
            pool.map(self.chek_word(), self.prob, chunksize=1)'''


if __name__ == "__main__":

    user_input = input('Enter your random characters : ')
    
    sart_time = time()
    print("starting time at : ", ctime(sart_time).split(' ')[3])

    c = GetReadableWords(user_input)
'''
    threads = []
    for word in c.prob_words():
        p = mp.Process(target=c.chek_word(), args=(word,))
        threads.append(p)
        p.start()

    for job in jobs:
        job.join()
'''
    #print(c.run())
    print(c.chek_word())
    end_time = time()
    print("ending time at : ", ctime(end_time).split(' ')[3])

    elaps_t = (end_time - sart_time)
    print("time taken is : %.2f sec" % elaps_t)
\$\endgroup\$
3
  • \$\begingroup\$ Welcome to Code Review! We often see Stack Overflow users recommend posting to Code Review, but that may or may not be appropriate advice. I see that you have some multiprocessing code here — but why is it commented out? Does your multiprocessing code work or not? \$\endgroup\$ May 17 at 0:57
  • \$\begingroup\$ On further thought, it doesn't matter that you have included some commented-out multiprocessing code, and it doesn't matter whether it works or not. The real problem is that your algorithm (generating all permutations, then checking whether each permutation constitutes a valid word) is horribly inefficient. So, Code Review is indeed the right place to get advice. \$\endgroup\$ May 17 at 1:01
  • \$\begingroup\$ thanks for your attention @200_success , I left that commented-out multiprocessing code cuz it results errors, and keep in mind that I'm beginner in python :)' \$\endgroup\$
    – Sp3kTr0
    May 17 at 1:49

2 Answers 2

2
\$\begingroup\$

Algorithm

The problem here is that your algorithm isn't scalable. For any given n-letter word, prob_words() generates n! candidate words. That's 40320 candidates for an 8-letter input.

To compound your performance problem, check_word() opens and scans the word list file once for each candidate word. Since the entire word list should fit quite comfortably memory on any general-purpose computer these days, you should read the word list just once.

So, forget about multithreading or multiprocessing. Work smarter, not harder! If you want to determine whether two words are anagrams of each other, all you need is to count or sort the letters. You don't need to generate a combinatoric explosion.

Design

GetReadableWords is not a well designed class. A good hint that the design is wrong is that classses (and objects) should be named like a noun, not a verb phrase. A second hint that you've gone wrong is that letters is really an input for just prob_words(), and not so much for chek_words().

In addition, neither prob_words() nor chek_words() is a good method name. Those names make no sense to me.

There is way too much code under if __name__ == "__main__". If you have that much code, then you should put it in a main() function and call it.

Suggested solution

'''Generate English words from given letters'''

class AnagramWordFinder:
    def __init__(self, word_list_filename='corncob_lowercase.txt'):
        self.vocab = {}
        with open(word_list_filename) as f:
            for line in f:
                word = line.rstrip()
                self.vocab.setdefault(''.join(sorted(word)), []).append(word)

    def words_from_letters(self, letters):
        return self.vocab.get(''.join(sorted(letters)), [])

def main():
    word_finder = AnagramWordFinder()
    print(word_finder.words_from_letters(input('Enter your characters: ')))

if __name__ == '__main__':
    main()

Arguably, you don't even need a class, especially if you only need to ask for input only once.

def unscramble_letters(letters, word_list_filename='corncob_lowercase.txt'):
    letters = ''.join(sorted(letters))
    with open(word_list_filename) as f:
        for line in f:
            if ''.join(sorted(line.rstrip())) == letters:
                yield line.rstrip()

if __name__ == '__main__':
    print(list(unscramble_letters(input('Enter your characters: '))))
\$\endgroup\$
3
  • 2
    \$\begingroup\$ In the function, you can simplify by deleting all of the string-joining. \$\endgroup\$
    – FMc
    May 17 at 17:21
  • \$\begingroup\$ Thanks so much @200_success That was so helpful. . And I really must work smarter than work harder. \$\endgroup\$
    – Sp3kTr0
    May 17 at 17:38
  • \$\begingroup\$ That was clever idea from clever teacher. \$\endgroup\$
    – Sp3kTr0
    May 17 at 17:50
0
\$\begingroup\$

Anagram lookup:

Unless capitalization is important, fold everything to, say, lowercase.

  1. Prep the list of valid rows by building a hash (associative array) mapping sorted letters to the word.
  2. When you have a set of letters, sort those letters, too.
  3. Then do a hashed lookup of step 2 in the array of step 1.

Step 1 might produce, for example:

amp => amp
amp => map
oot => too
\$\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.