• 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

Map Sorting

 
Greenhorn
Posts: 18
C++ Suse Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Given


I am custom sorting this map thus:


Where comparator is defined as:


Am doing this right?
 
author & internet detective
Posts: 41860
908
Eclipse IDE VI Editor Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
What are you trying to accomplish? It looks like sorting the map by the values while retaining the relationship between key/value pairs? If so, I don't see any problems with your approach.
 
Ranch Hand
Posts: 39
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
What you are doing here is creating a separate LinkedList of EntrySet and sorting it according to Values. While this seems OK, but in case you want to have a map sorted according to values, this is what you can do.

Create a comparator


Now create a TreeMap to use this comparator:


This would be slightly cleaner way of doing the thing.
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Divyanand Kutagulla wrote:Am doing this right?


As Jeanne said: the approach seems reasonable, except for one thing: LinkedLists take quadratic time to sort. An ArrayList, OTOH, will sort in logarithmic time; and probably take less space too.

However: you might want to answer her question too. If you simply want a "two-way" relationship between your keys and values, then you might be better off creating a "reverse multimap", viz:HIH

Winston
 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Deepak Bajoria wrote:...but in case you want to have a map sorted according to values, this is what you can do...


Interesting idea, but I see a few problems:
1. Your compare() method doesn't check when values are equal and return 0. This might be deliberate in order to retain ALL the original key mappings, but I suspect it's flawed.
2. What would you expect sortedRepresentation.get("X") to return (assuming "X" is a valid key)? I suspect you'll get null more often than you think; but I have to admit, I'm not absolutely sure.

I hate to say, but I much prefer Divyanand's solution - other than the LinkedList.

Winston
 
Deepak Bajoria
Ranch Hand
Posts: 39
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:
1. Your compare() method doesn't check when values are equal and return 0. This might be deliberate in order to retain ALL the original key mappings, but I suspect it's flawed.


This is of-course a sample implementation of compare method which can be easily modified as per the exact use case. This was never the concern here.

Winston Gutkowski wrote:
2. What would you expect sortedRepresentation.get("X") to return (assuming "X" is a valid key)? I suspect you'll get null more often than you think; but I have to admit, I'm not absolutely sure.


This comparator is designed to sort only the map which was passed to it while invoking the constructor, in which case sortedRepresentation.get("X") is never going to give null.
 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Deepak Bajoria wrote:This comparator is designed to sort only the map which was passed to it while invoking the constructor, in which case sortedRepresentation.get("X") is never going to give null.


Really? You're creating a TreeMap, which is a binary tree structure. Since your Comparator is actually only concerned with what was in the original Map, and is going to order those keys according to their associated values, I could definitely see problems if the original Map is subsequently updated; not to mention the idea of ordering something (your String keys) by something they're not even directly associated with, AND which might be duplicated [Edit: thinking about it; that may actually be the showstopper].

It might work as you've written it (ie, with no "equal" value), and like I say, it's an interesting idea; but I'm not sure I'd want to do any predictive analysis on it.

Winston
 
Divyanand Kutagulla
Greenhorn
Posts: 18
C++ Suse Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Jeanne Boyarsky wrote:What are you trying to accomplish? It looks like sorting the map by the values while retaining the relationship between key/value pairs? If so, I don't see any problems with your approach.



Hi Jeanne,

I wanted to sort the map by values while retaining the key->value relationship
(Just wanted some professional opinion abt my approach)

Thanks for your response,
Divyanand

 
Divyanand Kutagulla
Greenhorn
Posts: 18
C++ Suse Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Deepak Bajoria wrote:What you are doing here is creating a separate LinkedList of EntrySet and sorting it according to Values. While this seems OK, but in case you want to have a map sorted according to values, this is what you can do.

Create a comparator


Now create a TreeMap to use this comparator:


This would be slightly cleaner way of doing the thing.




Hi Deepak,

Thank you for your reply.

In my code I do create a comparator

I wanted to use Collections.sort method to accomplish the sorting And I wanted to be memory efficient
Yes creating a TreeMap would help was it is sorted map. but it would take additional memory, I already have a map - granted it is not sorted, but I can use the Collections.sort to sort it with the right comparator.

Divyanand

 
Deepak Bajoria
Ranch Hand
Posts: 39
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:
Really? You're creating a TreeMap, which is a binary tree structure. Since your Comparator is actually only concerned with what was in the original Map, and is going to order those keys according to their associated values, I could definitely see problems if the original Map is subsequently updated; not to mention the idea of ordering something (your String keys) by something they're not even directly associated with, AND which might be duplicated [Edit: thinking about it; that may actually be the showstopper].

It might work as you've written it (ie, with no "equal" value), and like I say, it's an interesting idea; but I'm not sure I'd want to do any predictive analysis on it.

Winston


Thanks Winston, I see what you mean. What I am trying to do is to figure out how the ArrayList or the ReverseMap approach that you suggested is going to solve the problem of additional element being added to the original map after sort is performed.
 
