This week's book giveaway is in the Servlets forum.
We're giving away four copies of Murach's Java Servlets and JSP and have Joel Murach on-line!
See this thread for details.
The moose likes Java in General and the fly likes Why & how to build map of maps? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Why & how to build map of maps?" Watch "Why & how to build map of maps?" New topic
Author

Why & how to build map of maps?

ramya narayanan
Ranch Hand

Joined: Oct 06, 2008
Posts: 338
Dear all,
In my project, I want to optimize a performance of a method from O(N) to O(Nlogn) .
My method actually iterates over a collection , searches it & finds the value which results in a O(N) performance.
To improve its performance to O(Nlogn),the solution approach is given as to build a map of maps using Treemap & comparator.
How to build a map of maps?

I need to build a Hashmap in which value of a key should be another map?
I suppose it would be like this?


import java.util.*;
class MapOfMaps
{
public static void main(String[] args)
{
TreeMap treemap=new TreeMap();
//Here the value 10 is assigned to key "sai" which will be used as a key in another element.
treemap.add("sai",10);
treemap.add("ramya","sai");
.....
.....
.....

}
}


1)Am I right ?
2) Why they are building & using these kind of map of maps. what is its use?
please clarify?
Regards.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 37926
    
  22
By, "optimise from O(N) to O(nlogn)," I presume you mean, "optimise from O(Nlogn) to O(n)."

That doesn't look right for what you are asking; you would want a Map<String, Map<Foo, Bar>>, or similar.
It sounds a very complicated way to work out performance; what are you going to sort on? Are you putting some sort of duration value into the Maps? (That would probably be a Long.) There must be better and easier ways to calculate performance.
ramya narayanan
Ranch Hand

Joined: Oct 06, 2008
Posts: 338
I presume you mean, "optimise from O(Nlogn) to O(n)."

No, to optimise the performance so that the cost of processing is O(N log N).

what are you going to sort on? Are you putting some sort of duration value into the Maps?

I'm going to sort on an collection. That method uses a O(n) method to find an detail from the collection.This should be updated in order to allow a more efficient algorithm to be used so that at most the cost of processing is O(N log N).

The sample method is:

