Re: Are zippers the right choice for sequence-like trees?
Thanks Jason - that’s helpful. -- paul.butcher-msgCount++ Silverstone, Brands Hatch, Donington Park... Who says I have a one track mind? http://www.paulbutcher.com/ LinkedIn: http://www.linkedin.com/in/paulbutcher Skype: paulrabutcher Author of Seven Concurrency Models in Seven Weeks: When Threads Unravel http://pragprog.com/book/pb7con On 4 June 2014 at 14:33:27, Jason Felice (jason.m.fel...@gmail.com) wrote: In general, I've found that zippers make complicated edits super-easy, while a recursive phrasing of the same algorithm - if it exists and isn't super complicated to write - performs better and gives more control over structural sharing. I might prove out an algorithm with zippers, but when the pedal hits the road for performance, I'll try to rephrase it. If you can phrase things in terms of (catvec (subvec ...) (subvec ...)), then I'll bet (but you should check) that rrb-vector will perform better and do more structural sharing. On Wed, Jun 4, 2014 at 8:29 AM, Paul Butcher p...@paulbutcher.com wrote: I am working with “sequence like” trees - by which I mean that they’re very broad (typically the root node will have several thousand children) and shallow (no more than 2 levels deep). I’m often dealing with a degenerate tree that’s really just a sequence (all the nodes in the tree are children of the root). A typical edit is either changing the value of a single element, inserting a single element, or deleting a small set of contiguous elements. I’m currently using clojure.zip to edit the tree, and it’s working just fine. But I’m concerned that it won’t be giving me much value in terms of structure sharing for this type of tree and this type of edit. So I have two questions: 1) What would be a good way for me to instrument my code to determine what level of structure sharing I am achieving? 2) Should I consider switching to something based on (say?) rrb-vector? -- paul.butcher-msgCount++ Silverstone, Brands Hatch, Donington Park... Who says I have a one track mind? http://www.paulbutcher.com/ LinkedIn: http://www.linkedin.com/in/paulbutcher Skype: paulrabutcher Author of Seven Concurrency Models in Seven Weeks: When Threads Unravel http://pragprog.com/book/pb7con -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Are zippers the right choice for sequence-like trees?
I am working with “sequence like” trees - by which I mean that they’re very broad (typically the root node will have several thousand children) and shallow (no more than 2 levels deep). I’m often dealing with a degenerate tree that’s really just a sequence (all the nodes in the tree are children of the root). A typical edit is either changing the value of a single element, inserting a single element, or deleting a small set of contiguous elements. I’m currently using clojure.zip to edit the tree, and it’s working just fine. But I’m concerned that it won’t be giving me much value in terms of structure sharing for this type of tree and this type of edit. So I have two questions: 1) What would be a good way for me to instrument my code to determine what level of structure sharing I am achieving? 2) Should I consider switching to something based on (say?) rrb-vector? -- paul.butcher-msgCount++ Silverstone, Brands Hatch, Donington Park... Who says I have a one track mind? http://www.paulbutcher.com/ LinkedIn: http://www.linkedin.com/in/paulbutcher Skype: paulrabutcher Author of Seven Concurrency Models in Seven Weeks: When Threads Unravel http://pragprog.com/book/pb7con -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: Are zippers the right choice for sequence-like trees?
In general, I've found that zippers make complicated edits super-easy, while a recursive phrasing of the same algorithm - if it exists and isn't super complicated to write - performs better and gives more control over structural sharing. I might prove out an algorithm with zippers, but when the pedal hits the road for performance, I'll try to rephrase it. If you can phrase things in terms of (catvec (subvec ...) (subvec ...)), then I'll bet (but you should check) that rrb-vector will perform better and do more structural sharing. On Wed, Jun 4, 2014 at 8:29 AM, Paul Butcher p...@paulbutcher.com wrote: I am working with “sequence like” trees - by which I mean that they’re very broad (typically the root node will have several thousand children) and shallow (no more than 2 levels deep). I’m often dealing with a degenerate tree that’s really just a sequence (all the nodes in the tree are children of the root). A typical edit is either changing the value of a single element, inserting a single element, or deleting a small set of contiguous elements. I’m currently using clojure.zip to edit the tree, and it’s working just fine. But I’m concerned that it won’t be giving me much value in terms of structure sharing for this type of tree and this type of edit. So I have two questions: 1) What would be a good way for me to instrument my code to determine what level of structure sharing I am achieving? 2) Should I consider switching to something based on (say?) rrb-vector? -- paul.butcher-msgCount++ Silverstone, Brands Hatch, Donington Park... Who says I have a one track mind? http://www.paulbutcher.com/ LinkedIn: http://www.linkedin.com/in/paulbutcher Skype: paulrabutcher Author of Seven Concurrency Models in Seven Weeks: When Threads Unravel http://pragprog.com/book/pb7con -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
