Ускорение попарного нечеткого сопоставления строк в Python

У меня есть коллекция из 40 000 строк, и я хочу сравнить их сходство попарно, используя fuzz.token_set_ratio(), но мой мозг не настроен правильно, чтобы сделать это эффективным способом, даже после изучения векторизации.

Вот пример:

from fuzzywuzzy import fuzz

s = ["fuzzy was a strong bear", 
 "fuzzy was a large bear", 
 "fuzzy was the strongest bear you could ever imagine"]

similarities = []
l = len(s)

for i in range(l):
    similarities.append([])
    for j in range(l):
        similarities[i].append(fuzz.token_set_ratio(s[i], s[j]))
similarities

Теперь очевидно, что этот код имеет как минимум два недостатка. Во-первых, он использует неэффективные циклы for. Во-вторых, хотя результирующая матрица similarities симметрична (это не всегда верно, но пока не обращайте на это внимания) и мне нужно вычислить только верхний или нижний треугольник, она вычисляет все элементы. Последнее, вероятно, то, что я мог бы написать по-своему, но я ищу самый быстрый способ получить similarities в Python.

Редактировать: Вот еще одна часть, возможно, полезной информации. Я попытался ускорить процесс, используя pdist, который, кажется, хорошо работает для некоторых подобных задач. Однако в этом случае по какой-то причине он кажется медленнее, чем мои неэффективные циклы for.

Вот код:

from fuzzywuzzy import fuzz
from scipy.spatial.distance import pdist, squareform
import numpy as np

def pwd(string1, string2):
    return fuzz.token_set_ratio(string1, string2)

s = []
for i in range(100):
    s.append("fuzzy was a strong bear")
    s.append("fuzzy was a large bear")
    s.append("fuzzy was the strongest bear you could ever imagine")

def pwd_loops():
    similarities = []
    l = len(s)
    for i in range(l):
        similarities.append([])
        for j in range(l):
            similarities[i].append(fuzz.token_set_ratio(s[i], s[j]))

a = np.array(s).reshape(-1,1)
def pwd_pdist():
    dm = squareform(pdist(a, pwd))

%time pwd_loops()
#Wall time: 2.39 s

%time pwd_pdist()
#Wall time: 3.73 s