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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
var loView:NotesView = null; var loEntryColl:NotesViewEntryCollection = null; var loTreeMap:java.util.TreeMap = new java.util.TreeMap(); var lsSortBy = viewScope.get("sortBy"); try { loView = database.getView("view"); if(null == lsSortBy || "" == lsSortBy) { lsSortBy = 0; } if(null != loView && loView.getEntryCount() > 0) { loEntryColl = loView.getAllEntries(); var loEntry:NotesViewEntry = loEntryColl.getFirstEntry(); var loTempEntry:NotesViewEntry = null; var keys:java.util.HashMap = new java.util.HashMap(); while(null != loEntry) { loDoc = loEntry.getDocument(); var lsKey = loEntry.getColumnValues().get(lsSortBy); if(keys.containsKey(lsKey)) { var k = keys.get(lsKey); lsKey = @LowerCase(lsKey); k += "~"; keys.put(lsKey, k); lsKey += k; } else { keys.put(lsKey, '~'); } /*while(loTreeMap.containsKey(lsKey)) { lsKey += "~"; }*/ loTreeMap.put(lsKey, loEntry.getColumnValues()); loTempEntry = loEntryColl.getNextEntry(loEntry); loEntry.recycle(); loEntry = loTempEntry; } } } catch(e) { print("Error : " + e); } finally { if(null != loView) loView.recycle(); if(null != loEntryColl) loEntryColl.recycle(); } return loTreeMap.values(); |

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.