[Chicago] Resolving lists within lists within lists within .....
Aaron Elmquist
elmq0022 at umn.edu
Fri Feb 19 11:42:40 EST 2016
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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/chicago/attachments/20160219/e4f4aa5b/attachment.html>
More information about the Chicago
mailing list