[Chicago] Resolving lists within lists within lists within .....
Aaron Elmquist
elmq0022 at umn.edu
Fri Feb 19 11:05:20 EST 2016
That's still potentially a lot of list copying though, isn't it?
On Fri, Feb 19, 2016 at 9:40 AM, Aaron Elmquist <elmq0022 at umn.edu> wrote:
> 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/29d0eaa7/attachment-0001.html>
More information about the Chicago
mailing list