Как преодолеть вложенность l oop для достижения линейной временной сложности? - PullRequest
Новая
       18

Как преодолеть вложенность l oop для достижения линейной временной сложности?

0 голосов
/ 27 мая 2020

Прежде всего этот код сравнивает два словаря и помещает их в один больший словарь. 1. Если у него один и тот же ключ, поместите значение из двух словарей в один ключ. 2. Если у него есть похожий ключ (например, банан и банан4), также поместите значение из двух словарей в один ключ и удалите его. 3. Наконец, если он имеет другое значение, чем поместите значение в соответствии с ключом исходного словаря. 

import pandas as pd
from fuzzywuzzy import fuzz

dict1 = {'apple' : 'g1', 'banana' : 'g2', 'mango' : 'g3'}
dict2 = {'apple' : 'a3', 'banana' : 'a4', 'grapes' : 'a1', 'pear' : 'a2', 'banan4' : 'a5'}

merged = {}
blocked_tuple = (dict1, dict2)
threshold = 59

for new_dict in blocked_tuple:
    for key in new_dict:
        flag = True
        if key in merged:
            merged[key].append(new_dict[key])
            flag = False
        else:
            merged[key] = [new_dict[key]]
        while flag:
            try:
                for i in merged:
                    distance = fuzz.token_set_ratio(key, i)
                    if (distance > threshold) and (distance != 100):
                        merged.pop(key)
                        merged[i].append(new_dict[key])
                        flag = False
                    else: flag = False
            except: pass

print(merged)

Этот код выведет: 

{'apple': ['g1', 'a3'], 'banana': ['g2', 'a4', 'a5'], 'mango': ['g3'], 'grapes': ['a1'], 'pear': ['a2']}

Что именно Я хотел. Однако в гораздо большем словаре эта программа могла бы работать постоянно. Есть ли способ создать новую функцию с линейной временной сложностью с тем же выходом, который я показал выше

1 Ответ

0 голосов
/ 27 мая 2020

вы можете несколько решить эту проблему, сначала отсортировав на основе некоторой эвристики c. 

from fuzzywuzzy import fuzz
dict1 = {'apple' : 'g1', 'banana' : 'g2', 'mango' : 'g3'}
dict2 = {'apple' : 'a3', 'banana' : 'a4', 'grapes' : 'a1', 'pear' : 'a2', 'banan4' : 'a5'}

merged = {}
threshold = 59
# the heuristic being sorted strings may be closer together
# this is not a perfect solution
keys = sorted(set(dict1.keys()).union(dict2.keys()))
# another heuristic could be you can sort on the freq dict. using Counter.
key_groups = []
i = 0
# you can try to group keys before merging
while i < len(keys) - 1:
    j = i
    dist = lambda :fuzz.token_set_ratio(keys[i], keys[j])
    while dist() > 59:
        j+=1
    key_groups.append(set(keys[i:j]))
    i=j
print(key_groups)
for key_group in key_groups:
    key = key_group.pop()
    val_set = merged.setdefault(key, set())
    for key in key_group.union([key]):
        if key in dict1:
            val_set.add(dict1[key])
        if key in dict2:
            val_set.add(dict2[key])
print(merged)

╰─➤  python3 snippet.py
[{'apple'}, {'banana', 'banan4'}, {'grapes'}, {'mango'}]
{'apple': {'g1', 'a3'}, 'banana': {'g2', 'a5', 'a4'}, 'grapes': {'a1'}, 'mango': {'g3'}}

Это может привести к снижению nlogn на практике, если ключи хорошо сочетаются с вашей эвристией сортировки c

...