[Chicago] Resolving lists within lists within lists within .....
Brad Martsberger
bradley.marts at gmail.com
Fri Feb 19 13:28:11 EST 2016
Adam, that's awesome, thanks.
On Fri, Feb 19, 2016 at 10:49 AM, Adam Forsyth <adam at adamforsyth.net> wrote:
> If you're looking for a single-pass iterative solution, you can emulate
> recursion with a stack:
>
> Start with a basic recursive implementation:
>
> def flatten(lst):
> result = []
> for item in lst:
> if isinstance(item, list):
> for item in flatten(item):
> result.append(item)
> else:
> result.append(item)
> return result
>
> Replace the for loops with while loops, and it's straightforward to
> replace the recursion with a stack that does the same thing:
>
> def iterative_flatten(lst):
> result = []
> stack = [(lst, 0)]
>
> while stack:
> lst, index = stack.pop()
> while index < len(lst):
> item = lst[index]
> if isinstance(item, list):
> stack.append((lst, index + 1))
> lst, index = item, 0
> else:
> result.append(item)
> index += 1
>
> return result
>
> This is very, very close to what Python is doing internally when you use a
> recursive solution.
>
>
> On Fri, Feb 19, 2016 at 10:42 AM, Aaron Elmquist <elmq0022 at umn.edu> wrote:
>
>> Okay, that made my jaw drop.
>>
>> On Fri, Feb 19, 2016 at 10:39 AM, JS Irick <hundredpercentjuice at gmail.com
>> > wrote:
>>
>>> I think we can agree that there is only one true solution:
>>>
>>> >>> my_list
>>>
>>> [1, 2, [1, 2, 3, [1, 2, 3, 4], 5], 4, 5]
>>>
>>> >>> json.loads("["+re.sub('[\[\]]','',json.dumps(my_list))+"]")
>>>
>>> [1, 2, 1, 2, 3, 1, 2, 3, 4, 5, 4, 5]
>>>
>>> On Fri, Feb 19, 2016 at 10:05 AM, Aaron Elmquist <elmq0022 at umn.edu>
>>> wrote:
>>>
>>>> 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
>>>>>>
>>>>>>
>>>>>
>>>>
>>>> _______________________________________________
>>>> Chicago mailing list
>>>> Chicago at python.org
>>>> https://mail.python.org/mailman/listinfo/chicago
>>>>
>>>>
>>>
>>>
>>> --
>>> ====
>>> JS Irick
>>> 312-307-8904
>>> Consultant: truqua.com
>>> Coach: atlascrossfit.com
>>> Programmer: juicetux.com
>>>
>>> _______________________________________________
>>> 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/0f919828/attachment.html>
More information about the Chicago
mailing list