Cómo comparar de manera eficiente dos diccionarios de listas de cadenas usando difflib?

Tengo dos diccionarios grandes de listas. Todos los elementos de las listas son cadenas de texto. Quiero comparar todos contra todos y calcular su similitud respectiva; pero el método ingenuo que utilizo es obviamente muy lento y no escala en absoluto:

import numpy as np
import difflib

first_dict = {"first1": ["aa", "bb", "cc", "dd"], "first2": ["ff", "gg"]}

second_dict = {"second1": ["cc", "dd", "jj", "aa", "bb"], "second2": ["ff", "gg"], "second3": ["hh", "ii"]}

mat = np.empty((len(second_dict), len(first_dict)))

for i, second in enumerate(second_dict.keys()):
    for j, first in enumerate(first_dict.keys()):
        sm = difflib.SequenceMatcher(None, sorted(first_dict[first]), sorted(second_dict[second]))
        mat[i, j] = sm.ratio()

print(mat)

¿Hay alguna manera inteligente de acelerar esto?