[Chicago] Resolving lists within lists within lists within .....

[Bob Haugen]

Adam, do you have a sense of the performance tradeoffs between the
stack-based and recursive approaches, given that recursion in Python was
named as a performance problem earlier in this thread?

On Fri, Feb 19, 2016 at 9:11 AM, Adam Forsyth <adam at adamforsyth.net> wrote:

> The problem with those solutions would be performance. Both pop(0) and
> insert(0, item) are O(n) (they take an amount of time proportional to the
> length of the list), so the resulting time complexity is quadratic instead
> of linear.
>
> To fix that, you could use a collections.deque for temporary storage, then
> convert it to a list at the end.
> Here's one last approach that is stack based.  There is some clean up to
> do here for sure (I'm mutating the original list for one), but the point is
> to illustrate an approach that is not recursive.
>
> def flatten_big_list(lst):
>     stack = []
>     while(lst):
>         top = lst.pop(0)
>         while(isinstance(top,list)):
>             temp = top.pop(0)
>             if top:
>                 lst.insert(0,top)
>             top = temp
>         stack.append(top)
>     return stack
>
>
> def flatten_big_list_gen(lst):
>     while(lst):
>         top = lst.pop(0)
>         while(isinstance(top,list)):
>             temp = top.pop(0)
>             if top:
>                 lst.insert(0,top)
>             top = temp
>         yield top
>
>
> print(flatten_big_list([1, [2, [3, [4, 5]]]]))
> print(list(flatten_big_list_gen([1, [2, [3, [4, 5]]]])))
>
> Feedback is always welcome.
>
>
> On Thu, Feb 18, 2016 at 9:29 PM, Mark Graves <mgraves87 at gmail.com> wrote:
>
>> Doug,
>>
>> Also, I didn't see your question get answered.
>>
>> "The" answer to why is recursion expensive vs iteration is stack traces.
>> See Guido's answer here
>> <https://t.yesware.com/tt/6640a48a14dbdef70b47105ac6b72156559fc5a6/5ba2375237a9fdc8efa681b19014981f/d6c3025efb0710ebe9f6fa425f843d2c/plus.google.com/115212051037621986145/posts/HajXHPGN752> or
>> try it yourself as mentioned here
>> <http://t.yesware.com/tt/6640a48a14dbdef70b47105ac6b72156559fc5a6/5ba2375237a9fdc8efa681b19014981f/dda1509570b2b5d9d162e6293a1b3f07/stackoverflow.com/questions/22893139/why-is-a-function-method-call-in-python-expensive>
>> .
>>
>> Recursion means creating more functions / stack traces.
>>
>> On Thu, Feb 18, 2016 at 7:55 PM, Adam Forsyth <adam at adamforsyth.net>
>> wrote:
>>
>>> Phil,
>>>
>>> That's generally true, but one small correction. Aaron's solution won't
>>> actually won't flatten strings, as they don't have "__iter__" methods. They
>>> implement iteration because they take sequential numeric indexes starting
>>> at 0, and raise an IndexError after the index passed is too large.
>>>
>>> Adam
>>> On Feb 18, 2016 19:22, "Robare, Phillip (TEKSystems)" <
>>> proba at allstate.com> wrote:
>>>
>>>> Aaron, unlike Massimo’s elegant one-liner you don’t check that what you
>>>> are iterating over is a list.  Since Python will happily iterate over
>>>> strings, dictionaries, and much more you quickly get into problems when the
>>>> list includes more types than lists and numbers.  I recount this from
>>>> experience when I tried to throw together a flatten routine and pass it a
>>>> data structure that I got from loading a JSON string.
>>>>
>>>>
>>>>
>>>> Phil Robare
>>>>
>>>>
>>>>
>>>> *<snip/>*
>>>>
>>>>
>>>>
>>>> On Thu, Feb 18, 2016 at 1:43 PM, Aaron Elmquist <elmq0022 at umn.edu>
>>>> wrote:
>>>>
>>>> Douglas,
>>>>
>>>> Here's one more version for you and the rest of the list. It's based on
>>>> Brad's code.  I will let you think about why this version might be better
>>>> or worse.  Also, recursion is great.  It's just too bad it's not one of
>>>> python's strong points.
>>>>
>>>>
>>>> def flatten(lst):
>>>>     for item1 in lst:
>>>>         if hasattr(item1, '__iter__'):
>>>>             for item2 in flatten(item1):
>>>>                 yield item2
>>>>         else:
>>>>             yield item1
>>>>
>>>> print([x for x in flatten([1, [2,3,[4,5,6,[7,8,9]]]]) if x%2 == 1])
>>>>
>>>> y = flatten([1, [2,3,[4,5,6,[7,8,9]]]])
>>>>
>>>> print(next(y))
>>>> print(next(y))
>>>> print(next(y))
>>>> .
>>>> .
>>>> .
>>>> <snip/>
>>>>
>>>> On Wed, Feb 17, 2016 at 9:48 PM, DiPierro, Massimo <
>>>> MDiPierro at cs.depaul.edu> wrote:
>>>>
>>>> here is a one liner:
>>>>
>>>> def flatten(x):
>>>>     return [z for y in x for z in flatten(y)] if isinstance(x,list)
>>>> else [x]
>>>>
>>>>
>>>>
>>>> _______________________________________________
>>>> Chicago mailing list
>>>> Chicago at python.org
>>>> https://mail.python.org/mailman/listinfo/chicago
>>>>
>>>>
>>> _______________________________________________
>>> Chicago mailing list
>>> Chicago at python.org
>>> https://mail.python.org/mailman/listinfo/chicago
>>>
>>>
>>
>> _______________________________________________
>> Chicago mailing list
>> Chicago at python.org
>> https://mail.python.org/mailman/listinfo/chicago
>>
>>
>
> _______________________________________________
> Chicago mailing list
> Chicago at python.org
> https://mail.python.org/mailman/listinfo/chicago
>
>
> _______________________________________________
> Chicago mailing list
> Chicago at python.org
> https://mail.python.org/mailman/listinfo/chicago
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/chicago/attachments/20160219/e00e8491/attachment.html>