我发现当参数并不太多时,从性能的角度来看,没必要用一个class来保存参数(虽然看起来更加生动形象),直接用最简单的元组就可以了.
from hanoi import *
# example trees for test...
trees=[]
trees.append(None)
trees.append([1,None,None])
trees.append([1,None,[2,None,None]])
trees.append([1,[3,[4,None,None],None],[600,None,None]])
trees.append([1,[3,[4,None,None],[6,None,None]],[2,[5,None,None],[7,None,None]]])
trees.append([10,[6,[8,None,None],[12,None,None]],[11,None,[15,None,None]]])
trees.append([10,[6,[8,[11,None,[15,None,None]],None],[12,None,None]],[10,[6,[8,None,None],[12,None,None]],[11,None,[15,None,None]]]]) # helper functions to build a valid preorder or inorder list from a tree
def _pre(tree):
if tree:
yield tree[0]
yield from _pre(tree[1])
yield from _pre(tree[2])
def _ino(tree):
if tree:
yield from _ino(tree[1])
yield tree[0]
yield from _ino(tree[2])
def pre(tree):
return list(_pre(tree))
def ino(tree):
return list(_ino(tree)) def make(prd,ind):
if prd and ind:
root = prd[0]
root_pos = ind.index(root)
ind_left= ind[:root_pos]
ind_right = ind[root_pos+1:]
cut = len(ind_left)+1
prd_left = prd[1:cut]
prd_right = prd[cut:]
left = make(prd_left,ind_left)
right = make(prd_right,ind_right)
return [root,left,right] def xmake(prd,ind):
stacks=[Stack(stg=0,prd=prd,ind=ind)]
while stacks:
c = stacks.pop()
if c.stg==0:
c.stg=1
if c.prd and c.ind:
root=c.prd[0]
c.tree_list=[root]
root_pos = c.ind.index(root)
ind_left = c.ind[:root_pos]
cut = len(ind_left)+1
prd_left = c.prd[1:cut]
c.ind_right = c.ind[root_pos+1:]
c.prd_right = c.prd[cut:]
stacks.append(c)
stacks.append(Stack(stg=0,prd=prd_left,ind=ind_left))
else:
res = None
elif c.stg==1:
c.stg=2
c.tree_list.append(res)
stacks.append(c)
stacks.append(Stack(stg=0,prd=c.prd_right,ind=c.ind_right))
elif c.stg==2:
c.tree_list.append(res)
res=c.tree_list
return res def ymake(prd,ind):
stacks=[(0,prd,ind,None,None,None,)]
while stacks:
stg,prd,ind,tree_list,prd_right,ind_right = stacks.pop()
if stg==0:
if prd and ind:
root=prd[0]
tree_list=[root]
root_pos = ind.index(root)
ind_left = ind[:root_pos]
cut = len(ind_left)+1
prd_left = prd[1:cut]
ind_right = ind[root_pos+1:]
prd_right = prd[cut:]
stacks.append((1,None,None,tree_list,prd_right,ind_right,))
stacks.append((0,prd_left,ind_left,None,None,None,))
else:
res = None
elif stg==1:
tree_list.append(res)
stacks.append((2,None,None,tree_list,None,None,))
stacks.append((0,prd_right,ind_right,None,None,None,))
elif stg==2:
tree_list.append(res)
res=tree_list
return res if __name__=='__main__':
for tree in trees:
preorder = pre(tree)
inorder = ino(tree)
compare(1,10000,make,xmake,ymake,prd=preorder,ind=inorder)
时间消耗情况"
>>>
1 groups, 10000 times
make best time: 0.005802598746597618
xmake best time: 0.040378714824230735
ymake best time: 0.010430907850763435
1 groups, 10000 times
make best time: 0.023853132543773928
xmake best time: 0.15266406806261454
ymake best time: 0.06813018108264718
1 groups, 10000 times
make best time: 0.061869156080883114
xmake best time: 0.29423481944120744
ymake best time: 0.14889103182256502
1 groups, 10000 times
make best time: 0.09127643060422885
xmake best time: 0.4971307733591055
ymake best time: 0.22370901906617036
1 groups, 10000 times
make best time: 0.15408382101704765
xmake best time: 0.8039180049905172
ymake best time: 0.37127052922146664
1 groups, 10000 times
make best time: 0.1331591427600083
xmake best time: 0.6996409992152874
ymake best time: 0.32450677483017465
1 groups, 10000 times
make best time: 0.2689833157646033
xmake best time: 1.3633301759510097
ymake best time: 0.6343635807709003