On Wed, Mar 16, 2011 at 7:35 PM, CuppoJava <patrickli_2...@hotmail.com> wrote: > Thank you for the reply again Mark. > Actually, now that I've had some time to think about your solution, I > think it, is in fact, suitable for myself after all. There's just some > trickiness involving handing out the numeric ids that I need to figure > out. > > eg. Nodes are automatically assigned a unique numeric id. There is a > counter somewhere that is incremented every time a new Node is > allocated. > > Upon entry to the print function, I will allocate a vector whose size > is the current value of the counter. This ensures that every Node has > a slot in the vector. > > The problem arises after the program as been running for a long time > and the value of the counter is very high. There might be only two > Nodes in use, but one Node might have an id = 1 (because it was one of > the first ones created), and the other Node could have an id = 1000000 > (because it was only recently created). Now the cost of allocating the > vector is too great. > > I think, if a good way of handing out the numeric ids is figured out, > your solution would be perfect! I'll give it some more thought.
I can't see this being fixed without maintaining some kind of a "freelist" to allow recycling numeric IDs. But nodes already have numeric IDs: their addresses in your process's address space. You can get a hash of it by calling (System/identityHashCode the-node). I think ultimately your best bet is just to use a set. It will probably use less memory than most of the approaches being considered, including numeric IDs with freelist, overall. If the hash "load factor" is really, truly unacceptable for some reason you may have to accept a time/space tradeoff and use a linear list of visited nodes with a linear search. Other than that, you can use nonrecycled node IDs and binary search for visited node IDs in a tree, and that about exhausts your options. -- 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
