7
\$\begingroup\$

I have a file in which I was to check the string similarity within the names in a particular column. I use fuzzywuzzy token sort ratio algorithm as it is required for my use case. here is the code, is there a way to speed it up? It is taking a lot of time for 30000 records.

import csv
import itertools
import pandas as pd
from fuzzywuzzy import fuzz

data = pd.read_csv('D:\\Sim_Input.csv')

Dishes = data['Product_Name']

threshold_ratio = 85

with open('D:\\Sim_Score.csv', 'w') as f1:
    writer = csv.writer(f1, delimiter='\t', lineterminator='\n', )
    writer.writerow(['tag4'])
    for str_1, str_2 in itertools.permutations(Dishes, 2):
        list = []
        ratio = (fuzz.token_sort_ratio(str_1, str_2))
        if ratio > threshold_ratio:
            row = (str_1, str_2, ratio)
            list.append(row)
            print(list)
            writer.writerow(list)

I need the output in a csv file with the names of ItemA, ItemB and similarity score, where the similarity should be above 85.

\$\endgroup\$
  • \$\begingroup\$ Makes sense... You're computing fuzzy similarity across 899,970,000 different permutations. Any reason you can't use combinations instead? itertools.combinations(Dishes, 2) should give you only 449,985,000 combinations, but you'd still consider every pair of dishes. \$\endgroup\$ – scnerd May 3 '18 at 14:47
  • \$\begingroup\$ Are you/can you run this on a multi-core machine? This code would be easy to parallelize \$\endgroup\$ – scnerd May 3 '18 at 14:52
  • \$\begingroup\$ I have a 8 core machine, Intel I7. How can this be parallelize? \$\endgroup\$ – Rishab Oberoi May 3 '18 at 15:56
  • \$\begingroup\$ can I use generators to make this run fast? \$\endgroup\$ – Rishab Oberoi May 3 '18 at 15:57
4
\$\begingroup\$

To avoid processing each dish so many times, you can use this to process them only 1 time:

dishes = ["pizza with bacon", "pizza with extra cheese", "vegetarian pizza", "cheese and bacon pizza", "bacon with pizza"]

processedDishes = []

for dish in dishes:
    processedDishes.append(fuzz._process_and_sort(dish, True, True))

for dish1, dish2 in itertools.combinations(enumerate(processedDishes), 2):  
    if fuzz.ratio(dish1[1], dish2[1]) >= 85:
        print(dishes[dish1[0]], dishes[dish2[0]])

You can then combine this with @scnerd solution to add multiprocessing

If you know your data is all the same type, you can further optimize it:

dishes = ["pizza with bacon", "pizza with extra cheese", "vegetarian pizza", "cheese and bacon pizza", "bacon with pizza"]

processedDishes = []
matchers = []

for dish in dishes:
    if dish:
        processedDish = fuzz._process_and_sort(dish, True, True)
        processedDishes.append(processedDish)
        matchers.append(fuzz.SequenceMatcher(None, processedDish))


for dish1, dish2 in itertools.combinations(enumerate(processedDishes), 2):
    matcher = matchers[dish1[0]]
    matcher.set_seq2(dish2[1])
    ratio = int(round(100 * matcher.ratio()))

    if ratio >= 85:
        print(dishes[dish1[0]], dishes[dish2[0]])

Update: checked how these ratios are calculated, here is a more efficient answer that avoids a lot of checks between pairs:

dishes = ["pizza with bacon", "pizza with extra cheese", "vegetarian pizza", "cheese and bacon pizza", "bacon with pizza", "a"]


processedDishes = []
matchers = []

for dish in dishes:
    if dish:
        processedDish = fuzz._process_and_sort(dish, True, True)
        processedDishes.append({"processed": processedDish, "dish": dish})


processedDishes.sort(key= lambda x: len(x["processed"]))

