Forums Register Login

Implement THIS!

+Pie Number of slices to send: Send
I posted this already in this forum, but i figure the question has evolved enough since then to warrant a fresh thead.
Consider an implementation to the following:
an object (we'll call it a Node) has two components. We'll call these 'x', and 'cost.' The collection is to have only one node with any given x value. The Collection is to be sorted, however, by the cost value. Furthermore, given a node, if a node exists in the Collection with that cost, the one with the lower cost is included, the other pitched.
Implementations I tried and the problems with them:
TreeSet: worked great, except given a node, i was unable to check and for equal nodes and compare with them if one was found.
TreeMap (key of x points to cost): great for replacing, but sorts by x, when i want to sort by cost. Cost clearly cannot point to x, as multiple nodes can have the same cost.
Any ideas?
Thanks,
Joe
+Pie Number of slices to send: Send
 

Originally posted by Joseph George:
Furthermore, given a node, if a node exists in the Collection with that cost, the one with the lower cost is included, the other pitched.


Do you mean if one exists with that x, the one with the lower cost is included?
+Pie Number of slices to send: Send
why, yes... clearly the file somehow got currrupted after i posted it with 'x'... someone ought to check the security...
[ May 08, 2004: Message edited by: Joseph George ]
+Pie Number of slices to send: Send
Anyone mind if I shamelessly draw my thread back to the top of the list? I answered your question, Ernest.
+Pie Number of slices to send: Send
I'll answer with more questions.
When you say you want it sorted by cost, what does that mean? Does it mean:
- You want to iterate over all the Nodes ordered by cost?
- You always want to know the most expensive Node?
- Something else?
If it's the iteration one, how often will you iterate over the collection, vs. how often will the container's contents be changed? What will the usage pattern look like: will you put everything in, then iterate, or will there be random changes and iterations interspersed? How frequently will you iterate over the collection, vs. how often will you make changes?
+Pie Number of slices to send: Send
every run of the algorithm (there need to be thousands of such runs a second...) I will remove one node (the node with the lowest cost... that answers your first question), and add up to 8 nodes. Nodes are never changed. In this case, I'm truly not trying to be the annoying question asker... I really am cuncurrently trying to find a solution. the kicker is this replacement buisness i described above.
[ May 09, 2004: Message edited by: Joseph George ]
+Pie Number of slices to send: Send
OK, great. The reason I'm asking so many questions is that you're going to need a compromise of some kind, and without knowing what's up, it's hard to know what the compromise should be, exactly.
OK, the "single lowest cost node" thing is great. You don't actually need the collection to be sorted; you just need to always know the cheapest node. That cries out for a heap-based priority queue. A heap-based priority queue keeps a bunch of data in semi-sorted order such that you always know the "first" node (i.e., it's a constant-time operation), it costs at most log(N) to find each "next" node, and adding or deleting nodes also costs at most log(N).
So what I'd do would be to use a HashMap with X as the keys and Node objects as the values, just so that you could keep the cheapest Node per X, and then also keep the nodes in a priority queue. When you add or remove those eight nodes, you'll have to check for X in the Map, and decide whether to replace a Node or not; when you decide to change the map, you'll have to add or remove the same node from the priority queue. When you remove the lowest-cost node from the priority queue, you'll have to remove that same Node object from the HashMap.
I'm sorry, this isn't as coherent as I'd like it to be; I have a crying baby and a rambunctious six-year-old running around. It's Mother's Day, after all But Google for Java Heap Priority Queue and there is lots of information.
+Pie Number of slices to send: Send
I'll see what I can do with that... Thanks alot! It seems like something that would be so simple, and yet... I don't see why there isn't a method along the lines of get(Object o) for TreeSets, which returns an object in the TreeSet equaling the parameter. 'twould make my life alot easier, anyway. Anyway, thanks for your advice, and a Happy Mother's Day to you!
+Pie Number of slices to send: Send
Hey Joseph,
Just a thought, you might like to look at the Jakarta Collections framework. This includes some more complex data structures like bidirectional maps and multisets.
To be honest I haven't followed this topic close enough to be sure they'd help, but from the issues you listed at the top of this thread, they may help. I was thinking maybe you could avoid implementing your own data structure, but I don't think there are any queue implementations in there. Maybe you could add one
Anyway, just a thought.
--Tim
+Pie Number of slices to send: Send
Maybe I'm missing something ... can you keep the objects in a map keyed on "x". Any time a new one comes in, see if you already have that x, add one if not, if the new one has lower "cost" than the old one put it in. That keeps the set with the lowest cost for a given "x".
Then when somebody wants a sorted view of this stuff, give them a new sorted set created from the old map. Probably have to build a quick comparator to get it sorted in the right order.
Nobody has to know you're keeping a hidden unsorted map. Isn't that why objects are so much fun?
+Pie Number of slices to send: Send
I would have to sort it hundreds of times a second... far too inefficient
+Pie Number of slices to send: Send
Another thought...
Having read a bit more, why not use a SortedMap, and create a new Comparator that sorts based on cost?
I haven't thought that through thoroughly, but it sounds like it'd resolve the problem you mentioned in the original post about TreeMap.
Cheers,

--Tim
+Pie Number of slices to send: Send
The problem with this is that the key (c) would have to have within it the value (cost). Thus, i would be having a node point to a node. I considered this, but discared it as preposterous, to have something point to itself. Maybe i was too quick in pitching it, but...
+Pie Number of slices to send: Send
 

Originally posted by Joseph George:
I will remove one node (the node with the lowest cost... that answers your first question), and add up to 8 nodes. Nodes are never changed.


If there are only 8 nodes, who will never change, do you know the values of 'x' before?
Is there a fixed pool of 8 possible values, or do you remove the cheapest object, when a 9th value occurs?
If the pool is greater than 8, how great is it?
I'm asking, because I'm thinking of using this value as an index - probably after some conversion of course...
[ May 09, 2004: Message edited by: Stefan Wagner ]
If you're gonna buy things, buy this thing and I get a fat kickback:
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com


reply
reply
This thread has been viewed 567 times.
Similar Threads
Richfaces Tree rich:treeNodesAdaptor not working
XMLWhiz test ...
Graphs and identifying adjacent nodes
unable to read value from XML file
need help
More...

All times above are in ranch (not your local) time.
The current ranch time is
Mar 28, 2024 19:29:22.