Re: Advice on choosing the right data structure
This is still just recursion because of the map. That means it has all the
problems of recursion. If you need to avoid recursion, you need to do a
depth first or breadth first traversal of the tree and hold onto state as
you do it. The zipper does some of this for you and provides an easy way to
traverse data in a depth first fashion. If you need additional state, say
to collect data, or track data as you mutate the tree, then zip-visit may
or may not help.
Ultimately, to use a zipper you need to structure your algorithms to work
with a depth first traversal rather than using tree recursion. That said,
doing standard tree recursion may be the right answer. It all depends on
your use case.
On Wednesday, December 4, 2013 8:38:11 PM UTC-5, dabd wrote:
Thanks I'll take a look at your libraries.
One problem I found with the zipper API is that if you have a recursive
function that takes a loc, when you call it on the clojure.zip/children of
a given loc it won't work because this function returns a seq of nodes
instead of a seq of locs. Shouldn't we add a function like
children-as-locs to the API for this purpose or is there another way?
(defn children-as-locs
Returns a seq of locs of the children of loc.
[loc]
(when (z/branch? loc)
(let [[node path] loc
cs (z/children loc)]
(map-indexed (fn [i c]
(with-meta [c {:l (vec (take i cs))
:pnodes (if path (conj (:pnodes path)
node) [node])
:ppath path
:r (vec (drop (inc i) cs))}]
(meta loc)))
cs
On Wednesday, December 4, 2013 11:46:29 PM UTC, Alexander Hudek wrote:
Additionally, if you need more complex access patterns you could see if
this helps:
https://github.com/akhudek/zip-visit
For performance, there is a fast-zip library that is api compatible with
clojure.zip. You can just swap the clojure.zip namespace for the fast-zip
namespace. Note that you'd need to make the same swap in any libraries you
use with your zippers (like zip-visit) since fast-zip is not implementation
compatible with clojure.zip.
More broadly, I've found that straight up recursive algorithms can be a
lot faster than zippers, especially for read only operations. Of course the
stack size limits what you can do with tree recursion. As others have said,
it's best to see if you actually have performance problems first.
On Wednesday, December 4, 2013 5:30:02 PM UTC-5, James Reeves wrote:
On 4 December 2013 21:09, dabd dario@gmail.com wrote:
I didn't get there because I ran into problems with the zipper API.
When you call 'children' on a loc you get a seq of nodes instead of a seq
of locs which causes me problems in a recursive algorithm operating on
locs.
Have you tried using next and end? for a depth-first transversal?
- James
--
--
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/groups/opt_out.
Re: Advice on choosing the right data structure
Why isn't a zipper appropriate for tree recursion?
On Sunday, December 8, 2013 2:16:33 AM UTC, Alexander Hudek wrote:
This is still just recursion because of the map. That means it has all the
problems of recursion. If you need to avoid recursion, you need to do a
depth first or breadth first traversal of the tree and hold onto state as
you do it. The zipper does some of this for you and provides an easy way to
traverse data in a depth first fashion. If you need additional state, say
to collect data, or track data as you mutate the tree, then zip-visit may
or may not help.
Ultimately, to use a zipper you need to structure your algorithms to work
with a depth first traversal rather than using tree recursion. That said,
doing standard tree recursion may be the right answer. It all depends on
your use case.
On Wednesday, December 4, 2013 8:38:11 PM UTC-5, dabd wrote:
Thanks I'll take a look at your libraries.
One problem I found with the zipper API is that if you have a recursive
function that takes a loc, when you call it on the clojure.zip/children of
a given loc it won't work because this function returns a seq of nodes
instead of a seq of locs. Shouldn't we add a function like
children-as-locs to the API for this purpose or is there another way?
(defn children-as-locs
Returns a seq of locs of the children of loc.
[loc]
(when (z/branch? loc)
(let [[node path] loc
cs (z/children loc)]
(map-indexed (fn [i c]
(with-meta [c {:l (vec (take i cs))
:pnodes (if path (conj (:pnodes path)
node) [node])
:ppath path
:r (vec (drop (inc i) cs))}]
(meta loc)))
cs
On Wednesday, December 4, 2013 11:46:29 PM UTC, Alexander Hudek wrote:
Additionally, if you need more complex access patterns you could see if
this helps:
https://github.com/akhudek/zip-visit
For performance, there is a fast-zip library that is api compatible with
clojure.zip. You can just swap the clojure.zip namespace for the fast-zip
namespace. Note that you'd need to make the same swap in any libraries you
use with your zippers (like zip-visit) since fast-zip is not implementation
compatible with clojure.zip.
More broadly, I've found that straight up recursive algorithms can be a
lot faster than zippers, especially for read only operations. Of course the
stack size limits what you can do with tree recursion. As others have said,
it's best to see if you actually have performance problems first.
On Wednesday, December 4, 2013 5:30:02 PM UTC-5, James Reeves wrote:
On 4 December 2013 21:09, dabd dario@gmail.com wrote:
I didn't get there because I ran into problems with the zipper API.
When you call 'children' on a loc you get a seq of nodes instead of a
seq
of locs which causes me problems in a recursive algorithm operating on
locs.
Have you tried using next and end? for a depth-first transversal?
- James
--
--
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/groups/opt_out.
Advice on choosing the right data structure
I would like to implement an algorithm that works on trees (n-ary trees) where each node is a complex type. Aside from the usual tree traversals I will need to be able to access the parent of a node. Performance is important since the algorithm is going to traverse the tree several times and update the nodes. I am wondering if a purely functional approach is better than using side effects. I tried a purely functional approach with zippers but ran into some trouble with the zipper API. I also think I will would have performance problems too as there is a lot of bookkeeping in a zipper (paths, parents associated with a loc). I looked into this nice document https://github.com/Prismatic/eng-practices/blob/master/clojure/20130926-data-representation.md to help me choose the right data structure. When maximum efficiency is important they suggest defrecord, deftype or reify. If I go for an imperative implementation it seems like deftype to represent the tree nodes would work well since it allows for mutable fields. Any advice on choosing the right data structure and whether to use a functional or imperative implementation is appreciated. Thanks. -- -- 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/groups/opt_out.
Re: Advice on choosing the right data structure
On 4 December 2013 20:27, dabd dario.reh...@gmail.com wrote: I tried a purely functional approach with zippers but ran into some trouble with the zipper API. I also think I will would have performance problems too as there is a lot of bookkeeping in a zipper (paths, parents associated with a loc). You think you'll have performance problems? Have you benchmarked and checked? :) - James -- -- 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/groups/opt_out.
Re: Advice on choosing the right data structure
I didn't get there because I ran into problems with the zipper API. When you call 'children' on a loc you get a seq of nodes instead of a seq of locs which causes me problems in a recursive algorithm operating on locs. On Wednesday, December 4, 2013 8:38:17 PM UTC, James Reeves wrote: On 4 December 2013 20:27, dabd dario@gmail.com javascript: wrote: I tried a purely functional approach with zippers but ran into some trouble with the zipper API. I also think I will would have performance problems too as there is a lot of bookkeeping in a zipper (paths, parents associated with a loc). You think you'll have performance problems? Have you benchmarked and checked? :) - James -- -- 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/groups/opt_out.
Re: Advice on choosing the right data structure
it might be worthwhile to implement custom zippers for your trees, without using clojure.zip. I've done this for navigating into json structures and it was relatively painless (admittedly I only needed a smallish subset of the functionality provided by clojure.zip). On Wed, Dec 4, 2013 at 1:09 PM, dabd dario.reh...@gmail.com wrote: I didn't get there because I ran into problems with the zipper API. When you call 'children' on a loc you get a seq of nodes instead of a seq of locs which causes me problems in a recursive algorithm operating on locs. On Wednesday, December 4, 2013 8:38:17 PM UTC, James Reeves wrote: On 4 December 2013 20:27, dabd dario@gmail.com wrote: I tried a purely functional approach with zippers but ran into some trouble with the zipper API. I also think I will would have performance problems too as there is a lot of bookkeeping in a zipper (paths, parents associated with a loc). You think you'll have performance problems? Have you benchmarked and checked? :) - James -- -- 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/groups/opt_out. -- Ben Wolfson Human kind has used its intelligence to vary the flavour of drinks, which may be sweet, aromatic, fermented or spirit-based. ... Family and social life also offer numerous other occasions to consume drinks for pleasure. [Larousse, Drink entry] -- -- 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/groups/opt_out.
Re: Advice on choosing the right data structure
I had to implement a custom tree zipper as none of the existing zippers worked for me. My question is are there better alternatives when you want the best performance in clojure? On Wednesday, December 4, 2013 9:12:16 PM UTC, Ben wrote: it might be worthwhile to implement custom zippers for your trees, without using clojure.zip. I've done this for navigating into json structures and it was relatively painless (admittedly I only needed a smallish subset of the functionality provided by clojure.zip). On Wed, Dec 4, 2013 at 1:09 PM, dabd dario@gmail.com javascript:wrote: I didn't get there because I ran into problems with the zipper API. When you call 'children' on a loc you get a seq of nodes instead of a seq of locs which causes me problems in a recursive algorithm operating on locs. On Wednesday, December 4, 2013 8:38:17 PM UTC, James Reeves wrote: On 4 December 2013 20:27, dabd dario@gmail.com wrote: I tried a purely functional approach with zippers but ran into some trouble with the zipper API. I also think I will would have performance problems too as there is a lot of bookkeeping in a zipper (paths, parents associated with a loc). You think you'll have performance problems? Have you benchmarked and checked? :) - James -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clo...@googlegroups.comjavascript: Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+u...@googlegroups.com javascript: 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+u...@googlegroups.com javascript:. For more options, visit https://groups.google.com/groups/opt_out. -- Ben Wolfson Human kind has used its intelligence to vary the flavour of drinks, which may be sweet, aromatic, fermented or spirit-based. ... Family and social life also offer numerous other occasions to consume drinks for pleasure. [Larousse, Drink entry] -- -- 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/groups/opt_out.
Re: Advice on choosing the right data structure
oh, I meant custom from the bottom up, without using clojure.zip at all (so your issue with the return value of children wouldn't come up). I realize this doesn't answer your question about alternatives. On Wed, Dec 4, 2013 at 1:15 PM, dabd dario.reh...@gmail.com wrote: I had to implement a custom tree zipper as none of the existing zippers worked for me. My question is are there better alternatives when you want the best performance in clojure? On Wednesday, December 4, 2013 9:12:16 PM UTC, Ben wrote: it might be worthwhile to implement custom zippers for your trees, without using clojure.zip. I've done this for navigating into json structures and it was relatively painless (admittedly I only needed a smallish subset of the functionality provided by clojure.zip). On Wed, Dec 4, 2013 at 1:09 PM, dabd dario@gmail.com wrote: I didn't get there because I ran into problems with the zipper API. When you call 'children' on a loc you get a seq of nodes instead of a seq of locs which causes me problems in a recursive algorithm operating on locs. On Wednesday, December 4, 2013 8:38:17 PM UTC, James Reeves wrote: On 4 December 2013 20:27, dabd dario@gmail.com wrote: I tried a purely functional approach with zippers but ran into some trouble with the zipper API. I also think I will would have performance problems too as there is a lot of bookkeeping in a zipper (paths, parents associated with a loc). You think you'll have performance problems? Have you benchmarked and checked? :) - James -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clo...@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+u...@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+u...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Ben Wolfson Human kind has used its intelligence to vary the flavour of drinks, which may be sweet, aromatic, fermented or spirit-based. ... Family and social life also offer numerous other occasions to consume drinks for pleasure. [Larousse, Drink entry] -- -- 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/groups/opt_out. -- Ben Wolfson Human kind has used its intelligence to vary the flavour of drinks, which may be sweet, aromatic, fermented or spirit-based. ... Family and social life also offer numerous other occasions to consume drinks for pleasure. [Larousse, Drink entry] -- -- 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/groups/opt_out.
Re: Advice on choosing the right data structure
On 4 December 2013 21:09, dabd dario.reh...@gmail.com wrote: I didn't get there because I ran into problems with the zipper API. When you call 'children' on a loc you get a seq of nodes instead of a seq of locs which causes me problems in a recursive algorithm operating on locs. Have you tried using next and end? for a depth-first transversal? - James -- -- 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/groups/opt_out.
Re: Advice on choosing the right data structure
Additionally, if you need more complex access patterns you could see if this helps: https://github.com/akhudek/zip-visit For performance, there is a fast-zip library that is api compatible with clojure.zip. You can just swap the clojure.zip namespace for the fast-zip namespace. Note that you'd need to make the same swap in any libraries you use with your zippers (like zip-visit) since fast-zip is not implementation compatible with clojure.zip. More broadly, I've found that straight up recursive algorithms can be a lot faster than zippers, especially for read only operations. Of course the stack size limits what you can do with tree recursion. As others have said, it's best to see if you actually have performance problems first. On Wednesday, December 4, 2013 5:30:02 PM UTC-5, James Reeves wrote: On 4 December 2013 21:09, dabd dario@gmail.com javascript: wrote: I didn't get there because I ran into problems with the zipper API. When you call 'children' on a loc you get a seq of nodes instead of a seq of locs which causes me problems in a recursive algorithm operating on locs. Have you tried using next and end? for a depth-first transversal? - James -- -- 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/groups/opt_out.
Re: Advice on choosing the right data structure
Thanks I'll take a look at your libraries.
One problem I found with the zipper API is that if you have a recursive
function that takes a loc, when you call it on the clojure.zip/children of
a given loc it won't work because this function returns a seq of nodes
instead of a seq of locs. Shouldn't we add a function like
children-as-locs to the API for this purpose or is there another way?
(defn children-as-locs
Returns a seq of locs of the children of loc.
[loc]
(when (z/branch? loc)
(let [[node path] loc
cs (z/children loc)]
(map-indexed (fn [i c]
(with-meta [c {:l (vec (take i cs))
:pnodes (if path (conj (:pnodes path)
node) [node])
:ppath path
:r (vec (drop (inc i) cs))}]
(meta loc)))
cs
On Wednesday, December 4, 2013 11:46:29 PM UTC, Alexander Hudek wrote:
Additionally, if you need more complex access patterns you could see if
this helps:
https://github.com/akhudek/zip-visit
For performance, there is a fast-zip library that is api compatible with
clojure.zip. You can just swap the clojure.zip namespace for the fast-zip
namespace. Note that you'd need to make the same swap in any libraries you
use with your zippers (like zip-visit) since fast-zip is not implementation
compatible with clojure.zip.
More broadly, I've found that straight up recursive algorithms can be a
lot faster than zippers, especially for read only operations. Of course the
stack size limits what you can do with tree recursion. As others have said,
it's best to see if you actually have performance problems first.
On Wednesday, December 4, 2013 5:30:02 PM UTC-5, James Reeves wrote:
On 4 December 2013 21:09, dabd dario@gmail.com wrote:
I didn't get there because I ran into problems with the zipper API.
When you call 'children' on a loc you get a seq of nodes instead of a seq
of locs which causes me problems in a recursive algorithm operating on locs.
Have you tried using next and end? for a depth-first transversal?
- James
--
--
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/groups/opt_out.
