5
\$\begingroup\$

The following code takes in two params. An array of sentences and an array of queries. Each query has one or more words. The function below prints out index of sentence for each query that has all the words in that sentence.

This is functioning code. However, it is not optimized for large inputs because of how it is written.

How can we make it more runtime optimized? Any ideas would be appreciated.

def textQueries(sentences, queries):
    sentences_sets = [set(s.split(' ')) for s in sentences]
    for i, words in enumerate(queries):
        results = ''
        for j, s in enumerate(sentences_sets):
            exists = True
            for word in words.split(' '):
                if word not in s:
                    exists = False
            if exists:
                results += ' %d' % j if results else '%d' % j
        if results:
            print results
        else: print -1
\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! You're talking about "large inputs". Can you give the reviewers a hint how large those inputs may be (typical number and length of sentences/queries)? You should also add some application context to better understand the code and its purpose. \$\endgroup\$ – AlexV Apr 22 at 22:07
  • \$\begingroup\$ 1 < len(sentences) <= 10,000, 1 < len(queries) <= 10,000 \$\endgroup\$ – jisu Apr 23 at 0:36
4
\$\begingroup\$

Welcome to Code Review!

So, I am assuming that queries is a list of words we are searching for, and any of them being found is a success. I am also assuming that sentences is a list of strings, with each element subdivide-able into a list of words.

Bugs:

I noticed that your existing code won't see "This is a test." as having the word "test" in it, because of the period. You may need to separate out commas, periods, parentheses and so on for it to work properly, but perhaps this is by design. I am unsure.

Add a Break:

The first thing I see that could be improved is you don't need a flag. Instead of setting exists = False and then keep looping, just add your results if it is there, and then just break. You don't need to search the entire sentence if you have already found it, and you don't need a flag if you are doing the one operation within the loop.

So:

for word in words.split(' '):
    if word in s:
        results += ' %d' % j if results else '%d' % j
        break

This will save you a few iterations for long sentences if the beginning matches.

Tries:

Now, if you want to completely rewrite the whole thing for O(n) passes, (which is the best you can possibly get for text searching), then you can use a "Trie" data structure. The way this works is by inserting all of your text, one character at a time per word, into a variation of a tree. This is O(n) insertion, where n is the number of characters in your input data. Then, for every search term, you go through and find, letter by letter, which words match. This is O(n) where n is the number of characters in each search term, so theoretically much less of an impact than the previous one.

I modified the code that was posted here (under public domain): https://towardsdatascience.com/implementing-a-trie-data-structure-in-python-in-less-than-100-lines-of-code-a877ea23c1a1

Most of it is not my own, but I modified it to fit your function.

class Node(object):
    def __init__(self, character):
        self.character = character
        self.children = []
        # A flag to say whether or not we are at the end of our current word.
        self.finished = False
        # How many times this character appeared in the addition process
        self.count = 1

class Trie(object):
    def __init__(self):
        # Create a root node with a non-character attribute so it won't be confused
        # with any of the entries.
        self.root = Node(None)

    def add(self, word):
        # Set our current node to the start/root.
        current_node = self.root
        for char in word:
            in_child = False
            # Search for the character in the children of the present node
            for child in current_node.children:
                if child.character == char:
                    # We found it, increase the counter by 1 to keep track that another
                    # word has it as well
                    child.count += 1
                    # And point the node to the child that contains this char
                    current_node = child
                    in_child = True
                    break
            # We did not find it so add a new chlid
            if not in_child:
                new_node = Node(char)
                current_node.children.append(new_node)
                # And then point node to the new child
                current_node = new_node
        # Everything finished. Mark it as the end of a word.
        current_node.word_finished = True


    def find_term(self, term):
        """
        Check and return
          1. If the prefix exsists in any of the words we added so far
          2. If yes then how may words actually have the prefix
        """
        node = self.root
        # If the root node has no children, then return False.
        # Because it means we are trying to search in an empty trie
        if not self.root.children:
            return False, 0
        for char in term:
            char_not_found = True
            # Search through all the children of the present `node`
            for child in node.children:
                if child.character == char:
                    # We found the char existing in the child.
                    char_not_found = False
                    # Assign node as the child containing the char and break
                    node = child
                    break
            # Return False anyway when we did not find a char.
            if char_not_found:
                return False, 0
        # Well, we are here means we have found the prefix. Return true to indicate that
        # And also the counter of the last node. This indicates how many words have this
        # prefix
        return True, node.count

def textQueries(sentences, queries):
    trie = Trie()
    sentences_list = [s.split(' ') for s in sentences]
    for sentence in sentences_list:
        for word in sentence:
            trie.add(word)

    for words in queries:
        words_list = words.split(' ')
        results_list = []
        for word in words_list:
            results = trie.find_term(word)
            if results[0]:
                results_list.append(results[1])
        if results_list:
            print results_list
        else: print -1

This will return:

Venkee Enterprises:>python test.py 
[2]
[1]

for my input data of:

sentences = ["Hello world, this is a sentence.", "This is also a sentence.", "This, however, is an incomplete"]
queries = ["sentence", "Hello"]

As it was able to find 2 words that match for the query "sentence" and 1 word that matched "Hello".

Hope this helps.

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