ramya narayanan

Ranch Hand

Posts: 338

posted 8 years ago

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?

1)Am I right ?

2) Why they are building & using these kind of map of maps. what is its use?

please clarify?

Regards.

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

Marshal

Posts: 55772

163

posted 8 years ago

By, "optimise from O(N) 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.

*log*n)," I presume you mean, "optimise from O(N*log*n) 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

posted 8 years ago

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

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:

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

Marshal

Posts: 55772

163

posted 8 years ago

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(n

Why are you using an Enumeration rather than an Iterator in your loop?

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(n

*log*n) time, then each search will run in O(*log*n) time.Why are you using an Enumeration rather than an Iterator in your loop?

Mike Simmons

Ranch Hand

Posts: 3090

14

Matteo Di Furia

Ranch Hand

Posts: 102

posted 8 years ago

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 ]

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) isbetterthan 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: 3090

14

posted 8 years ago

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

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.

**[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

posted 8 years ago

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)

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

I do hope you are saying that this can be done using the

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.

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.

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**methodBut 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

Marshal

Posts: 55772

163

ramya narayanan

Ranch Hand

Posts: 338

posted 8 years ago

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

Posts: 338

Mike Simmons

Ranch Hand

Posts: 3090

14

posted 8 years ago

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 ]

[ November 04, 2008: Message edited by: Mike Simmons ]