for idx, dish in enumerate(processedDishes):
    length = len(dish["processed"])
    matcher = fuzz.SequenceMatcher(None, dish["processed"])
    for idx2 in range(idx + 1, len(processedDishes)):
        dish2 = processedDishes[idx2]
        if 2 * length / (length + len(dish2["processed"])) < 0.85: # upper bound
            break

        matcher.set_seq2(dish2["processed"])

        if matcher.quick_ratio() >= 0.85 and matcher.ratio() >= 0.85: # should also try without quick_ratio() check
            print(dish["dish"], dish2["dish"])
\$\endgroup\$
  • \$\begingroup\$ This is great! I used your code and combine with @scnerd Multiprocessing and the entine 30000 ran in 15 minutes with permutations. It used to take some 8 hours. Even with the code that scnerd with, it took 5 hours. \$\endgroup\$ – Rishab Oberoi May 4 '18 at 17:43
  • 1
    \$\begingroup\$ @RishabOberoi impressive :). Maybe you should post final code combining both as an answer too \$\endgroup\$ – juvian May 4 '18 at 17:48
  • \$\begingroup\$ @RishabOberoi check my update \$\endgroup\$ – juvian May 4 '18 at 18:29
  • \$\begingroup\$ Yes, the algo works exactly how you implemented in the updated code. This is again very fast. let me work on my code and will share the complete solution that I am building. \$\endgroup\$ – Rishab Oberoi May 5 '18 at 13:59
8
\$\begingroup\$

The first algorithmic recommendation is to use itertools.combinations instead of .permutations, since you don't care about order. This assumes fuzz.token_sort_ratio(str_1, str_2) == fuzz.token_sort_ratio(str_2, str_1). There are half as many combinations as there are permutations, so that gives you a free 2x speedup.

This code also lends itself easily to parallelization. On an i7 (8 virtual cores, 4 physical), you could probably expect this to give you ~4-8x speedup, but that depends on a lot of factors. The least intrusive way to do this is to use multiprocessing.Pool.map or .imap_unordered:

import multiprocessing as mp

def ratio(strings):
    s1, s2 = strings
    return s1, s2, fuzz.token_sort_ratio(s1, s2)

with open('D:\\Sim_Score.csv', 'w') as f1:
    writer = csv.writer(f1, delimiter='\t', lineterminator='\n', )
    writer.writerow(['tag4'])

    with mp.Pool() as pool:
        for s1, s2, r in pool.imap_unordered(ratio, itertools.combinations(Dishes, 2)):
            if r > threshold_ratio:
                writer.writerow([(s1, s2, r)])

All told, I'd expect these changes to give you 5-10x speedup, depending heavily on the number of cores you have available.

For reference, a generator comprehension version of this might look something like:

with mp.Pool() as pool:
    writer.writerows((s1, s2, r)
                     for s1, s2, r in pool.imap_unordered(ratio, itertools.combinations(Dishes, 2))
                     if r > threshold_ratio)

That version has a some, but very little, performance improvement over the non-comprehension version, and IMO is harder to read/maintain.

One other minor thing I noticed in testing my code was that fuzzywuzzy recommends installing python-Levenshtein in order to run faster; when I did so, it ran about 20x slower than when it used the built-in SequenceMatcher. When I uninstalled python-Levenshtein it got fast again. That seems very odd to me, but it's certainly something worth trying.

Finally, if performance is important, you could consider digging into what fuzz.token_sort_ratio does to see if you could remove some repeated work. For example, it's tokenizing and sorting each string again every time you pass it in, so maybe you could pre-tokenize/sort the strings and only run the ratio logic inside the main loop. A quick dig tells me that token_sort_ratio is two main steps:

  1. Preprocess each string using fuzz._process_and_sort

  2. Run fuzz.partial_ratio against the processed strings

I'm not able to get this to run faster at the moment, but I'll edit and update this answer if I can get that approach to work well.

\$\endgroup\$
  • \$\begingroup\$ Thanks, I shall try this and will post the result. Please share and update when you find something. \$\endgroup\$ – Rishab Oberoi May 3 '18 at 18:16
  • \$\begingroup\$ Hi, I tried your updated code of 200000 approx distinct records. The previous code took 3 hours and the updated one took 47 minutes. \$\endgroup\$ – Rishab Oberoi May 11 '18 at 12:07

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.