Fun Stuff > CLIKC
A programming thread!
ankhtahr:
It actually is a Algorithms and Data Structures lecture…
The exercise is number four on this exercise sheet.
I've tried to translate the given task as good as I can here: (refer to the PDF for the picture)
--- Quote ---In computer science results of a time-wise expensive operation are often saved to be able to access them faster later on. Such an expensive operation is for example loading of data from the hard drive to the RAM, or the rendering of downloading of map tiles on a GPS. A data structure which allows this is called "cache". Usually the memory in which the data is to be buffered is too small to back up all requests. In this case some entries need to be removed. Which those are is decided by an eviction strategy.
One of the most common stategies is "Least Recently Used (LRU)", where the entry which hasn't been read for the longest time is deleted. To find this entry one can, instead of using timestamps, combine a doubly linked list with a hash table in an elegant way. The following picture shows the schematical setup of this data structure:
<picture here>
Your task is to implement this in Java. Your data structure should implement a method ValueType retrieve(KeyType key) in O(1), which returns the value to a given key. The hashtable contains all cached elements. The doubly linked list displays the age of these elements. A retrieve first checks whether an entry is already cached, using the hashtable. If this is the case, it needs to be removed from it's current position in the list and moved to the front. Else it needs to be read from the background container (expensive!) and inserted into hashtable and chained list. To solve this task use the following data, which can be retrieved from the lecture website:
ContainerInterface.java: An interface for the underlying operations.
SlowRam.java: An example container which implements this interface.
PagerInterface.java: An interface for the Cache.
Pager.java: An abstract class which implements this interface.
LRUCacheTest.java: A JUnit-class which you can use for testing your class. It's also the task your handed in solution will be pre-checked.
Create a Java Class LRUCache in a file named "LRUCache.java". Your class needs to extend Pager. Only upload this single file. You'll receive one point, if you hand in a non-trivial solution, which passes the JUnit test. You'll receive additional three points if you implement the described structure correctly. You'll then receive four additional points if you implement the hashtable and the chained list yourself, so using neither java.util.HashMap nor a list class.
Hint: Questions like this are often being asked in job interviews.
--- End quote ---
I'd probably want to implement it using java.util.HashMap first, and implement it afterwards.
ankhtahr:
--- Quote from: ankhtahr on 15 May 2014, 12:38 ---I'd probably want to implement it using java.util.HashMap first, and implement it afterwards.
--- End quote ---
Done.
All I need to do now is implement my own HashMap, which behaves like the java.util one, at least in regards to the put, get, remove and containsKey method.
ankhtahr:
Motherfucking Java.
I need an array. Of elements of my self defined list. What do I need to do? Of course:
--- Code: (java) ---DoublyLinkedListElement[] table = (DoublyLinkedListElement[]) new Object[11]
--- End code ---
with a damn @suppressWarnings("unchecked") beforehand. Because Java.
Sadly the system we use to hand in our solutions denies your solution anyway. We've been trying to fuck our way around this fucking language barrier for two hours now. It's 5:49 am. I need some sleep. Also I need to hand it in until noon. But as I have a partner, who has done basically the rest of the exercise sheet, I feel obliged to finish this. I guess I'll stay here until he appears and tells me to go home.
pwhodges:
I'm amused at all this Java shenanigans. When I had to write a cache of this sort (commercially, for money), I sketched it out in pseudocode and then implemented it in assembly language. As I recall it took about 300 bytes. The improvement in OS performance was similar to installing a SSD in modern terms.
Masterpiece:
--- Quote from: ankhtahr on 15 May 2014, 20:49 ---
--- Code: (java) ---DoublyLinkedListElement[] table = (DoublyLinkedListElement[]) new Object[11]
--- End code ---
--- End quote ---
I'm guessing you haven't had generics yet.
Navigation
[0] Message Index
[#] Next page
[*] Previous page
Go to full version