python – 序列化有向加权图
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了python – 序列化有向加权图,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3564字,纯文字阅读大概需要6分钟。
内容图文
我有一个有向加权图.图的每个节点表示为2元组,其第一个元素是节点的名称,其第二个元素是包含源自此节点的所有顶点的元组,按其权重排序.基本上每个顶点的权重是它在该元组内的索引.
免责声明:
a = ('A', () )
a是名称为A的节点,其中没有顶点.
b = ('B', () )
a = ('A', (b,) )
a是名为A的节点,其中一个顶点指向名为B的节点,权重为0.
b = ('B', () )
c = ('C', () )
a = ('A', (b, c) )
a是名为A的节点,其中两个顶点指向名为B和C的节点,第一个是权重0,第二个是权重1.
很明显(‘A’,(b,c))不等于(‘A’,(c,b)).
现在我需要根据这些规则序列化这个图:
>结果的第一个元素是起始节点.
>然后按照权重递增的顺序跟随从起始节点直接可访问的所有节点.如果节点已经在结果中,请不要再次附加它.
>现在递归地将规则一和二应用于刚刚添加的所有元素.
基本上,从低到高(重量)第一,深度第二.
这里有一个示例输入和输出:
f = ('F', () )
e = ('E', () )
d = ('D', (e,) )
c = ('C', (f, d, e) )
b = ('B', (d,) )
a = ('A', (b, c) )
结果是:
['A', 'B', 'C', 'D', 'F', 'E']
现在我的第一个天真的方法是:
def serialize (node):
acc = []
def serializeRec (node, level):
tbd = [] #acc items to be deleted
tbi = False #insertion index
for idx, item in enumerate (acc):
if item [1] > level and tbi == False:
tbi = idx
if item [0] == node [0]:
if item [1] > level: tbd.append (item)
else: break
else:
if tbi == False: acc.append ( (node [0], level) )
else: acc.insert (tbi, (node [0], level) )
for item in tbd:
acc.remove (item)
for vertex in node [1]:
serializeRec (vertex, level + 1)
serializeRec (node, 0)
#remove levels
return [node for node, level in acc]
这显然是一个非常糟糕的主意,因为在每次递归中我都会迭代各种列表.这就是我切换到字典的原因:
def serializeDict (node):
levels = defaultdict (list) #nodes on each level
nodes = {} #on which level is which node
def serializeRec (node, level):
try:
curLevel = nodes [node [0] ]
if curLevel > level:
nodes [node [0] ] = level
levels [curLevel].remove (node [0] )
levels [level].append (node [0] )
except:
nodes [node [0] ] = level
levels [level].append (node [0] )
for vertex in node [1]:
serializeRec (vertex, level + 1)
serializeRec (node, 0)
#flatten dict items
return [node for level in (v for _, v in sorted (levels.items (), key = lambda x: x [0] ) ) for node in level]
除非常小的图表,其运行速度要快得多.
我现在的问题是:
如何以最小化运行时的目标优化此序列化?
内存使用无关紧要(是的,宝贝),KLOC无关紧要,只有运行时间.除输入数据的格式外,一切都可以更改.但如果最后节省时间,我很乐意在序列化功能中重新组织这些数据.
我非常感谢你阅读这篇TL; DR墙的文字.
鬼混的示例图:
z = ('Z', () ); y = ('Y', (z,) ); x = ('X', (z, y) ); w = ('W', (x, y, z) ); v = ('V', (w, x) ); u = ('U', (w, v) ); t = ('T', (u, w) ); s = ('S', (z, v, u) ); r = ('R', (t, u, z) ); q = ('Q', (r, z) ); p = ('P', (w, u) ); o = ('O', (v, r, q) ); n = ('N', (r, z) ); m = ('M', (t,) ); l = ('L', (r,) ); k = ('K', (x, v) ); j = ('J', (u,) ); i = ('I', (n, k) ); h = ('H', (k, x) ); g = ('G', (l,) ); f = ('F', (t, m) ); e = ('E', (u,) ); d = ('D', (t, e, v) ); c = ('C', (m,) ); b = ('B', (n,) ); a = ('A', (g, m, v) )
解决方法:
这可以在没有递归的情况下工作,并使用双端队列来提高效率:
from collections import deque
def serialize_plain(n):
name, children = n
output = [name]
candidates = deque(children)
while candidates:
cname, cchildren = candidates.popleft()
if cname not in output:
output.append(cname)
candidates.extend(cchildren)
return output
根据图表的大小,保留已经处理的一组节点以避免昂贵的列表查询可能是有意义的:
from collections import deque
def serialize_with_set(n):
name, children = n
output = [name]
done = {name}
candidates = deque(children)
while candidates:
cname, cchildren = candidates.popleft()
if cname not in done:
output.append(cname)
done.add(cname)
candidates.extend(cchildren)
return output
内容总结
以上是互联网集市为您收集整理的python – 序列化有向加权图全部内容,希望文章能够帮你解决python – 序列化有向加权图所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。