Take the 2-minute tour ×

I have a table Rating

  • row1 = (V1, K1, 5);
  • row2 = (V2, K2, 7);
  • row2 = (V1, K1, 3);

I need to aggregate the Points in an AggregateRating table such that the table contains

  • row1 = (V1, K1, 8);
  • row2 = (V2, K2, 7);

I loop once through the Rating table and create a map with [key = (Col1,Col2), value = Points] If the key exists I add the points else create a new map entry. The Rating table can contain close to 100+ entries so I wanted to avoid making multiple passes.

Is this the most efficient way to go about it??

share|improve this question
Unless the + in 100+ doesn't mean billions you should stick with a clean and efficient implementation as you suggested. The most efficient solutions are seldomly needed. –  Howard Apr 7 '12 at 7:56
@Howard what kind of more efficient solution do you mean? Btw if the query is made a billion times it might be of importance to reduce its complexity 100 times. –  Boris Strandjev Apr 7 '12 at 8:00
@Boris Exactly what I meant. There is a difference between "most efficient" and "efficient in the real world". All kind of "dirty" things like prefetching, sizes of cache lines... come into play. And it matters if you have data in the billions range but not for 100+. In this region you should keep the solution simple and understandable - i.e. efficient for the coder and all others reading your code (of course without hurting system's performance unneccessarily). –  Howard Apr 7 '12 at 8:05
add comment

1 Answer

up vote 0 down vote accepted

It depends on what data structure you use to store the map. If you use hash map than storing and reading from it will be constant in complexity (O(1)). Then you make a single pass with one query and at most one insert for every entry in the array. This means that the whole complexity of your algorithm will be O(n).

However, the input alone is O(n), which means you can not do any better.

Keep in mind that if you choose different implementation of the map, e.g. tree map, the complexity will change and you will not get the most efficient solution.

share|improve this answer
Thanks, yup I am using a HashMap –  Oliver Apr 10 '12 at 16:05
add comment

Your Answer


