0

For example, what I need to implement at the moment is called the Submission history. This requires me to use data-structure that takes better than O(n) for each of its methods, and someone told me to use

HashMap<studentId, TreeMap<Date, studentScore>>

since,

getBestGrade method: find all submission for student in O(1) and then find best submission in O(N) (You can improve it by caching best score).

So my question is, how would I approach to use caching for the getBestGrade? What I am thinking is, first make a class for the tree-map and add methods of put, remove and getBestGrade in it. Than I just call it back in the another class.

Also, how does the use of caching reduce the time-complexity(big-O)?

Please help... thanks.

승기유
  • 133
  • 9
  • 1
    By having a separate Map that maps the student-id to max-score you'll implement a primitive cache that will require O(1) to get the best submission of a student. – Nir Alfasi Sep 19 '17 at 04:51
  • So, is my opinion in the right track to do caching? – 승기유 Sep 19 '17 at 04:54
  • For example, in the main class, assuming that it is called Assignment, I declare the map of maps (hash-map containing the tree-map), named as 'map'. Then I make a sub class called StudentScore for the tree-map then add methods (put, remove, GetBestGrade) in it. Finally, in the main class, for the getBestGrade method, I write down like, StudentScoreSet t = map.get(studnetId); return t.GetBestGrade(); – 승기유 Sep 19 '17 at 04:56
  • 1
    If you're using a treemap you can call [`lastKey`](https://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html#lastKey()) to get the highest score – Nir Alfasi Sep 19 '17 at 04:59
  • Does performing lastKey require caching? – 승기유 Sep 19 '17 at 05:01
  • getBestGrade method: find all submission for student in O(1) and then find best submission in O(N) (You can improve it by caching best score). In that sentence, just finding best submission is like what you just said, lastKey but the sentence says that it takes O(n) time – 승기유 Sep 19 '17 at 05:02
  • Treemap is also a map which means access in O(1) – Nir Alfasi Sep 19 '17 at 05:19

1 Answers1

0

It is called memoization method(technique). In Java 8, there are new features for this issue, here is the link. It depends on the frequency of the repeating the operation that you cached the old data. You should manage the cache size, of course. It may provide you some advantages however, it may also going to kill your memory. Here is an example.

BTW, this is a good way to store the data. Acess will take O(1) with given studentId and Date keys.

HashMap<studentId, TreeMap<Date, studentScore>>
Oguz
  • 1,867
  • 1
  • 17
  • 24