Reducing computation time in a nested loop

Wiliam 0
Viewed 70

Suppose I have a dataframe with 3 rows of text:

#(needed libraries):
from keybert import KeyBERT
from sentence_transformers import SentenceTransformer
from keyphrase_vectorizers import KeyphraseCountVectorizer
import pandas as pd
sentence_model = SentenceTransformer("all-MiniLM-L6-v2")
st_model = KeyBERT(model=sentence_model)

data = pd.DataFrame({'text':['Machine learning (ML) is a type of artificial intelligence (AI) that allows software applications to become more accurate at predicting outcomes without being explicitly programmed to do so. Machine learning algorithms use historical data as input to predict new output values.','Physics is the natural science that studies matter, its fundamental constituents, its motion and behavior through space and time, and the related entities of energy and force. Physics is one of the most fundamental scientific disciplines, with its main goal being to understand how the universe behaves.','Chemistry is the branch of science that deals with the properties, composition, and structure of elements and compounds, how they can change, and the energy that is released or absorbed when they change.']})

I want to go through each text (row) and pick the most relevant if they follow a specific pattern, do to this I made a double loop (nested loop) which does the job but takes a lot of computational time, my method is as follow:

pt = []
patterns = ['<J.*>*<N.*>+', '<V.*>+', '<N.*>*<V.*>+', '<J.*>*<N.*>*<V.*>+']
for j in range(len(data)):
    for i in range(len(patterns)):
        vectorizer = KeyphraseCountVectorizer(pos_pattern = patterns[i])
        pt.append(st_model.extract_keywords(data.text.iloc[j],stop_words = "english", vectorizer=vectorizer,use_mmr=True, diversity=0.4))

as you can see there is 4 patterns that should be applied to 3 rows of texts. I wonder how can I make this nested loop computationally light as my original dataset contains 1000s of rows and using this method will take hours to be executed.

Bear in mind I've provided the libraries and the exact context so my problem would be reproduceable but the real issue happens in the second block of code where the nested loop is located.

UPDATE: I have also now tried to use itertools product as:

pt = []
vecz = []
patterns = ['<J.*>*<N.*>+', '<V.*>+', '<N.*>*<V.*>+', '<J.*>*<N.*>*<V.*>+']
for i in range(len(patterns)):
    vectorizer = KeyphraseCountVectorizer(pos_pattern = patterns[i])
    vecz.append(vectorizer)
    
from itertools import product  

for j, i in product(range(len(data)), range(len(vecz))):
    pt.append(st_model.extract_keywords(data.text.iloc[j],stop_words = "english", vectorizer=vecz[i],use_mmr=True, diversity=0.4))

but the performance did not improve drastically.

itertools nested-loops python
2 Answers

For an optimization problem, the first thing you should do is measure. Run the following from a terminal:

python -m cProfile -s tottime yourscript.py

And observe the lines in the resulting table with the highest tottime.

Everything that's less than 5% of the total time is probably not worth looking at.

I have repeatedly written about profiling and improving Python programs. Here is a link to the first article. The rest of the articles in the series are shown on the bottom of that page.

Functions and methods built into Python are often not worth looking at unless you can modify their parameters. Consider the following string formatting operation:

In [1]: f = 139.3592529296875;

In [3]: %timeit str(f)
724 ns ± 0.31 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [4]: %timeit "{0}".format(f)
734 ns ± 1.21 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [5]: %timeit "{0:.5f}".format(f)
314 ns ± 0.0365 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [7]: %timeit "{0:f}".format(f)
313 ns ± 7.35 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [8]: %timeit "{0:e}".format(f)
382 ns ± 0.171 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Observe how using a format specifier can cut the time for the conversion in half. The reason I researched this was because through profiling I found a program of mine that spent about 50% of its time formatting strings...

If the bottleneck is in an external library, it is time to peruse the documentation for that thoroughly. There might be a faster way than you are using now.

Optimization

A general observation is that a better algorithm tends to beat optimizing. Seeing as how I'm not familiar with the libraries you are using, I cannot offer concrete advice here.

General advice for speeding up loops

  • Move all invariants (things that don't change between iterations) outside of the loop.
  • Can you create invariants by re-ordering nested loops?
  • If the iterations of a loop are independent, that is the result of an iteration does not depend on a previous iteration, consider using multiprocess to run them in parallel. That will not reduce the total amount of time, but it will make use of the multiple CPU's that basically every computer has these days.
userFd750

Two main things will likely speed this up a lot:

  1. Bring Vectorizer out of the loop.
  2. Pass the whole column to st_model.extract_keywords, it accepts an array!
patterns = ['<J.*>*<N.*>+', '<V.*>+', '<N.*>*<V.*>+', '<J.*>*<N.*>*<V.*>+']
vectorizers = [KeyphraseCountVectorizer(pos_pattern=pattern) for pattern in patterns]

for i, vectorizer in enumerate(vectorizers):
    # Pass the whole column.
    data[f'pattern{i}'] = st_model.extract_keywords(data.text, stop_words = "english", vectorizer=vectorizer, use_mmr=True, diversity=0.4)

print(data)

Output:

                                                text                                           pattern0                                           pattern1                                           pattern2                                           pattern3
0  Machine learning (ML) is a type of artificial ...  [(machine learning algorithms, 0.6082), (ai, 0...  [(predicting, 0.3156), (programmed, 0.2338), (...  [(machine learning algorithms use, 0.6833), (p...  [(machine learning algorithms use, 0.6833), (p...
1  Physics is the natural science that studies ma...  [(physics, 0.554), (fundamental scientific dis...  [(matter, 0.3478), (behaves, 0.1066), (underst...  [(physics is, 0.64), (studies matter, 0.3398),...  [(physics is, 0.64), (universe behaves, 0.3568...
2  Chemistry is the branch of science that deals ...  [(chemistry, 0.6888), (science, 0.4082), (elem...  [(absorbed, 0.2731), (change, 0.1097), (is rel...  [(chemistry is, 0.7016), (absorbed, 0.2731), (...  [(chemistry is, 0.7016), (absorbed, 0.2731), (...
BeRT2me0
Related