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

Question

У меня есть коллекция из 40000 строк, и я хочу сравнить их сходство попарно, используя 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