You are asking on the wrong list. Nobody in the Clojure list will ever tell you that monkey-patching and mutating your data structure is the right approach in order to traverse it. And that's totally fine: ask away, if you're willing to accept other solutions. But you've rejected all ideas aside from the one you had before you got here as non- performant, when you don't seem to have a clear understanding of the performance characteristics of either.
Space waste? Really? You can't afford a pointer to each Node object during the traversal, but you can afford an extra boolean field in each Node, even when you're not traversing them? Hint: objects are typically allocated on pointer-sized boundaries, so an extra boolean at the end will take up as much "real" space as a whole pointer. And you have a *binary* tree, storing a Node[] instead of Node left, Node right? Instead of two pointers and two data objects, you're storing two data objects, two pointers, a pointer to Node[], and a length property. Throw away that extra crap and you have more than enough room for a temporary hashtable. On Mar 16, 11:17 am, CuppoJava <patrickli_2...@hotmail.com> wrote: > It sounds like hashing is the only solution that can really compete > with these markers. My particular problem cannot use hashing because > the space waste and extra compute time is unacceptable. I'll just have > to be particularly careful for multithreading my app. > > Thanks for the replies > -Patrick > > On Mar 16, 10:31 am, Armando Blancas <armando_blan...@yahoo.com> > wrote: > > > > > > > > > > However, the visited field has nothing to do with the actual Node > > > class. It's simply for other functions to use as a marker. > > > > This solution is kludgy, but I cannot see any other *performant* way > > > of doing this. > > > I don't think markers are a kludge. Besides modeling, data structures > > must support stuff like performance requirements. This is no different > > than, say, reference counting in GC's, COM, inodes, etc. -- 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
