# Optimize function that does phrase-search and lists them

I am writing a long piece of code, which is taking way too long to execute. I used cProfile on the code, I found that the following function is called 150 times and takes 1.3 seconds per call, leading to around 200 seconds to this function alone. The function is -

def makeGsList(sentences,org):
gs_list1=[]
gs_list2=[]
for s in sentences:
if s.startswith(tuple(StartWords)):
s = s.lower()
if org=='m':
gs_list1 = [k for k in m_phrases if k in s]
if org=='h':
gs_list1 = [k for k in h_phrases if k in s]
for gs_element in gs_list1:
gs_list2.append(gs_element)
gs_list3 = list(set(gs_list2))
return gs_list3


The code is supposed to take a list of sentences and a flag org. Then it goes through each line, checks if it starts with any of the words present in the list StartWords, and then lower-cases it. Then, depending on the value of org, it makes a list of all phrases in the current sentence which are also present in either m_phrases or h_phrases. It keeps appending these phrases to another list gs_list2. Finally it makes a set of gs_list2 and returns it.

Can someone give me any suggestion as to how I can optimize this function to reduce the time taken to execute?

Some examples -

StartWords = ['!Series_title','!Series_summary','!Series_overall_design','!Sample_title','!Sample_source_name_ch1','!Sample_characteristics_ch1']

sentences = [u'!Series_title\t"Transcript profiles of DCs of PLOSL patients show abnormalities in pathways of actin bundling and immune response"\n', u'!Series_summary\t"This study was aimed to identify pathways associated with loss-of-function of the DAP12/TREM2 receptor complex and thus gain insight into pathogenesis of PLOSL (polycystic lipomembranous osteodysplasia with sclerosing leukoencephalopathy). Transcript profiles of PLOSL patients\' DCs showed differential expression of genes involved in actin bundling and immune response, but also for the stability of myelin and bone remodeling."\n', u'!Series_summary\t"Keywords: PLOSL patient samples vs. control samples"\n', u'!Series_overall_design\t"Transcript profiles of in vitro differentiated DCs of three controls and five PLOSL patients were analyzed."\n', u'!Series_type\t"Expression profiling by array"\n', u'!Sample_title\t"potilas_DC_A"\t"potilas_DC_B"\t"potilas_DC_C"\t"kontrolli_DC_A"\t"kontrolli_DC_C"\t"kontrolli_DC_D"\t"potilas_DC_E"\t"potilas_DC_D"\n',  u'!Sample_characteristics_ch1\t"in vitro differentiated DCs"\t"in vitro differentiated DCs"\t"in vitro differentiated DCs"\t"in vitro differentiated DCs"\t"in vitro differentiated DCs"\t"in vitro differentiated DCs"\t"in vitro differentiated DCs"\t"in vitro differentiated DCs"\n', u'!Sample_description\t"DAP12mut"\t"DAP12mut"\t"DAP12mut"\t"control"\t"control"\t"control"\t"TREM2mut"\t"TREM2mut"\n']

h_phrases = ['pp1665', 'glycerophosphodiester phosphodiesterase domain containing 5', 'gde2', 'PLOSL patients', 'actin bundling', 'glycerophosphodiester phosphodiesterase 2', 'glycerophosphodiester phosphodiesterase domain-containing protein 5']


m_phrases are similar. Assume in this case, org=h.

Regarding sizes -

The length of both lists h_phrases and m_phrases is around 250,000. And each element in the lists is on an average 2 words long. The list of sentences is around 10-20 sentences long and I have provided an example list to give you the idea of how big each sentence can be.

• Welcome to codereview! Please change the title so that it denotes what the code does, not what you're expecting out of a review. More, please provide some sentences examples. Some test cases wouldn't hurt. What are StartWords, m_words, h_words? If you expect good reviews, make sure you add all the relevant data to your question – яүυк Jul 15 '17 at 10:43
• @MrGrj done as you said – user1993 Jul 15 '17 at 11:04
• @user1993: Thanks for adding some examples. But none of the phrases occur in any of the sentences! Is this also the case in your data? (If so, I can think of a very easy way to speed it up.) If not, could you update the post to include better (that is, more representative) examples? – Gareth Rees Jul 15 '17 at 12:30
• In this kind of problem the sizes are quite important. How many sentences do you have in your data? How many start words? How many phrases? – Gareth Rees Jul 15 '17 at 12:37
• @GarethRees I have improved the examples and provided an idea about the sizes. You can have a look – user1993 Jul 15 '17 at 13:31

