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

Fri Feb 19 10:24:38 EST 2016

Thanks Adam.  I was knew pushing to the front of a list is generally a bad
(horrible) idea and would not scale.  Using collections.deque as you
suggest is definitely a much better idea.  Thanks for point that out.

So, now that we had all this discussion, has anyone encountered this issue
in the real world, or is this discussion just academic?

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/31099816/attachment-0001.html>