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

Aaron Elmquist elmq0022 at umn.edu
Fri Feb 19 10:40:46 EST 2016 

Brad, that's a really cool approach and very readable.  Thanks!

On Fri, Feb 19, 2016 at 9:34 AM, Brad Martsberger <bradley.marts at gmail.com>
wrote:

> Aaron, Thanks for your example. One thing to point out is that popping
> from the front of a list is expensive because the entire list has to be
> copied. Some options are to flatten the list from the back (popping off the
> end of the list is cheap), or copying the list into a deque (from
> collections import deque).
>
> Here is another example of a non recursive version of flatten. It's not
> nearly as elegant as the recursive version. It's longer than Aaron's
> iterative version, but avoids hand manipulating the iteration over the
> lists (no popping or inserting).
>
> def press(lst):
>     """
>     Flattens nested lists one level
>
>     Returns a tuple (new_list, changed) where changed is a boolean
> indicating
>     whether new_list is different from lst.
>     """
>     changed = False
>     new_list = []
>     for element in lst:
>         if isinstance(element, list):
>             new_list.extend(element)
>             changed = True
>         else:
>             new_list.append(element)
>
>     return new_list, changed
>
>
> def flatten(lst):
>     """
>     Fully flattens nested lists into a list with no sublists
>     """
>     new_list = lst
>     changed = True
>     while changed:
>         new_list, changed = press(new_list)
>     return new_list
>
> On Fri, Feb 19, 2016 at 6:59 AM, Aaron Elmquist <elmq0022 at umn.edu> wrote:
>
>> 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/c6a27a72/attachment.html>

More information about the Chicago mailing list