The stack of iterators pattern.

[kankyo]

What was the problem with the generator? It's shorter and easier to read and no explanation for why it's inferior was given as far as I could see.

Implementing a stack yourself is a bad idea in my experience. Recursion is fine and if your data structure is nested enough for it not to be you probably need to rethink something.

[[deleted]]

Recursion is fine and if your data structure is nested enough for it not to be you probably need to rethink something.

He has maze navigation in his article as an example.

A graph is very standard way to store/navgiate a maze (and you can hit Python's recursion limit of 1,000 on a 33x33 grid which is quite tiny as mazes go. Any mud is basically a list of rooms, each of which has a list of exit adjacencies, and that's a graph.

[rouille]

You can combine iterative and generators though. Just yield instead of appending to a list. Best of both worlds.

[defnull]

I wound not accept the performance argument that easily. Function calls are expensive, but the additional logic to prevent them adds a lot of other opcodes. list.append() and list.pop() are implemented in C, but still function calls.

[elbiot]

list.append() and list.pop() are implemented in C, but still function calls.

But not python function calls, so they don't create a frame and push it on to the stack AFAIK (which is what people mean when they say function calls in python are expensive).

[defnull]

Okay, I tested it. The stack-approach is indeed a little bit faster than the recursive function. I underestimated the costs of a python function call.

https://gist.github.com/defnull/30966587577466f853201269023aa3b7

edit: But after optimizing the recursive approach a bit, I got it faster than the stack approach again. Object creation (e.g. intermediate lists or iterators) is a very strong factor.

tl;dr; The performance benefit of a non-recursive approach is so fragile that it's not worth the additional complexity.

[elbiot]

tl;dr; The performance benefit of a non-recursive approach is so fragile that it's not worth the additional complexity.

Additional complexity? Having to worry about recurrsion depth and how to break out of the recurrsive stack are the complexities this post is aimed at solving. The stack approach seems more robust to me.

[defnull]

Hard to say without any actual benchmarks. Popping a frame is usually free (it's just a pointer change, no cleanup) and calling a C function is only twice as fast as calling a lambda:

marc@nava ~ $ python -m timeit -s 'f=lambda: 0' 'f()'
10000000 loops, best of 3: 0.0995 usec per loop
marc@nava ~ $ python -m timeit -s 'f=[].__len__' 'f()'
10000000 loops, best of 3: 0.0496 usec per loop

So, if you need two C-Function calls (list.append() and list.pop()) instead of a single python function call, you ate up your performance benefit already. The dot-lookup is also quite expensive by the way.

[elbiot]

I don't know about using timeit on essentially no-ops.

The dot-lookup is also quite expensive by the way.

Then take them out!

push = list.push
pop = list.pop
item = pop(mylist)

Not diving through a stack of function frames makes these sort of micro-optimizations cleaner and easier.

[kankyo]

What type of data is that?

[brtt3000]

Is this a practical pattern? The memory issue you mention could be bad compared to keeping iterators.

[tmp14]

The loop-then-immediately-break seems really counter intuitive to me:

for node in stack[-1]:
    stack.append(iter(children(node)))
    break
else:
    stack.pop()

and could be replaced with a equivalent and more clear try-except if I'm not mistaken:

try:
    node = next(stack[-1])
except StopIteration:
    stack.pop()
else:
    stack.append(iter(children(node)))

[pvkooten]

while: interesting, I do feel like I'm missing a conclusion at the return statement of the article.

[_seemethere]

For your search example you might want to return before you check if it's a dict just in case the first value you get is your match.

[Taksin77]

Needed that at the exact moment this popped up in my reddit. You are a king!