To improve the performance of code, a good plan is to:

1. Identify the hotspots, for example using profiling.

2. Prepare a representative test case and measure its performance.

3. Experiment with changes and see which ones improve the performace.

Step (2) is very important — if we don't have a representative test case then we might end up measuring the wrong thing. In this case I understand from the post that in the real program:

1. There are few sentences (tens), mostly 100 words or fewer.

2. There are many phrases (250,000), mostly with 5 words or fewer.

3. The matches are quite sparse (most sentences have no phrases).

4. The sentences change between calls to makeGsList but the phrases remain the same for each call.

So my test case is going to use your sentences list (8 elements is reasonably close to "10–20"), but I'm going to have to make my own phrases list, because you've only given me 7 elements which is nowhere near to 250,000.

>>> words = [line.strip().lower() for line in open('/usr/share/dict/words')]
>>> len(words)
235886
>>> from random import sample, randrange
>>> m_phrases = [' '.join(sample(words, randrange(1, 6))) for _ in range(250000)]


and then I'll time ten executions of makeGsList using Python's timeit module:

>>> from timeit import timeit
>>> timeit(lambda:makeGsList(sentences, 'm'), number=10)
2.7161848249379545


This is roughly similar to your reported results, so it might be representative enough. Now to try some changes.

First, let's tidy the code.

1. Instead of converting StartWords to a tuple for each sentence, convert it just once.

2. Instead of taking an org argument (and then checking it for each sentence), take a phrases argument.

3. Instead of maintaining a list gs_list2 and then converting it to a set to remove duplicates, maintain a set instead.

Revised code (this isn't noticeably faster, but it's in a better shape to work on):

def makeGsList2(sentences, phrases):
"Return list of elements of phrases that appear in any of the sentences."
start_words = tuple(StartWords)
gs_set = set()
for s in sentences:
if s.startswith(start_words):
s = s.lower()
for phrase in phrases:
if phrase in s:
return list(gs_set)


It's clear that we have to avoid the loop over the phrases for each sentence. What we can do instead is to pre-process the phrases into a data structure that we can apply once to each sentence. What we need here is the Aho–Corasick algorithm. This isn't built into Python, but we could try one of the packages from PyPI. In the code below I'm using the pyahocorasick package; see the documentation for details.

import ahocorasick

def make_automaton(phrases):
"""Return an ahocorasick.Automaton that matches any of the phrases."""
automaton = ahocorasick.Automaton()
for phrase in phrases:
automaton.make_automaton()
return automaton

def makeGsList3(sentences, automaton):
"Return list of unique matches of the automaton against the sentences."
start_words = tuple(StartWords)
gs_set = set()
for s in sentences:
if s.startswith(start_words):
gs_set.update(phrase for _, phrase in automaton.iter(s.lower()))
return list(gs_set)


Building the automaton takes a few seconds but it can be done just once for each list of phrases:

>>> m_automaton = make_automaton(m_phrases)


And then the actual search is very quick:

>>> timeit(lambda:makeGsList3(sentences, m_automaton), number=10)
0.0021720759104937315


This is about 1,200 times faster than the code in the post! Of course, this result only stands up to the extent that my test case is representative of the real system.

• thanks a lot for the detailed answer. Little busy now, but will get back to you on this very soon – user1993 Jul 15 '17 at 15:27
• I dearly want to try your method, but I use Spyder for my coding (Windows 10) and I am trying to install pyahocorasick in it, but to no avail. I have opened an issue on their github page to see if anybody can help - github.com/conda/conda/issues/5714 – user1993 Jul 22 '17 at 10:56
• i was finally able to get it to work. It's amazing! It sped up my code by 3 times. Was just going through the wiki page for the algorithm and the paper, to try to understand how they came up with this idea. Quite amazing – user1993 Jul 31 '17 at 5:33
• i was going through the examples of the AC algorithm, and I found that it outputs all elements of the list which are subsets of the search key. But here I (and I believe a lot of people, for their work) need to find exact matches of the search key in the list. Does the command you used, do precisely that?, even if the AC can do a lot more? – user1993 Jul 31 '17 at 11:25