Improve performance of combinations

It is slightly complicated to reason about the data since you have not attached it, but we can see multiple places that might provide an improvement:

1. First, let's rewrite the code in a way which is easier to reason about than using the indices:

   dictionary = {
       t.id: (
           t.text,
           t.set,
           t.compare_string
       )
       for t in dataframe.itertuples()
   }
   
   highly_similar = []
   
   for a, b in itertools.combinations(dictionary.items(), 2):
       a_id, (a_text, a_set, a_compre_string) = a
       b_id, (b_text, b_set, b_compre_string) = b
   
       if (a_compre_string == b_compre_string
               and not a_set.isdisjoint(b_set)):
           similarity_score = fuzz.ratio(a_text, b_text)
   
           if (similarity_score >= 95 and len(a_text) >= 10)
                   or similarity_score == 100):
               highly_similar.append(
                   [a_id, b_id, a_text, b_text, similarity_score])
   

2. You seem to only care about pairs having the same compare_string values. Therefore, and assuming this is not something that all pairs share, we can key by whatever that value is to cover much less pairs.

   To put some numbers into it, let's say you have 120K inputs, and 1K values for each value of val[1][2] - then instead of covering 120K * 120K = 14 * 10^9 combinations, you would have 120 bins of size 1K (where in each bin we'd need to check all pairs) = 120 * 1K * 1K = 120 * 10^6 which is about 1000 times faster. And it would be even faster if each bin has less than 1K elements.

   import collections
   
   # Create a dictionary from compare_string to all items
   # with the same compare_string
   items_by_compare_string = collections.defaultdict(list)
   for item in dictionary.items():
       compare_string = item[1][2]
       items_by_compare_string[compare_string].append(items)
   
   # Iterate over each group of items that have the same
   # compare string
   for item_group in items_by_compare_string.values():
       # Check pairs only within that group
       for a, b in itertools.combinations(item_group, 2):
           # No need to compare the compare_strings!
           if not a_set.isdisjoint(b_set):
               similarity_score = fuzz.ratio(a_text, b_text)
   
               if (similarity_score >= 95 and len(a_text) >= 10)
                       or similarity_score == 100):
                   highly_similar.append(
                       [a_id, b_id, a_text, b_text, similarity_score])
   

3. But, what if we want more speed? Let's look at the remaining operations:

   • We have a check to find if two sets share at least one item
     • This seems like an obvious candidate for optimization if we have any knowledge about these sets (to allow us to determine which pairs are even relevant to compare)
     • Without additional knowledge, and just looking at every two pairs and trying to speed this up, I doubt we can do much - this is probably highly optimized using internal details of Python sets, I don't think it's likely to optimize it further
   • We a fuzz.ratio computation which is some external function, and I'm going to assume is heavy
     • If you are using this from the FuzzyWuzzy package, make sure to install python-Levenshtein to get the speedups detailed here
   • We have some comparisons which we are unlikely to be able to speed up
     • We might be able to cache the length of a_text by nesting the two loops, but that's negligible
   • We have appends to a list, which runs on average ("amortized") constant time per operation, so we can't really speed that up

Therefore, I don't think we can reasonably suggest any more speedups without additional knowledge. If we know something about the sets that can help optimize which pairs are relevant we might be able to speed things up further, but I think this is about it.

EDIT: As pointed out in other answers, you can obviously run the code in multi-threading. I assumed you were looking for an algorithmic change that would possibly reduce the number of operations significantly, instead of just splitting these over more CPUs.

Essentially, from python programming side, i see two things that can improve your processing time:

Multi-threads and Vectorized operations

From the fuzzy score side, here is a list of tips you can use to improve your processing time (new anonymous tab to avoid paywall):

https://towardsdatascience.com/fuzzy-matching-at-scale-84f2bfd0c536

Using multi thread you can speed you operation up to N times, being N the number of threads in you CPU. You can check it with:

import multiprocessing
multiprocessing.cpu_count()

Using vectorized operations you can parallel process your operations in low level with SIMD (single instruction / multiple data) operations, or with gpu tensor operations (like those in tensorflow/pytorch).

Here is a small comparison of results for each case:

import numpy as np
import time

A = [np.random.rand(512) for i in range(2000)]
B = [np.random.rand(512) for i in range(2000)]
high_similarity = []


def measure(i,j,a,b,high_similarity):
    d = ((a-b)**2).sum()
    if d>12:
        high_similarity.append((i,j,d))

start_single_thread = time.time()
for i in range(len(A)):
    for j in range(len(B)):
        if i<j:
            measure(i,j,A[i],B[j],high_similarity)

finis_single_thread = time.time()

print("single thread time:",finis_single_thread-start_single_thread)

out[0] single thread time: 147.64517450332642

running on multi thread:

from threading import Thread
 
high_similarity = []
def measure(a = None,b= None,high_similarity = None):
    d = ((a-b)**2).sum()
    if d > 12:
        high_similarity.append(d) 

start_multi_thread = time.time()
for i in range(len(A)):
    for j in range(len(B)):
        if i<j:
            thread = Thread(target=measure,kwargs= {'a':A[i],'b':B[j],'high_similarity':high_similarity} )
            thread.start()
thread.join()

finish_multi_thread = time.time()
print("time to run on multi threads:",finish_multi_thread - start_multi_thread)

out[1] time to run on multi-threads: 11.946279764175415

A_array = np.array(A)
B_array = np.array(B)

start_vectorized = time.time()
for i in range(len(A_array)):
    #vectorized distance operation
    dists = (A_array-B_array)**2

    high_similarity+= dists[dists>12].tolist()

    aux   = B_array[-1]
    np.delete(B_array,-1)
    np.insert(B_array, 0, aux)

finish_vectorized = time.time()

print("time to run vectorized operations:",finish_vectorized-start_vectorized)

out[2] time to run vectorized operations: 2.302949905395508

Note that you can't guarantee any order of execution, so will you also need to store the index of results. The snippet of code is just to illustrate that you can use parallel process, but i highly recommend to use a pool of threads and divide your dataset in N subsets for each worker and join the final result (instead of create a thread for each function call like i did).