ISCCMQuotaDetail getQuotaDetail(ISCCMAllocation allocation,
ISCCMDirectPromotion directPromotion, ISCCMQuotaState quotaState,
ISCCollection details) {
trace.println("!!getQuotaDetail method");
ISCCMQuotaDetail quotaDetail = null;

for (Enumeration detailsEnum = details.elements(); detailsEnum
.hasMoreElements() {
ISCCMQuotaDetail qd = (ISCCMQuotaDetail) detailsEnum.nextElement();
if (qd.getAllocation().equals(allocation)
&& qd.getQuota().equals(directPromotion.getQuota())
&& qd.getQuotaState().equals(quotaState)) {
return qd;
}
}

return quotaDetail;

}

The solutions approach is:
The for loop in CMEngineComponentAccumulate.getQuotaDetail should be removed and replaced by a lookup to a TreeMap or something similar that will allow each individual lookup to occur in O(log N) time rather than O(N).

In direct Comp memory, we should iterate over all of the details and build a map of maps.
For each quota detail - qd, the key for the first map would be the qd.getAllocation() and the value would be a second map. The second map would be keyed by qd.getQuotaState() and the value would be the quota detail.
The Maps should all be of type TreeMap, which will require the implementation of a comparator that should be driven off each objects GID.
Within processAllocation, we can then do one lookup to get the map of quota details for the allocation being processed and in turn update 'updateQuotaState' to use the map that we get back to obtain the quota detail.
Note: Do NOT modify any of the SCCollection files.



Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 37926
    
  22
I am finding this thread hard to understand. Is this for an algorithms assignment?

Copying the entire contents of a Collection into an ordered Collection or a TreeMap can easily be done, but I think that would run in at best O(nlogn) time, then each search will run in O(logn) time.

Why are you using an Enumeration rather than an Iterator in your loop?
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 2983
    
    9
[ramya]: In my project, I want to optimize a performance of a method from O(N) to O(Nlogn) .

How is that an optimization? O(N) is better than O(N*log(N)), at least asymptotically.
Matteo Di Furia
Ranch Hand

Joined: Jun 20, 2008
Posts: 102
Originally posted by Mike Simmons:
[ramya]: In my project, I want to optimize a performance of a method from O(N) to O(Nlogn) .

How is that an optimization? O(N) is better than O(N*log(N)), at least asymptotically.


O(N) is better than O(N log N) starting from N=2 (in this case log N means log on base 2), no need to go that far away. I can't really understand where is the improvement we are discussing here.
[ October 31, 2008: Message edited by: Matteo Di Furia ]
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 2983
    
    9
[Matteo]: O(N) is better than O(N log N) starting from N=2 (in this case log N means log on base 2), no need to go that far away.

Remember, big O notation ignores constants. It's possible that O(N) represents an equation like

    time = 10000000 * N

while O(N * log(N)) represents

    time = 0.0001 * N * log(N)

In this case the O(N * log(N)) would be better unless N is very large. Of course, it's also possible that the situation is reversed. We really don't know in general. That's why testing of actual performance is important.

Also, the difference between log base 2 and log base 10 or natural logarithms (base e) is unimportant when using big O notation. Logs in each base are proportional to each other, and so that's just another constant of proportionality that drops out.
ramya narayanan
Ranch Hand

Joined: Oct 06, 2008
Posts: 338
At the outset I would like to clarify that I'm a novice when it comes to algorithms.
We've been supporting a project, in which I've been asked to update a algorithm so that its performance improved to O(N log N)
Remember, big O notation ignores constants. It's possible that O(N) represents an equation like

time = 10000000 * N

while O(N * log(N)) represents

time = 0.0001 * N * log(N)

In this case the O(N * log(N)) would be better unless N is very large.


In my case, the value of N is large i.e. collection elements is huge.

Copying the entire contents of a Collection into an ordered Collection or a TreeMap can easily be done

I do hope you are saying that this can be done using the copy method
But what I want to do is to have a ordered Tree map , which builds a map of maps, as given in the solution approach.
The for loop in CMEngineComponentAccumulate.getQuotaDetail should be removed and replaced by a lookup to a TreeMap or something similar that will allow each individual lookup to occur in O(log N) time rather than O(N).

In direct Comp memory, we should iterate over all of the details and build a map of maps.
For each quota detail - qd, the key for the first map would be the qd.getAllocation() and the value would be a second map. The second map would be keyed by qd.getQuotaState() and the value would be the quota detail.
The Maps should all be of type TreeMap, which will require the implementation of a comparator that should be driven off each objects GID.
Within processAllocation, we can then do one lookup to get the map of quota details for the allocation being processed and in turn update 'updateQuotaState' to use the map that we get back to obtain the quota detail.

Actually I want to know how to build a map of maps eventhough there is a difference of opinion on whether this would improve the performance .
Regards.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 37926
    
  22
I told you what you need in my first reply. Wasn't that sufficient?
ramya narayanan
Ranch Hand

Joined: Oct 06, 2008
Posts: 338
No I just want to know about other's opinion on this?
Martijn Verburg
author
Bartender

Joined: Jun 24, 2003
Posts: 3274
    
    5

I'm with Campbell on this one if it helps


Cheers, Martijn - Blog,
Twitter, PCGen, Ikasan, My The Well-Grounded Java Developer book!,
My start-up.
ramya narayanan
Ranch Hand

Joined: Oct 06, 2008
Posts: 338
Sorry , the requirement is to optimise the performance from O(n) to O(logn).
In this case, I'm planning to build two tree maps, T1 and T2
where T2 will be called as value in T1.
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 2983
    
    9
Excellent. I'm glad you were able to clear that up. So, are you still looking for something from us? I can't tell. If so, what? Campbell's first few responses still sounds good to me. If you want more, you should probably show some effort and tell the details. If you just want to collect more opinions, without more effort on your part, that's not going to go very far. Good luck.
[ November 04, 2008: Message edited by: Mike Simmons ]
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 37926
    
  22
Originally posted by ramya narayanan:
Sorry , the requirement is to optimise the performance from O(n) to O(logn).


Aaah. Now I understand.
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Why & how to build map of maps?
 
Similar Threads
How to sort a map descendingly
TreeMap containsKey issue
Danchisholms: Collections question
what collection class to use??
Calling one map from another