aspose file tools*
The moose likes Java in General and the fly likes Sorting and Collection Help Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Sorting and Collection Help" Watch "Sorting and Collection Help" New topic
Author

Sorting and Collection Help

Joe Shy
Ranch Hand

Joined: Dec 09, 2005
Posts: 38
I am working on sorting a list of alpha numerics. No big deal, or so I thought. I have to filter out unique keys and sort on the alpha numberic column. I brought them in using a Hashtable and Set. That allowed me to pull the related values under there duplicate key. Then I pulled out the non duplicate values into a vector and do Collections.sort(<Vector> ; . It sorts them just fine. Now I need to find the hash key that macthes the value to update the DB order. The hash table doesn't return the key value on any of the get() or contains() methods listed in the API. Anyone have an idea on how to do this? I thought about creating objects, but then after sorting run into the same problem. I didn't paste the code yet, but can if someone would like to see it. I am trying to avoid writing my own sort, since the Collections.sort part suites my needs.

Simple example
Key1 Value3
Key2 Value1
Key3 Value2

Vector: Value3, Value1,Value2
Sort...
Value 1, Value2, Value3
Get Key from value???

Thanks for the help,
Joe


SCJP, SCJD(In Progress)<br /> <br />"They whom make no mistakes usually make nothing at all."
Ken Blair
Ranch Hand

Joined: Jul 15, 2003
Posts: 1078
A Map doesn't provide methods to find the key for a given value because not only would it have to iterate over the entries to find the key but many different keys may have the same value. Off the top of my head the first thing I would look at is creating a wrapper for the Map.Entry. Create a Map.Entry that wraps another Map.Entry and implements Comparable to delegate to the value. Then grab them with entrySet(), copy to a List and do the sort. Then it's simply a matter of retrieving the key from the now sorted entries.
Joe Shy
Ranch Hand

Joined: Dec 09, 2005
Posts: 38
Thank you for the response, I think I see what you mean, but I have to work with the Map.Entry some more.
Ken Blair
Ranch Hand

Joined: Jul 15, 2003
Posts: 1078
I needed a change of pace so I tried it myself. Normally I don't give out code, but you've already made an attempt at it and I doubt this is homework.

Joe Shy
Ranch Hand

Joined: Dec 09, 2005
Posts: 38
Thanks for the code. You are correct, this is for work and not homework. However, I am seeing that the code requires Java 5.0. I think I can work with it to make it work with 1.4.2, and post my results. Thanks again for the head start.

Peter Chase
Ranch Hand

Joined: Oct 30, 2001
Posts: 1970
I admit I didn't read the previous posts in detail, so this might not be helpful, but...

Couldn't you use a SortedMap? An implementation is provided: TreeMap. This will keep itself sorted, as you add entries.

Also, if you do want a map with two-way look-up, you can simply use two parallel maps. One maps keys to values and the other maps values to keys. I have sometimes made a wrapper class, TwoWayMap, to encapsulate this idea.

You talk about using Hashtable and Vector. It sounds like this is new code, and you're using Java 1.4. Therefore, you should not be using these old classes, but instead should use HashMap and ArrayList, or similar. The synchronisation provided by Hashtable and Vector is rarely useful, because it's on an operation-by-operation level; it justs wastes performance.


Betty Rubble? Well, I would go with Betty... but I'd be thinking of Wilma.
Joe Shy
Ranch Hand

Joined: Dec 09, 2005
Posts: 38
I guess I chose Vector since I can start with the initial size of 10 and then do .addElement() and it increases the size by one. I do this because the total capacity could be 1 or 100, never more than 1000. I don't want to reserve 100 arrays with 1000 entries to ensure capacity. I wouldn't be surprised if I am missing something though.

I do like the idea of the wrapper class with two maps. I haven't had much time to work on this today, but will keep plugging away.

Thanks always,
Joe
Mr. C Lamont Gilbert
Ranch Hand

Joined: Oct 05, 2001
Posts: 1170

Both HashMap and ArrayList let you set the default size. Some even let you tweak the growth rate. Dump Vector and Hashtable.
Ken Blair
Ranch Hand

Joined: Jul 15, 2003
Posts: 1078
Originally posted by Joe Quickshot:
Thanks for the code. You are correct, this is for work and not homework. However, I am seeing that the code requires Java 5.0. I think I can work with it to make it work with 1.4.2, and post my results. Thanks again for the head start.



You'll have to remove the generics and possibly insert some type checking and casts.

Originally posted by Peter Chase:
I admit I didn't read the previous posts in detail, so this might not be helpful, but...

Couldn't you use a SortedMap? An implementation is provided: TreeMap. This will keep itself sorted, as you add entries.

Also, if you do want a map with two-way look-up, you can simply use two parallel maps. One maps keys to values and the other maps values to keys. I have sometimes made a wrapper class, TwoWayMap, to encapsulate this idea.

You talk about using Hashtable and Vector. It sounds like this is new code, and you're using Java 1.4. Therefore, you should not be using these old classes, but instead should use HashMap and ArrayList, or similar. The synchronisation provided by Hashtable and Vector is rarely useful, because it's on an operation-by-operation level; it justs wastes performance.


The only problem with SortedMap is it sorts on the key rather than the value. I believe you can use a Comparator instead but I don't know if that will let you sort on the value or just substitute a different sorting on key. I didn't even look at that because I didn't think about it.

Originally posted by Joe Quickshot:
I guess I chose Vector since I can start with the initial size of 10 and then do .addElement() and it increases the size by one. I do this because the total capacity could be 1 or 100, never more than 1000. I don't want to reserve 100 arrays with 1000 entries to ensure capacity. I wouldn't be surprised if I am missing something though.

I do like the idea of the wrapper class with two maps. I haven't had much time to work on this today, but will keep plugging away.

Thanks always,
Joe


Honestly I fail to see how that's a good thing. Why would you want the array to be resized every time? If you know what the capacity will be then set it to that, if you don't then let ArrayList grow the way it's designed to. It will more than likely be a trivial amount of space that is "wasted" by an ArrayList with more capacity than needed once you're doing filling it. That space is almost certainly far more trivial than the time lost due to unnecessary synchronization and constantly resizing the array. In the worst case scenario you'd have 1.9kb of memory sitting in an array unused (I'm defining a worst case scenario as being an array resize on the very last insertion where the last insertion is the 1000th element). Even if you had 500 of these massive 1000 element arrays at any given time you're still only looking at less than 1mb of memory taken up in excessive array sizes. Do you really think that's going to be important compared to the space those 500,000 objects are taking up? Or the time spent creating and inserting those?
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18570
    
    8

Or you could use an ArrayList and, when it's full, call its "trimToSize()" method.
Ken Blair
Ranch Hand

Joined: Jul 15, 2003
Posts: 1078
That too. Of course, that's assuming resizing the array again is worth the memory.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Sorting and Collection Help