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:
Preprocess each string using fuzz._process_and_sort
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.
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