Skip to content

Instantly share code, notes, and snippets.

@haizaar
Last active August 29, 2015 14:17
Show Gist options
  • Save haizaar/a3cda2dc17a814f08aa5 to your computer and use it in GitHub Desktop.
Save haizaar/a3cda2dc17a814f08aa5 to your computer and use it in GitHub Desktop.
dictionary tree traversal with path keeping
inline: 0.388133 seconds
iterate_tree: 0.772798
iterate_tree2: 0.707333
iterate_tree3: 0.564626
iterate_tree3_noyield: 0.498388
iterate_tree3_nofeedback: 0.353944
iterate_tree5: 0.650102
iterate_tree5_noyield: 0.566557
iterate_tree5_nofeedback: 0.435601
iterate_tree6: 0.562908
iterate_tree6_noyield: 0.657400
iterate_tree6_nofeedback: 0.495867
===================
inline: 0.373992 seconds
iterate_tree: 0.785275
iterate_tree2: 0.733026
iterate_tree3: 0.568669
iterate_tree3_noyield: 0.478942
iterate_tree3_nofeedback: 0.349861
iterate_tree5: 0.666957
iterate_tree5_noyield: 0.561710
iterate_tree5_nofeedback: 0.436763
iterate_tree6: 0.556949
iterate_tree6_noyield: 0.661005
iterate_tree6_nofeedback: 0.505315
===================
inline: 0.371376 seconds
iterate_tree: 0.774100
iterate_tree2: 0.792793
iterate_tree3: 0.576650
iterate_tree3_noyield: 0.479125
iterate_tree3_nofeedback: 0.344007
iterate_tree5: 0.663087
iterate_tree5_noyield: 0.582382
iterate_tree5_nofeedback: 0.438463
iterate_tree6: 0.643334
iterate_tree6_noyield: 0.702786
iterate_tree6_nofeedback: 0.542529
===================
inline: 0.375493 seconds
iterate_tree: 0.775765
iterate_tree2: 0.699562
iterate_tree3: 0.559925
iterate_tree3_noyield: 0.529699
iterate_tree3_nofeedback: 0.343166
iterate_tree5: 0.639239
iterate_tree5_noyield: 0.549155
iterate_tree5_nofeedback: 0.461195
iterate_tree6: 0.543466
iterate_tree6_noyield: 0.620466
iterate_tree6_nofeedback: 0.494854
===================
inline: 0.360489 seconds
iterate_tree: 0.781050
iterate_tree2: 0.714968
iterate_tree3: 0.568337
iterate_tree3_noyield: 0.474860
iterate_tree3_nofeedback: 0.364178
iterate_tree5: 0.658812
iterate_tree5_noyield: 0.554898
iterate_tree5_nofeedback: 0.433046
iterate_tree6: 0.560966
iterate_tree6_noyield: 0.649476
iterate_tree6_nofeedback: 0.497308
===================
inline: 0.418819 seconds
iterate_tree: 0.782076
iterate_tree2: 0.994035
iterate_tree3: 0.672291
iterate_tree3_noyield: 0.602802
iterate_tree3_nofeedback: 0.438645
iterate_tree5: 0.811397
iterate_tree5_noyield: 0.704024
iterate_tree5_nofeedback: 0.555990
iterate_tree6: 0.634752
iterate_tree6_noyield: 0.708318
iterate_tree6_nofeedback: 0.548175
===================
inline: 0.431803 seconds
iterate_tree: 0.797864
iterate_tree2: 0.962760
iterate_tree3: 0.676052
iterate_tree3_noyield: 0.627296
iterate_tree3_nofeedback: 0.432995
iterate_tree5: 0.801945
iterate_tree5_noyield: 0.760071
iterate_tree5_nofeedback: 0.557158
iterate_tree6: 0.618978
iterate_tree6_noyield: 0.715398
iterate_tree6_nofeedback: 0.564163
===================
inline: 0.430824 seconds
iterate_tree: 0.790162
iterate_tree2: 0.961879
iterate_tree3: 0.685668
iterate_tree3_noyield: 0.603360
iterate_tree3_nofeedback: 0.426412
iterate_tree5: 0.801495
iterate_tree5_noyield: 0.717511
iterate_tree5_nofeedback: 0.550656
iterate_tree6: 0.615157
iterate_tree6_noyield: 0.724978
iterate_tree6_nofeedback: 0.552988
===================
inline: 0.428661 seconds
iterate_tree: 0.789669
iterate_tree2: 1.007039
iterate_tree3: 0.675401
iterate_tree3_noyield: 0.600943
iterate_tree3_nofeedback: 0.440957
iterate_tree5: 0.808624
iterate_tree5_noyield: 0.720491
iterate_tree5_nofeedback: 0.563287
iterate_tree6: 0.655150
iterate_tree6_noyield: 0.774540
iterate_tree6_nofeedback: 0.583963
===================
inline: 0.415149 seconds
iterate_tree: 0.788343
iterate_tree2: 0.962036
iterate_tree3: 0.690689
iterate_tree3_noyield: 0.592946
iterate_tree3_nofeedback: 0.468659
iterate_tree5: 0.804124
iterate_tree5_noyield: 0.709770
iterate_tree5_nofeedback: 0.601748
iterate_tree6: 0.623776
iterate_tree6_noyield: 0.714162
iterate_tree6_nofeedback: 0.562679
===================
inline: 0.271403 seconds
iterate_tree: 0.843282
iterate_tree2: 0.216329
iterate_tree3: 0.413761
iterate_tree3_noyield: 0.227204
iterate_tree3_nofeedback: 0.161373
iterate_tree5: 0.439838
iterate_tree5_noyield: 0.221589
iterate_tree5_nofeedback: 0.179010
iterate_tree6: 0.230437
iterate_tree6_noyield: 0.140812
iterate_tree6_nofeedback: 0.119887
===================
inline: 0.278680 seconds
iterate_tree: 0.803759
iterate_tree2: 0.231160
iterate_tree3: 0.398721
iterate_tree3_noyield: 0.212599
iterate_tree3_nofeedback: 0.158962
iterate_tree5: 0.439686
iterate_tree5_noyield: 0.221264
iterate_tree5_nofeedback: 0.191299
iterate_tree6: 0.215052
iterate_tree6_noyield: 0.136341
iterate_tree6_nofeedback: 0.118227
===================
inline: 0.278797 seconds
iterate_tree: 0.859108
iterate_tree2: 0.220438
iterate_tree3: 0.417627
iterate_tree3_noyield: 0.232952
iterate_tree3_nofeedback: 0.158761
iterate_tree5: 0.467679
iterate_tree5_noyield: 0.221373
iterate_tree5_nofeedback: 0.182964
iterate_tree6: 0.229962
iterate_tree6_noyield: 0.136830
iterate_tree6_nofeedback: 0.134050
===================
inline: 0.272146 seconds
iterate_tree: 0.846570
iterate_tree2: 0.216674
iterate_tree3: 0.402913
iterate_tree3_noyield: 0.208778
iterate_tree3_nofeedback: 0.173020
iterate_tree5: 0.451698
iterate_tree5_noyield: 0.242138
iterate_tree5_nofeedback: 0.192739
iterate_tree6: 0.229692
iterate_tree6_noyield: 0.135935
iterate_tree6_nofeedback: 0.123902
===================
inline: 0.271496 seconds
iterate_tree: 0.835806
iterate_tree2: 0.236507
iterate_tree3: 0.483542
iterate_tree3_noyield: 0.209482
iterate_tree3_nofeedback: 0.156664
iterate_tree5: 0.423417
iterate_tree5_noyield: 0.222805
iterate_tree5_nofeedback: 0.202381
iterate_tree6: 0.214501
iterate_tree6_noyield: 0.140129
iterate_tree6_nofeedback: 0.119652
===================
def iterate_tree(tree, depth, callback):
if depth:
for k, subtree in tree.items():
cb = partial(callback, k)
for i in iterate_tree(subtree, depth-1, cb):
yield i
else:
for k, v in tree.items():
rv = callback(k, v)
yield rv
def iterate_tree2(tree, depth, callback):
iterators = [iter(tree.items())]
args = []
while iterators:
try:
k, v = next(iterators[-1])
except StopIteration:
depth += 1
iterators.pop()
if args:
args.pop()
continue
if depth:
args.append(k)
iterators.append(iter(v.items()))
depth -= 1
else:
yield callback(*(args + [k, v]))
def iterate_tree3(tree, depth, callback, args=()):
if depth:
for k, subtree in tree.items():
for i in iterate_tree3(subtree, depth-1, callback, args+(k,)):
yield i
else:
for k, v in tree.items():
rv = callback(*(args + (k, v)))
yield rv
def iterate_tree3_noyield(tree, depth, callback, args=()):
if depth:
for k, subtree in tree.items():
iterate_tree3_noyield(subtree, depth-1, callback, args+(k,))
else:
for k, v in tree.items():
callback(*(args + (k, v)))
def iterate_tree5(node, depth, callback, path=()):
for (k, v) in node.items():
kpath = path + (k,)
if depth:
for i in iterate_tree5(v, depth-1, callback, kpath):
yield i
else:
yield callback(*(kpath + (v,)))
def iterate_tree5_noyield(node, depth, callback, path=()):
for (k, v) in node.items():
kpath = path + (k,)
if depth:
iterate_tree5_noyield(v, depth-1, callback, kpath)
else:
callback(*(kpath + (v,)))
def iterate_tree6(tree, depth, callback):
iterators = [iter(tree.items())]
args = []
while iterators:
while depth:
for k, v in iterators[-1]:
args.append(k)
iterators.append(iter(v.items()))
depth -= 1
break
else:
break
else:
for k, v in iterators[-1]:
yield callback(*(args + [k, v]))
depth += 1
del iterators[-1]
del args[-1:]
def iterate_tree6_noyield(tree, depth, callback):
iterators = [iter(tree.items())]
args = []
while iterators:
while depth:
for k, v in iterators[-1]:
args.append(k)
iterators.append(iter(v.items()))
depth -= 1
break
else:
break
else:
for k, v in iterators[-1]:
callback(*(args + [k, v]))
depth += 1
del iterators[-1]
del args[-1:]
tree = dict()
for i in range(10):
tree[i] = dict()
for j in range(10):
tree[i][j] = dict()
for k in range(10):
tree[i][j][k] = dict()
for l in range(10):
tree[i][j][k][l] = dict()
for m in range(10):
tree[i][j][k][l][m] = dict()
for n in range(10):
tree[i][j][k][l][m][n] = ["a", "b", "c", "d", "e", "f", "g"]
import time
from functools import partial
def callback(*args):
assert isinstance(args[-1], list)
def callback2(*args):
callback(*args)
start = time.time()
for k1, leafs1 in tree.items():
for k2, leafs2 in leafs1.items():
for k3, leafs3 in leafs2.items():
for k4, leafs4 in leafs3.items():
for k5, leafs5 in leafs4.items():
for k6, val in leafs5.items():
callback(k1, k2, k3, k4, k5, k6, val)
print("inline: %f seconds" % (time.time() - start))
start = time.time()
for i in iterate_tree(tree, 5, callback):
pass
print("iterate_tree: %f" % (time.time() - start))
start = time.time()
for i in iterate_tree2(tree, 5, callback):
pass
print("iterate_tree2: %f" % (time.time() - start))
start = time.time()
for i in iterate_tree3(tree, 5, callback):
pass
print("iterate_tree3: %f" % (time.time() - start))
start = time.time()
iterate_tree3_noyield(tree, 5, callback2)
print("iterate_tree3_noyield: %f" % (time.time() - start))
start = time.time()
iterate_tree3_noyield(tree, 5, callback)
print("iterate_tree3_nofeedback: %f" % (time.time() - start))
start = time.time()
for i in iterate_tree5(tree, 5, callback):
pass
print("iterate_tree5: %f" % (time.time() - start))
start = time.time()
iterate_tree5_noyield(tree, 5, callback2)
print("iterate_tree5_noyield: %f" % (time.time() - start))
start = time.time()
iterate_tree5_noyield(tree, 5, callback)
print("iterate_tree5_nofeedback: %f" % (time.time() - start))
start = time.time()
for i in iterate_tree6(tree, 5, callback):
pass
print("iterate_tree6: %f" % (time.time() - start))
start = time.time()
iterate_tree6_noyield(tree, 5, callback2)
print("iterate_tree6_noyield: %f" % (time.time() - start))
start = time.time()
iterate_tree6_noyield(tree, 5, callback)
print("iterate_tree6_nofeedback: %f" % (time.time() - start))
def iterate_tree(tree, depth, callback):
if depth:
for k, subtree in tree.items():
cb = partial(callback, k)
yield from iterate_tree(subtree, depth-1, cb)
else:
for k, v in tree.items():
rv = callback(k, v)
yield rv
def iterate_tree2(tree, depth, callback):
iterators = [iter(tree.items())]
args = []
while iterators:
try:
k, v = next(iterators[-1])
except StopIteration:
depth += 1
iterators.pop()
if args:
args.pop()
continue
if depth:
args.append(k)
iterators.append(iter(v.items()))
depth -= 1
else:
yield callback(*(args + [k, v]))
def iterate_tree3(tree, depth, callback, args=()):
if depth:
for k, subtree in tree.items():
yield from iterate_tree3(subtree, depth-1, callback, args+(k,))
else:
for k, v in tree.items():
rv = callback(*(args + (k, v)))
yield rv
def iterate_tree3_noyield(tree, depth, callback, args=()):
if depth:
for k, subtree in tree.items():
iterate_tree3_noyield(subtree, depth-1, callback, args+(k,))
else:
for k, v in tree.items():
callback(*(args + (k, v)))
def iterate_tree5(node, depth, callback, path=()):
for (k, v) in node.items():
kpath = path + (k,)
if depth:
yield from iterate_tree5(v, depth-1, callback, kpath)
else:
yield callback(*(kpath + (v,)))
def iterate_tree5_noyield(node, depth, callback, path=()):
for (k, v) in node.items():
kpath = path + (k,)
if depth:
iterate_tree5_noyield(v, depth-1, callback, kpath)
else:
callback(*(kpath + (v,)))
def iterate_tree6(tree, depth, callback):
iterators = [iter(tree.items())]
args = []
while iterators:
while depth:
for k, v in iterators[-1]:
args.append(k)
iterators.append(iter(v.items()))
depth -= 1
break
else:
break
else:
for k, v in iterators[-1]:
yield callback(*(args + [k, v]))
depth += 1
del iterators[-1]
del args[-1:]
def iterate_tree6_noyield(tree, depth, callback):
iterators = [iter(tree.items())]
args = []
while iterators:
while depth:
for k, v in iterators[-1]:
args.append(k)
iterators.append(iter(v.items()))
depth -= 1
break
else:
break
else:
for k, v in iterators[-1]:
callback(*(args + [k, v]))
depth += 1
del iterators[-1]
del args[-1:]
tree = dict()
for i in range(10):
tree[i] = dict()
for j in range(10):
tree[i][j] = dict()
for k in range(10):
tree[i][j][k] = dict()
for l in range(10):
tree[i][j][k][l] = dict()
for m in range(10):
tree[i][j][k][l][m] = dict()
for n in range(10):
tree[i][j][k][l][m][n] = ["a", "b", "c", "d", "e", "f", "g"]
import time
from functools import partial
def callback(*args):
assert isinstance(args[-1], list)
def callback2(*args):
callback(*args)
start = time.time()
for k1, leafs1 in tree.items():
for k2, leafs2 in leafs1.items():
for k3, leafs3 in leafs2.items():
for k4, leafs4 in leafs3.items():
for k5, leafs5 in leafs4.items():
for k6, val in leafs5.items():
callback(k1, k2, k3, k4, k5, k6, val)
print("inline: %f seconds" % (time.time() - start))
start = time.time()
for i in iterate_tree(tree, 5, callback):
pass
print("iterate_tree: %f" % (time.time() - start))
start = time.time()
for i in iterate_tree2(tree, 5, callback):
pass
print("iterate_tree2: %f" % (time.time() - start))
start = time.time()
for i in iterate_tree3(tree, 5, callback):
pass
print("iterate_tree3: %f" % (time.time() - start))
start = time.time()
iterate_tree3_noyield(tree, 5, callback2)
print("iterate_tree3_noyield: %f" % (time.time() - start))
start = time.time()
iterate_tree3_noyield(tree, 5, callback)
print("iterate_tree3_nofeedback: %f" % (time.time() - start))
start = time.time()
for i in iterate_tree5(tree, 5, callback):
pass
print("iterate_tree5: %f" % (time.time() - start))
start = time.time()
iterate_tree5_noyield(tree, 5, callback2)
print("iterate_tree5_noyield: %f" % (time.time() - start))
start = time.time()
iterate_tree5_noyield(tree, 5, callback)
print("iterate_tree5_nofeedback: %f" % (time.time() - start))
start = time.time()
for i in iterate_tree6(tree, 5, callback):
pass
print("iterate_tree6: %f" % (time.time() - start))
start = time.time()
iterate_tree6_noyield(tree, 5, callback2)
print("iterate_tree6_noyield: %f" % (time.time() - start))
start = time.time()
iterate_tree6_noyield(tree, 5, callback)
print("iterate_tree6_nofeedback: %f" % (time.time() - start))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment