1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
import timeit

setup = """
def create(children, depth, d = 0):
    if depth == 1:
        return { str(i):str(i) for i in range(children[0]) }
    return { str(i):create(children[1:] if len(children) > 1 else children,
                           depth - 1, d + 1) for i in range(children[0]) }

# 300 levels of nesting, 2 children in the outher 11 levels, 1 children
# in deeper levels
a = create([2,2,2,2,2,2,2,2,2,2,2,1], 300)
# 3 levels of nesting; 100 children in outmost level, 10 in middle, 3 in innermost
b = create([100, 10, 3], 3)
# 3 levels of nesting; 3 children in outmost level, 100 in middle, 1000 in innermost
c = create([3, 100, 1000], 3)

def report(x): pass

def test1(d):
    stack = d.items()
    while stack:
        k, v = stack.pop()
        if isinstance(v, dict):
            stack.extend(v.iteritems())
        else:
            report((k, v))

def test2(d):
    iters = [d.iteritems()]

    while iters:
        it = iters.pop()
        try:
            k, v = it.next()
        except StopIteration:
            continue

        iters.append(it)

        if isinstance(v, dict):
            iters.append(v.iteritems())
        else:
            report((k, v))

def test3(d):
    for k, v in d.iteritems():
        if isinstance(v, dict):
            test3(v)
        else:
            report((k, v))
"""

print "Dictionary a"
print timeit.timeit("test1(a)", setup=setup, number=5)
print timeit.timeit("test2(a)", setup=setup, number=5)
print timeit.timeit("test3(a)", setup=setup, number=5)
print "Dictionary b"
print timeit.timeit("test1(b)", setup=setup, number=5)
print timeit.timeit("test2(b)", setup=setup, number=5)
print timeit.timeit("test3(b)", setup=setup, number=5)
print "Dictionary c"
print timeit.timeit("test1(c)", setup=setup, number=5)
print timeit.timeit("test2(c)", setup=setup, number=5)
print timeit.timeit("test3(c)", setup=setup, number=5)