• Post Reply Bookmark Topic Watch Topic
  • New Topic

Implement THIS!  RSS feed

 
Ranch Hand
Posts: 815
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
author and iconoclast
Sheriff
Posts: 24217
38
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
Nick George
Ranch Hand
Posts: 815
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 ]
 
Nick George
Ranch Hand
Posts: 815
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Anyone mind if I shamelessly draw my thread back to the top of the list? I answered your question, Ernest.
 
Ernest Friedman-Hill
author and iconoclast
Sheriff
Posts: 24217
38
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
Nick George
Ranch Hand
Posts: 815
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 ]
 
Ernest Friedman-Hill
author and iconoclast
Sheriff
Posts: 24217
38
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Nick George
Ranch Hand
Posts: 815
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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!
 
Ranch Hand
Posts: 539
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
Nick George
Ranch Hand
Posts: 815
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I would have to sort it hundreds of times a second... far too inefficient
 
Tim West
Ranch Hand
Posts: 539
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Nick George
Ranch Hand
Posts: 815
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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...
 
Ranch Hand
Posts: 1923
Linux Postgres Database Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 ]
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!