Better way to iterate through a dictionary and comparing its keys with itself I have a dictionary with author names as keys and values of None. I want to use fuzzywuzzy to compare these author names to see if there are similar ones that I can combine.

So far I am using two dictionaries (they have the same data in both of them, and ideally I would just use one) and then using a double for loop. I want to optimize it further, and I was thinking of using Dictionary Composition, but I couldn't figure out how to get that working with my fuzzy compare logic.

import uuid
from fuzzywuzzy import fuzz

authorToDelete = {}
dictOfAllData1 = {'Trevor Jacobs': None, 'Josh Francis': None, 'Marcie Lank': None, 'Marcie H. Lank': None}
dictOfAllData2 = {'Trevor Jacobs': None, 'Josh Francis': None, 'Marcie Lank': None, 'Marcie H. Lank': None}

for key in dictOfAllData1:
    for key2 in dictOfAllData2:
        str1 = ' '.join(key.split()) #some spaces are different so I handle those here
        str2 = ' '.join(key2.split())
        ratio = fuzz.ratio(str1, str2)
        if fuzz.ratio(str1, str2) &gt; 85 and dictOfAllData1[key] == None:
            dictOfAllData1[key] = str(uuid.uuid1())
        elif ratio &gt; 85:
            if str1 != str2:
                authorToDelete[key2] = None
            else:
                dictOfAllData1[key] = str(uuid.uuid1())

for deleteMe in authorToDelete:
    dictOfAllData1.pop(deleteMe)

print(dictOfAllData1)

#Output is: {'Trevor Jacobs': 'edb6e3d8-3898-11ea-9b62-784f4397bfaf', 'Josh Francis': 'edb6e892-3898-11ea-9b62-784f4397bfaf', 'Marcie Lank': 'edb6eaea-3898-11ea-9b62-784f4397bfaf'}



This is the code I have so far. It works, but it takes longer than I think it should (about 4 seconds with a dictionary of ~700 keys, and about 80 seconds with a dictionary of ~2,700 keys)

My question is how can I make this more efficient? Is there a way I can use if in dict or something like that instead of my second for loop?

I originally posted this on StackOverflow
Before speaking about the actual algorithm, let me hint you at the official Style Guide for Python Code (often just called PEP 8), a set of guidelines to write idiomatic-looking Python code. A core takeaway of the read should be, that in Python lower_case_with_underscores is the preferred way to name variables and functions. Fortunately you don't have to remember all those rules. There is good tool support for style and also static code checking in Python. A non-exhaustive list can be found here on this post here on Code Review Meta. I personally most often use flake8 and pylint from that list.

With that out of the way, let's have a look at the code. First, you don't need to have two copies of your dict. Also, the whitespace normalization inside the loop is run more often than needed, because it is calculated several times for every key. Fortunately, it's easy to solve both of those problems:

keys = list(dict_of_all_data.keys())
authors = {key: ' '.join(key.split()) for key in keys}


keys now holds all author names from the original dict, whereas authors holds their normalized versions. Maybe you should also consider to convert all the names to upper-/lowercase in order to make it even more robust, but you'll have to see yourself if that's worth it.

Looking at the fuzzywuzzy documentation of fuzzywuzzy.fuzz reveals that it basically seems to be a wrapper around difflib.SequenceMatcher. From a few quick experiments I got the impression that the following is true:

fuzzywuzzy.fuzz(str1, str2) == fuzzywuzzy.fuzz(str2, str1)


With that in mind, the amount of computations can be cut down even more, by avoiding duplicate comparisons. Since you gave no special reason for using UUIDs, I skipped them in the reworked code for the moment.

dict_of_all_data = {'Trevor Jacobs': None, 'Josh Francis': None, 'Marcie Lank': None, 'Marcie H. Lank': None}

keys = list(dict_of_all_data.keys())
authors = {key: ' '.join(key.split()) for key in keys}
authors_to_delete = []

for i, key1 in enumerate(keys, 1):
    author1 = authors[key1]
    for key2 in keys[i:]:   # this helps to avoid duplicate comparison
        author2 = authors[key2]
        ratio = fuzz.ratio(author1, author2)
        if ratio &gt; 85 and dict_of_all_data[key1] is None:
            dict_of_all_data[key1] = True   # likely not even necessary
            authors_to_delete.append(key2)

for delete_me in authors_to_delete:
    dict_of_all_data.pop(delete_me)

print(dict_of_all_data)


As a bonus, one should wrap the code into a function to nicely separate it from the rest of the code. Whether or not you want to convert this code into a function, it would be a good idea to replace the magic value 85 with a parameter/constant with a meaningful name.

Grajdeanu Alex presents a similar idea in his answer, but uses itertools.combinations instead of doing the de-duplication manually as I suggested above.