Nested Generator Performance - Printable Version

Nested Generator Performance - Printable Version

+- Python Forum (https://python-forum.io)
+-- Forum: Forum & Off Topic (https://python-forum.io/forum-23.html)
+--- Forum: Board (https://python-forum.io/forum-26.html)
+--- Thread: Nested Generator Performance (/thread-4381.html)

Nested Generator Performance - micseydel - Aug-12-2017

(Even though this is still Python, it's not really a question, or any other section, so here I am.)

I often give an interview question to flatten a nested structure, such as [1, 2, [3, [4]], 5]. To do it "greedily" it trivial for most people, but to do it "lazily" is often more of a challenge (especially in other languages). I received a solution like this recently:

def flatten(a):
    for el in a:
        if type(el) == list:
            for el1 in flatten(el):
                yield el1
        else:
            yield el

Until this week, this was basically the solution I always wanted. Sure, isinstance might be preferred, and yield from, and maybe you even want some way to handle iterables other than lists, but the gist of it is there. Right?

Compare it to something like this

def flatten(x):
    stack = [iter(x)]
    while stack:
        try:
            e = next(stack[-1])
        except StopIteration:
            stack.pop()
        else:
            if isinstance(e, list):
                stack.append(iter(e))
            else:
                yield e

That looks so noisy, right? The first one being definitely better?

I'm curious what others thoughts' are on this, and please think about it a bit before checking the spoiler...

Hide/Show

from time import time

import sys
sys.setrecursionlimit(10000) # overly liberal


def flatten_recursive(x):
    for e in x:
        if isinstance(e, list):
            yield from flatten_recursive(e)
        else:
            yield e

def flatten_iterative(x):
    stack = [iter(x)]
    while stack:
        try:
            e = next(stack[-1])
        except StopIteration:
            stack.pop()
        else:
            if isinstance(e, list):
                stack.append(iter(e))
            else:
                yield e


def generate(depth, inner_size=100000):
    result = list(range(inner_size))
    for _ in range(depth):
        result = [result]
    return result

for f in (flatten_recursive, flatten_iterative):
    print(f.__name__)
    for depth in (100, 200, 500, 1000, 2000, 4000):
        structure = generate(depth)

        print("  Depth =", depth, end=" ")
        start = time() # crude, but fine for this
        list(f(structure)) # unpack it
        duration = time() - start
        print(" ... took {:.2f} seconds".format(duration))

Output:$ python3 testit.py
flatten_recursive
  Depth = 100  ... took 0.68 seconds
  Depth = 200  ... took 1.41 seconds
  Depth = 500  ... took 4.10 seconds
  Depth = 1000  ... took 8.18 seconds
  Depth = 2000  ... took 17.06 seconds
  Depth = 4000  ... took 36.99 seconds
flatten_iterative
  Depth = 100  ... took 0.04 seconds
  Depth = 200  ... took 0.04 seconds
  Depth = 500  ... took 0.04 seconds
  Depth = 1000  ... took 0.04 seconds
  Depth = 2000  ... took 0.04 seconds
  Depth = 4000  ... took 0.04 seconds

It appears that the way Python handles stacks from recursive generators requires it to start at the beginning of the stack and work its way to the top (also known as stack[-1]). I was hoping that yield from might be smart enough to do magic, but it seems that it causes the shorter solution here to be O(n * d) instead of something more like O(n + d).

RE: Nested Generator Performance - nilamo - Aug-13-2017

My initial impression would be that a non-recursive version would be faster, all other things equal, because function calls are slow in python (and there's known recursion limits). But I ignored that, because I'm dumb :p
Here's what I came up with (before looking at the spoiler).

Hide/Show

test = [1, 2, [3, [4]], 5]
expected = [1, 2, 3, 4, 5]


def nilamo_flatten_greedy(items):
    items = list(items)
    flat =
    while items:
        item = items.pop(0)
        try:
            flattened = nilamo_flatten_greedy(iter(item))
            flattened.extend(items)
            items = flattened
        except TypeError:
            flat.append(item)
    return flat


def nilamo_flatten(items):
    for item in items:
        try:
            yield from nilamo_flatten(iter(item))
        except TypeError:
            yield item

greedy = list(nilamo_flatten_greedy(test))
lazy = list(nilamo_flatten(test))
print(greedy, lazy)
assert greedy == expected == lazy

After seeing your timings (and the fact that your recursive version looks nearly the same as mine), I added the timings:

Hide/Show

Output:flatten_recursive
  Depth = 100  ... took 0.35 seconds
  Depth = 200  ... took 0.71 seconds
  Depth = 500  ... took 1.87 seconds
  Depth = 1000  ... took 4.02 seconds
  Depth = 2000  ... took 8.05 seconds
  Depth = 4000  ... took 17.17 seconds
flatten_iterative
  Depth = 100  ... took 0.04 seconds
  Depth = 200  ... took 0.03 seconds
  Depth = 500  ... took 0.04 seconds
  Depth = 1000  ... took 0.04 seconds
  Depth = 2000  ... took 0.04 seconds
  Depth = 4000  ... took 0.04 seconds
nilamo_flatten
  Depth = 100  ... took 0.43 seconds
  Depth = 200  ... took 0.81 seconds
  Depth = 500  ... took 2.05 seconds
  Depth = 1000  ... took 4.18 seconds
  Depth = 2000  ... took 8.75 seconds
  Depth = 4000  ... took 17.26 seconds

I stopped timing the greedy one I wrote, since it... too 58 seconds with a depth of 100.