Bartender
Posts: 4568
9
  • Likes 3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:As Jeanne said: the approach seems reasonable, except for one thing: LinkedLists take quadratic time to sort.



You sure about that? I'm pretty sure Collections.sort has N log N performance even on linked lists - it copies it to an array, sorts it there, and copies it back.
 
Deepak Bajoria
Ranch Hand
Posts: 39
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Divyanand Kutagulla wrote:


Hi Deepak,

Thank you for your reply.

In my code I do create a comparator

I wanted to use Collections.sort method to accomplish the sorting And I wanted to be memory efficient
Yes creating a TreeMap would help was it is sorted map. but it would take additional memory, I already have a map - granted it is not sorted, but I can use the Collections.sort to sort it with the right comparator.

Divyanand


If really care about memory, and you do not worry about the possibility of original map being updated after Collection.sort has been performed, then what you have done looks most reasonable to me. Of course, you can use ArrayList instead of LinkedList which might have better performance, although I am not sure about it.
 
Divyanand Kutagulla
Greenhorn
Posts: 18
C++ Suse Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Further to my question I modifiwd my sorting code thus:

The question I originally had in mind (but forgot to ask) is:
If representations.entrySet() returns a Set<String, Integer> then Why are we allowed to cast the Set to a ArrayList?
(ArrayList implements List interface which is different from the Set interface so casting a Set to an ArrayList should break at run time right?)

Thanks in advance for any clarification & sorry in advance if the question sounds ignorant.

Divyanand
 
Matthew Brown
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You're absolutely right that you can't cast it to an ArrayList. But if you look closely you'll see that isn't what that code is doing. It's creating a new ArrayList. ArrayList, like most collection classes, has a constructor that takes any Collection as an argument so that the new ArrayList contains the same elements as that collection.
 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Matthew Brown wrote:You sure about that? I'm pretty sure Collections.sort has N log N performance even on linked lists - it copies it to an array, sorts it there, and copies it back.


Oh yeah, that makes sense. (Duh)

Deepak Bajoria wrote:Thanks Winston, I see what you mean. What I am trying to do is to figure out how the ArrayList or the ReverseMap approach that you suggested is going to solve the problem of additional element being added to the original map after sort is performed.


It doesn't. Once created, both structures will be "snapshots" of the original, which is no different to Divyanand's idea of creating a List and then sorting it.
The main difference between your approach and mine is that mine creates a completely new Map, whereas yours creates one that is dependent on the original for finding things. Don't forget that the Comparator is used for all sorts of internal operations in a TreeMap.

You could certainly roll your own 'TwoWayMap' class that maintains both versions simultaneously, but it might get quite involved - especially if an update to either structure needs to be reflected in the other.

Winston
 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Divyanand Kutagulla wrote:Further to my question I modifiwd my sorting code thus:


Looks fine, and although Matthew is almost certainly correct about how Collections.sort() works, I suspect it will be a bit faster.

However, even better is probably:
List<Map.Entry<String, Integer>> representationEntries = new ArrayList<>(representations.entrySet());

The fact is Collections.sort() doesn't care what kind of List it's sorting, so it's usually best not to restrict it.

Indeed, it's almost always better to use interfaces for collections except when you're actually creating them. It's part of a technique called "programming to the interface", and applies to things other than just collections too.

HIH

Winston
 
Divyanand Kutagulla
Greenhorn
Posts: 18
C++ Suse Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:

Divyanand Kutagulla wrote:Further to my question I modifiwd my sorting code thus:


Looks fine, and although Matthew is almost certainly correct about how Collections.sort() works, I suspect it will be a bit faster.

However, even better is probably:
List<Map.Entry<String, Integer>> representationEntries = new ArrayList<>(representations.entrySet());

The fact is Collections.sort() doesn't care what kind of List it's sorting, so it's usually best not to restrict it.

Indeed, it's almost always better to use interfaces for collections except when you're actually creating them. It's part of a technique called "programming to the interface", and applies to things other than just collections too.

HIH

Winston



Hi Winston,

Thank you for your answers/insights to my questions.

This post and the other post on Map Iteration ( sorry dunno how to link it) were motivated by my experiments with collections and the Date, Calendar and locale classes.
I am am prepping for the OCP 7 upgrade exam and (i am a 1.2 certified programmer), and thought I'd write some code to help to understand what I am learning.

Any ways thanks for all your help!

Thanks,
Divyanand
 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Divyanand Kutagulla wrote:This post and the other post on Map Iteration ( sorry dunno how to link it) were motivated by my experiments with collections and the Date, Calendar and locale classes.
I am am prepping for the OCP 7 upgrade exam and (i am a 1.2 certified programmer), and thought I'd write some code to help to understand what I am learning.


Ooof. Good luck with that - the absolute worst "framework" in the Java foundation class system (and I say that as someone who loves Java) - and thankfully upgraded in version 8. Glad I don't have to do exams on it anymore.

I'm still puzzled as to how map sorting relates to the date/time system though; but I'm sure you have your reasons.

Winston
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic