Вложено для цикла, занимающего много времени в Python (оптимизация)

Question

У меня есть код на языке Python с вложенным циклом for, и он занимает слишком много времени, подумайте о наличии словаря типа dict = {'110': ('jade'), '2': ('amber'), '111' : ('harry')}

, а вот мой код -

all_keys = dict.keys()
for number in all_keys:
    for more_number in all_keys:
        if SequenceMatcher(None, number, more_number).ratio() > 0.5:
            dict[number] = dict[number].union(dict[more_number])

Вывод: -

dict = {'110' : ('jade', 'harry'), '2' : ('amber')}

то, что делает этот код, проверяет, имеет ли ключи вероятность совпадения более 0,5, и если да, то добавляет оба ключа в набор и сохраняет его,Для получения дополнительных данных требуется так много времени по понятным причинам.Есть ли способ оптимизировать?

Answer 1

Для начала, ваш код выделяет экземпляр SequenceMatcher в каждой итерации инерного цикла, всего O(N^2).

Учитывая, что из него извлекается только одно значение, оно должно бытьможно сделать его без сохранения состояния и использовать один предварительно выделенный экземпляр.

Кроме того, вместо итерации по ключам и оплаты ненужных затрат на поиск в самом внутреннем цикле (сохраняя O(N^2) поисков), вы можете просто выполнить итерацию с for k,v in d.items():.

И, наконец, я почти уверен (для уверенности, что нужно увидеть код SequenceMatcher), можно делать то, что вам нужно, лучше, чем в O(N^2) (по крайней мере,как O(N log(N))).