• Post Reply Bookmark Topic Watch Topic
  • New Topic

Sorting Map  RSS feed

 
Jeff Gent
Ranch Hand
Posts: 44
Eclipse IDE IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm trying to sort some values and maintain a key so I know the associated order. However, it doesn't appear to be very efficient - cpu or memory wise. Any suggestions on how to do this better.

mapwords.put(int, int);
...
Map tempmap = MapSortedByValue.createMapSortedByValue(mapwords);
Then iterate through the tempmap to assign the order.

 
Jesper de Jong
Java Cowboy
Sheriff
Posts: 16057
88
Android IntelliJ IDE Java Scala Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Why exactly do you think it is not very CPU- or memory-efficient? Is this a real performance problem in your application or is it just because you have a feeling (without evidence) that it's a problem?
 
Jeff Gent
Ranch Hand
Posts: 44
Eclipse IDE IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jesper de Jong wrote:Why exactly do you think it is not very CPU- or memory-efficient? Is this a real performance problem in your application or is it just because you have a feeling (without evidence) that it's a problem?

A Java Profiler. The performance is a matter of scale. Works great with smaller-mid size data sets. I'm trying to improve the scale, so if I can do this better, I'd like to.
 
Matthew Brown
Bartender
Posts: 4568
9
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I've no idea if it affects things, but one thing that stands out to me as a bit strange is that the SortByIntegerComparator takes your Map as a constructor argument. A Comparator should just compare two values - it shouldn't need to know the entire list. And an inefficient Comparator will certainly lead to an inefficient sort algorithm, because it will be called lots of times. Maybe you could show us the code for that?
 
Jeff Gent
Ranch Hand
Posts: 44
Eclipse IDE IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Matthew Brown wrote:I've no idea if it affects things, but one thing that stands out to me as a bit strange is that the SortByIntegerComparator takes your Map as a constructor argument. A Comparator should just compare two values - it shouldn't need to know the entire list. And an inefficient Comparator will certainly lead to an inefficient sort algorithm, because it will be called lots of times. Maybe you could show us the code for that?

Ahh, ya - should have included that. Here it is...
 
Jesper de Jong
Java Cowboy
Sheriff
Posts: 16057
88
Android IntelliJ IDE Java Scala Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A side note; this won't affect performance, but will make your code more type-safe: you should use generics to make clear what the types of keys and values in your Map are and what types the comparator compares. Apparently your Map contains Integer objects for both keys and values. You can get rid of some casts too if you use generics.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jeff Gent wrote:I'm trying to sort some values and maintain a key so I know the associated order. However, it doesn't appear to be very efficient - cpu or memory wise. Any suggestions on how to do this better.

Like Matthew, I'm a little puzzled as to what it is you're trying to achieve. A TreeMap will take O(n * log(n)) time to load from another collection and will occupy roughly 2 * nodeSize space. An ArrayList, on the other hand, will take O(n + log(n)) time to sort into a particular order (assuming you clone it first) and take only the space needed to store n references; so it really depends on whether you need the dynamic properties of a TreeMap or not. I suspect the business of "maintaining a key so I know the associated order" is a red herring.

Winston
 
Jeff Gent
Ranch Hand
Posts: 44
Eclipse IDE IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston, here is what I'm trying to efficiently achieve.
Let's say I have 1,000,000 objects and one of the values is importance and another is id.
So I'm trying to rank the objects by importance. I don't care about getting a list of the importance values. I just want a list of the id ranked by the object's importance value.

Example (id,importance)
(1,5)
(2,1)
(3,8)
(4,2)
(5,2)

I want the id order.
2
4
5
1
3
 
dennis deems
Ranch Hand
Posts: 808
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If importance is a field on the class, then all the comparator needs to do is look at that field on both objects. There is no need to complicate things by introducing a whole other data structure.
 
Jeff Gent
Ranch Hand
Posts: 44
Eclipse IDE IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dennis Deems wrote:If importance is a field on the class, then all the comparator needs to do is look at that field on both objects. There is no need to complicate things by introducing a whole other data structure.

Sounds great... how would that work exactly.. haha.
Let's say I have this class and I have an ArrayList<MyStuff> mystuff.

I want to create a new Array, List, Map, Hash, whatever works best.. of the id order based on importance.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jeff Gent wrote:Winston, here is what I'm trying to efficiently achieve.
Let's say I have 1,000,000 objects and one of the values is importance and another is id.
So I'm trying to rank the objects by importance. I don't care about getting a list of the importance values. I just want a list of the id ranked by the object's importance value.

Yes, I follow that, but it doesn't answer the whole question. Do you need a structure that dynamically maintains these objects in sorted order, or do you simply need them sorted once you've got them all? The answer to that question will determine what you need to do.

The fact is that whatever you decide, the ordering is done on references, not the objects themselves, so extracting the ID and then sorting them is only likely to add space, while saving you very little time. The code is likely to be very similar no matter what you decide, eg:however, if you only need the sorted data once, you'd probably be better off just cloning the List and sorting it (or indeed, just sorting the list you've got), viz:As you can see, the code to print them out is identical.

Winston
 
dennis deems
Ranch Hand
Posts: 808
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jeff Gent wrote:
Dennis Deems wrote:If importance is a field on the class, then all the comparator needs to do is look at that field on both objects. There is no need to complicate things by introducing a whole other data structure.

Sounds great... how would that work exactly.. haha.
Let's say I have this class and I have an ArrayList<MyStuff> mystuff.

I want to create a new Array, List, Map, Hash, whatever works best.. of the id order based on importance.


1. Create a Comparator<MyStuff> that sorts MyStuff instances based on the importance field.
2a. Call Collections.sort with your mystuff list and the comparator. The list is now sorted by importance.
2b. Alternatively, you can instantiate a TreeSet with the comparator and add everything to that instead. No need in this case to use Collections.sort.

Edit: yeah, as Winston has shown each case. ;)
 
Jeff Gent
Ranch Hand
Posts: 44
Eclipse IDE IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Guys! This should really help
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!