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
import multiprocessing as mp
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', )
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:
Preprocess each string using
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.