python – 序列化有向加权图
我有一个有向加权图.图的每个节点表示为2元组,其第一个元素是节点的名称,其第二个元素是包含源自此节点的所有顶点的元组,按其权重排序.基本上每个顶点的权重是它在该元组内的索引.
免责声明: a = ('A',() ) a是名称为A的节点,其中没有顶点. b = ('B',() ) a = ('A',(b,) ) a是名为A的节点,其中一个顶点指向名为B的节点,权重为0. b = ('B',() ) c = ('C',c) ) a是名为A的节点,其中两个顶点指向名为B和C的节点,第一个是权重0,第二个是权重1. 很明显(‘A’,c))不等于(‘A’,(c,b)). 现在我需要根据这些规则序列化这个图: >结果的第一个元素是起始节点. 基本上,从低到高(重量)第一,深度第二. 这里有一个示例输入和输出: f = ('F',() ) e = ('E',() ) d = ('D',(e,) ) c = ('C',(f,d,e) ) b = ('B',(d,) ) a = ('A',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,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',y) ); w = ('W',(x,y,z) ); v = ('V',(w,x) ); u = ('U',v) ); t = ('T',(u,w) ); s = ('S',v,u) ); r = ('R',(t,u,z) ); q = ('Q',(r,z) ); p = ('P',u) ); o = ('O',(v,r,q) ); n = ('N',z) ); m = ('M',) ); l = ('L',) ); k = ('K',v) ); j = ('J',) ); i = ('I',(n,k) ); h = ('H',(k,x) ); g = ('G',(l,) ); f = ('F',m) ); e = ('E',) ); d = ('D',e,v) ); c = ('C',(m,) ); b = ('B',) ); 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 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |