[Chicago] Resolving lists within lists within lists within .....
JS Irick
hundredpercentjuice at gmail.com
Fri Feb 19 12:05:02 EST 2016
Massimo-
I gave up making the same joke when I couldn't come up with as awesome a
term as "square bracket injection attacks"
On Fri, Feb 19, 2016 at 10:47 AM, DiPierro, Massimo <MDiPierro at cs.depaul.edu
> wrote:
> LOL
>
> vulnerable to square brackets injection attacks! [1, 2, [1, 2, 3, [1, 2,
> ‘[9,1,9]', 4], 5], 4, 5]
>
> On Feb 19, 2016, at 10:39 AM, JS Irick <hundredpercentjuice at gmail.com
> <mailto: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<mailto:
> 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<mailto:
> 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
> <mailto: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<mailto:
> 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<mailto:
> 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
> <mailto: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
> <mailto: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<mailto:
> 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<mailto: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<mailto:Chicago at python.org>
> https://mail.python.org/mailman/listinfo/chicago
>
>
> _______________________________________________
> Chicago mailing list
> Chicago at python.org<mailto:Chicago at python.org>
> https://mail.python.org/mailman/listinfo/chicago
>
>
>
> _______________________________________________
> Chicago mailing list
> Chicago at python.org<mailto:Chicago at python.org>
> https://mail.python.org/mailman/listinfo/chicago
>
>
>
> _______________________________________________
> Chicago mailing list
> Chicago at python.org<mailto:Chicago at python.org>
> https://mail.python.org/mailman/listinfo/chicago
>
>
>
> _______________________________________________
> Chicago mailing list
> Chicago at python.org<mailto:Chicago at python.org>
> https://mail.python.org/mailman/listinfo/chicago
>
>
>
>
> _______________________________________________
> Chicago mailing list
> Chicago at python.org<mailto:Chicago at python.org>
> https://mail.python.org/mailman/listinfo/chicago
>
>
>
>
> --
> ====
> JS Irick
> 312-307-8904
> Consultant: truqua.com<http://truqua.com/>
> Coach: atlascrossfit.com<http://atlascrossfit.com/>
> Programmer: juicetux.com<http://juicetux.com/>
> _______________________________________________
> Chicago mailing list
> Chicago at python.org<mailto: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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/chicago/attachments/20160219/8b9c0959/attachment.html>
More information about the Chicago
mailing list