XPage – Sort View Column – Optimized

In my previous post I discussed about sorting a view column using java.util.TreeMap. In this post I shall discuss about some optimizations to address the issue with duplicate values (refer to the line 19-21 in previous post).

Let us calculate time complexity of existing code:

From here: http://java.sun.com/javase/6/docs/api/java/util/TreeMap.html
This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Therefore,

Time complexity of TreeMap.containsKey, T1 = log(n)

Time complexity of TreeMap.put, T2 = log(n)

Time complexity of inner while loop, T3 = n * T1

Total time complexity,
T = n * (T3 + log(n)) log(n) for TreeMap.put
T = n * (n * T1 + log(n))
T = n * (n * log(n) + log(n))
T = n * (n + 1) * log(n)

From above calculation we can hardly do anything with T1 and T2, but we can optimize T3.

Let us modify the code to optimize:

From the API doc of HashMap:
This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets.

Let us calculate the time complexity of this code:

Time complexity of HashMap.containsKey, T4 = K1 , where K is constant

Time complexity of HashMap.get, T5 = K2 , where K2 is constant

Time complexity of HashMap.put, T6 = K3 , where K3 is constant

Total time complexity,
T’ = n * (T4 + T5 + T6 + log(n))
T’ = n * (K1 + K2 + K3 + log(n))
T’ = n * (K + log(n)) , where K = K1 + K2 + K3

It is clear that T’ < T. Hence our new algorithm is much more better than previous one.

Leave a Reply

Your email address will not be published. Required fields are marked *