Ξέν*_*νος 5 python recursion dictionary nested python-3.x
我有一个复杂的嵌套字典，结构如下：
example = {
('rem', 125): {
('emo', 35): {
('mon', 133): {
('ony', 33): 0
},
('mor', 62): {
('ore', 23): 0
},
('mot', 35): {
('ote', 22): 0
},
('mos', 29): {
('ose', 29): 0
}
},
('emi', 32): {
('min', 109): {
('ine', 69): 0
},
('mit', 58): {
('ite', 64): 0,
('ity', 45): 0
}
},
('eme', 26): {
('mer', 68): {
('ere', 24): 0,
('ery', 20): 0
}
}
},
('iro', 30): {
('ron', 27): {
('oni', 94): {
('nic', 205): 0
},
('one', 47): {
('ned', 86): 0,
('ner', 85): 0,
('nes', 26): 0,
('net', 20): 0
},
('ona', 44): {
('nal', 246): 0
}
}
},
('det', 122): {
('ete', 53): {
('ter', 212): {
('ery', 72): 0,
('era', 35): 0
},
('ten', 65): {
('ene', 21): 0
}
}
},
('uni', 217): {
('nin', 62): {
('ine', 32): {
('ned', 88): 0,
('ner', 74): 0,
('net', 25): 0
}
},
('nim', 31): {
('ima', 50): {
('mal', 23): 0
}
},
('niv', 25): {
('ive', 28): {
('ver', 48): 0
}
}
},
('nat', 66): {
('ati', 21): {
('tiv', 517): {
('ive', 821): 0
},
('tin', 230): {
('ine', 134): 0,
('ina', 22): 0
},
('tic', 187): {
('ice', 23): 0
},
('tis', 129): {
('ise', 25): 0
},
('tiz', 59): {
('ize', 100): 0
},
('tit', 52): {
('ite', 60): 0
},
('tif', 43): {
('ify', 30): 0
},
('til', 25): {
('ile', 79): 0,
('ily', 37): 0
}
}
},
('mar', 286): {
('ari', 30): {
('rin', 156): {
('ine', 168): 0,
('ina', 24): 0
},
('ris', 146): {
('ise', 31): 0
},
('rit', 119): {
('ite', 174): 0,
('ity', 118): 0
},
('ril', 63): {
('ily', 88): 0
},
('riz', 56): {
('ize', 134): 0
},
('ric', 30): {
('ice', 25): 0
},
('rid', 25): {
('ide', 49): 0
},
('rif', 24): {
('ify', 32): 0
}
},
('ara', 21): {
('rac', 84): {
('acy', 60): 0,
('ace', 33): 0
},
('rat', 76): {
('ate', 451): 0
},
('rag', 56): {
('age', 90): 0
},
('rad', 47): {
('ade', 36): 0
}
}
},
('ref', 153): {
('efo', 27): dict()
},
('gen', 150): {
('ene', 56): {
('nes', 644): {
('ese', 33): 0
},
('ner', 118): {
('ery', 37): 0
}
},
('eni', 25): {
('nit', 112): {
('ite', 200): 0,
('ity', 93): 0
},
('nin', 59): {
('ine', 54): 0
},
('niz', 33): {
('ize', 178): 0
}
}
},
('pol', 384): {
('oly', 255): dict(),
('oli', 35): {
('lit', 234): {
('ity', 698): 0,
('ite', 209): 0
},
('lis', 79): {
('ise', 28): 0
},
('lin', 72): {
('ine', 206): 0
},
('lid', 36): {
('ide', 21): 0
},
('lif', 24): {
('ify', 21): 0
},
('liz', 22): {
('ize', 209): 0
}
},
('ola', 22): {
('lat', 165): {
('ate', 422): 0
},
('lar', 48): {
('ary', 106): 0
},
('lan', 27): {
('ane', 24): 0
}
},
('ole', 22): {
('len', 60): {
('ene', 58): 0
},
('ler', 39): {
('ery', 36): 0
}
}
},
('lam', 117): {
('ame', 33): {
('mer', 46): {
('ere', 24): 0,
('ery', 20): 0
}
}
},
('mal', 213): {
('ala', 64): {
('lac', 67): {
('ace', 32): 0
},
('lan', 65): {
('ane', 24): 0
},
('lat', 58): {
('ate', 422): 0
},
('lar', 31): {
('ary', 106): 0
}
},
('ale', 37): {
('len', 90): {
('ene', 58): 0
},
('ler', 26): {
('ery', 36): 0
}
}
},
('rev', 156): {
('eve', 76): {
('ver', 139): {
('ery', 27): 0
},
('vel', 36): {
('ely', 168): 0
}
},
('evi', 44): {
('vit', 27): {
('ity', 64): 0
}
},
('evo', 28): dict()
},
('ura', 42): {
('ran', 25): {
('ani', 91): {
('nic', 76): 0
}
}
},
('val', 78): {
('ale', 28): {
('len', 90): {
('ene', 58): 0
},
('ler', 26): {
('ery', 36): 0
}
}
},
('ven', 111): {
('ene', 26): {
('nes', 644): {
('ese', 33): 0
},
('ner', 118): {
('ery', 37): 0
}
}
},
('lat', 106): {
('ati', 39): {
('tiv', 517): {
('ive', 821): 0
},
('tin', 230): {
('ine', 134): 0,
('ina', 22): 0
},
('tic', 187): {
('ice', 23): 0
},
('tis', 129): {
('ise', 25): 0
},
('tiz', 59): {
('ize', 100): 0
},
('tit', 52): {
('ite', 60): 0
},
('tif', 43): {
('ify', 30): 0
},
('til', 25): {
('ile', 79): 0,
('ily', 37): 0
}
},
('ate', 27): {
('ter', 153): {
('ery', 72): 0,
('era', 35): 0
},
('tel', 117): {
('ely', 112): 0
},
('ten', 74): {
('ene', 21): 0
}
}
},
('aci', 42): {
('cid', 21): {
('idi', 49): {
('dic', 20): 0
},
('ida', 43): {
('dal', 118): 0
},
('ide', 43): {
('der', 40): 0,
('des', 38): 0,
('ded', 20): 0
}
}
}
}
它只是复杂对象的一小部分，我发布了如此复杂的示例来表明该对象到底有多复杂，完整的对象从示例的第一层开始可以有多达 15 个嵌套级别，并且第一个还有更多级别键。
让我解释一下这是什么，这是用于基于马尔可夫链的伪词生成中，每个键是一个由三个字母字符串和一个正整数组成的元组，该字符串要么由元音字母，要么由辅音字母组成和一个元音字母或 CVC。
该字符串是一个三字母状态，整数表示该状态的权重/似然/频率，连续级别的每个键都是一个可以跟随前一级别状态的状态，一个状态只能跟随另一个状态当且仅当另一个状态的最后两个字母是第一个状态的开始，数字是从前一个状态转换到下一个状态的可能性。
第一级状态是可以在单词开头找到的状态，第二级状态是在单词中跟随先前第一状态作为第二状态的状态。每个最后一层的值应该是0，表示嵌套结束，在示例中，如果第一个嵌套层的嵌套值为 0，并且每个后续嵌套层的嵌套值加 1，则最后一个嵌套层的嵌套值加 3（长度第一个状态）应该是六（通过遍历树生成的单词的长度应该是）。
一个单词是通过加权随机选择一个状态来生成的，加权随机从它的值中选择一个状态，递归地直到该值为零，然后，取出第一个状态的所有字母，从第二个字母开始的第三个字母说明并连接字母。
例如，如果选择是 ('uni', 'nin', 'ine', 'ned')，则要采用的块是'uni', 'n', 'e', 'd'，生成的单词是'unined'。
现在我有三个问题，第一个问题是字典没有排序，这是最容易解决的。第二个是字典有空的嵌套字典，这些字典意味着分支过早终止，因为分支不能“合法”增长，这些分支无效，我想从最后一层到第一层递归地切断无效分支level（从最后一级到第一级，如果值字典为空，则递归地向后弹出键，直到值不再为空），这个有点困难。
最困难的部分是，有很多分支只有一个子分支，我需要递归地将这些子分支与其父分支合并，从最后一层向后到第一层。
简而言之，我需要它变成这样：
{
('acid', 42): {
('idal', 43): 0,
('ide', 43): {
('ded', 20): 0,
('der', 40): 0,
('des', 38): 0
},
('idic', 49): 0
},
('dete', 122): {
('tene', 65): 0,
('ter', 212): {
('era', 35): 0,
('ery', 72): 0
}
},
('gen', 150): {
('ene', 56): {
('nery', 118): 0,
('nese', 644): 0
},
('eni', 25): {
('nine', 59): 0,
('nit', 112): {
('ite', 200): 0,
('ity', 93): 0
},
('nize', 33): 0
}
},
('iron', 30): {
('onal', 44): 0,
('one', 47): {
('ned', 86): 0,
('ner', 85): 0,
('nes', 26): 0,
('net', 20): 0
},
('onic', 94): 0
},
('lamer', 117): {
('ere', 24): 0,
('ery', 20): 0
},
('lat', 106): {
('ate', 27): {
('tely', 117): 0,
('tene', 74): 0,
('ter', 153): {
('era', 35): 0,
('ery', 72): 0
}
},
('ati', 39): {
('tice', 187): 0,
('tify', 43): 0,
('til', 25): {
('ile', 79): 0,
('ily', 37): 0
},
('tin', 230): {
('ina', 22): 0,
('ine', 134): 0
},
('tise', 129): 0,
('tite', 52): 0,
('tive', 517): 0,
('tize', 59): 0
}
},
('mal', 213): {
('ala', 64): {
('lace', 67): 0,
('lane', 65): 0,
('lary', 31): 0,
('late', 58): 0
},
('ale', 37): {
('lene', 90): 0,
('lery', 26): 0
}
},
('mar', 286): {
('ara', 21): {
('rac', 84): {
('ace', 33): 0,
('acy', 60): 0
},
('rade', 47): 0,
('rage', 56): 0,
('rate', 76): 0
},
('ari', 30): {
('rice', 30): 0,
('ride', 25): 0,
('rify', 24): 0,
('rily', 63): 0,
('rin', 156): {
('ina', 24): 0,
('ine', 168): 0
},
('rise', 146): 0,
('rit', 119): {
('ite', 174): 0,
('ity', 118): 0
},
('rize', 56): 0
}
},
('nati', 66): {
('tice', 187): 0,
('tify', 43): 0,
('til', 25): {
('ile', 79): 0,
('ily', 37): 0
},
('tin', 230): {
('ina', 22): 0,
('ine', 134): 0
},
('tise', 129): 0,
('tite', 52): 0,
('tive', 517): 0,
('tize', 59): 0
},
('pol', 384): {
('ola', 22): {
('lane', 27): 0,
('lary', 48): 0,
('late', 165): 0
},
('ole', 22): {
('lene', 60): 0,
('lery', 39): 0
},
('oli', 35): {
('lide', 36): 0,
('lify', 24): 0,
('line', 72): 0,
('lise', 79): 0,
('lit', 234): {
('ite', 209): 0,
('ity', 698): 0
},
('lize', 22): 0
}
},
('rem', 125): {
('emer', 26): {
('ere', 24): 0,
('ery', 20): 0
},
('emi', 32): {
('mine', 109): 0,
('mit', 58): {
('ite', 64): 0,
('ity', 45): 0
}
},
('emo', 35): {
('mony', 133): 0,
('more', 62): 0,
('mose', 29): 0,
('mote', 35): 0
}
},
('rev', 156): {
('eve', 76): {
('vely', 36): 0,
('very', 139): 0
},
('evity', 44): 0
},
('uni', 217): {
('nimal', 31): 0,
('nine', 62): {
('ned', 88): 0,
('ner', 74): 0,
('net', 25): 0
},
('niver', 25): 0
},
('uranic', 42): 0,
('vale', 78): {
('lene', 90): 0,
('lery', 26): 0
},
('vene', 111): {
('nery', 118): 0,
('nese', 644): 0
}
}
我是这样做的：
def merge(obj):
for k, v in list(obj.items()):
if isinstance(v, dict):
merge(v)
if len(v) == 1:
a, b = k
k1, v1 = list(obj.pop(k).items())[0]
key = (a + k1[0][2:], b)
obj[key] = v1
def pop_empty(obj):
for k, v in list(obj.items()):
if isinstance(v, dict):
pop_empty(v)
if not v:
obj.pop(k)
def nested_sort(dic):
d = dict()
for k, v in sorted(dic.items()):
if isinstance(v, dict):
d[k] = nested_sort(v)
else:
d[k] = v
return d
pop_empty(example)
merge(example)
nested_sort(example)
我需要处理一个比这复杂得多的极其复杂的对象，有什么更有效的方法来做到这一点？
该对象有许多重复的元素和重复的嵌套字典，一般来说，重复非常重，记忆化是一个巨大的帮助，但是其中两个函数不返回任何值，而一个函数返回一个值，尝试使用 lru_cache 包装它会引发unhashable type dict，任何人都可以使用记忆法重新实现相同的想法吗？
通过结合这三个过程，我的速度提高了约 25%。
def merge(obj, /):
result = {}
for key, val in sorted(obj.items()):
if isinstance(val, dict):
val = merge(val)
if not val:
continue
if len(val) == 1:
k1, val = next(iter(val.items()))
key = (key[0] + k1[0][2:], key[1])
result[key] = val
return result
我不知道还有多少可能。
| 归档时间： |
|
| 查看次数： |
881 次 |
| 最近记录： |