[Chicago] Resolving lists within lists within lists within .....
Adam Forsyth
adam at adamforsyth.net
Fri Feb 19 11:49:46 EST 2016
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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/chicago/attachments/20160219/118cc603/attachment-0001.html>
More information about the Chicago
mailing list