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.
To improve the performance of code, a good plan is to:


Identify the hotspots, for example using profiling.
Prepare a representative test case and measure its performance.
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:


There are few sentences (tens), mostly 100 words or fewer.
There are many phrases (250,000), mostly with 5 words or fewer.
The matches are quite sparse (most sentences have no phrases).
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.

&gt;&gt;&gt; words = [line.strip().lower() for line in open('/usr/share/dict/words')]
&gt;&gt;&gt; len(words)
235886
&gt;&gt;&gt; from random import sample, randrange
&gt;&gt;&gt; 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:

&gt;&gt;&gt; from timeit import timeit
&gt;&gt;&gt; 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.


Instead of converting StartWords to a tuple for each sentence, convert it just once.
Instead of taking an org argument (and then checking it for each sentence), take a phrases argument.
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:
                    gs_set.add(phrase)
    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.add_word(phrase, phrase)
    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:

&gt;&gt;&gt; m_automaton = make_automaton(m_phrases)


And then the actual search is very quick:

&gt;&gt;&gt; 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.