• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Sorting and Collection Help

 
Ranch Hand
Posts: 38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Ranch Hand
Posts: 1078
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 1078
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.

 
Ranch Hand
Posts: 1970
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Joe Shy
Ranch Hand
Posts: 38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Ranch Hand
Posts: 1170
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 1078
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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?
 
Marshal
Posts: 28193
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Or you could use an ArrayList and, when it's full, call its "trimToSize()" method.
 
Ken Blair
Ranch Hand
Posts: 1078
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
That too. Of course, that's assuming resizing the array again is worth the memory.
 
Don't listen to Steve. Just read this tiny ad:
a bit of art, as a gift, the permaculture playing cards
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic