This week's book giveaway is in the Design forum.We're giving away four copies of Design for the Mind and have Victor S. Yocco on-line!See this thread for details.
Win a copy of Design for the Mind this week in the Design forum!

# Why & how to build map of maps?

ramya narayanan
Ranch Hand
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.
.....
.....
.....

}
}

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

Campbell Ritchie
Sheriff
Posts: 48652
56
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
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:

ISCCMDirectPromotion directPromotion, ISCCMQuotaState quotaState,
ISCCollection details) {

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

}

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
Posts: 48652
56
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
Posts: 3036
10
[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
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
Posts: 3036
10
[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
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
Posts: 48652
56
I told you what you need in my first reply. Wasn't that sufficient?

ramya narayanan
Ranch Hand
Posts: 338
No I just want to know about other's opinion on this?

Martijn Verburg
author
Bartender
Posts: 3275
5
I'm with Campbell on this one if it helps

ramya narayanan
Ranch Hand
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
Posts: 3036
10
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
Posts: 48652
56
Originally posted by ramya narayanan:
Sorry , the requirement is to optimise the performance from O(n) to O(logn).

Aaah. Now I understand.