![]() |
![]() DAY 1 :: Task 2 :: Desciption Description in greek :: Solution :: Data sets Back to Day 1 problems - solutions - data sets TASK 2 - Requests Assume that we have a collection of equal size objects, a cache that can store K objects and a sequence of N requests for objects of the collection. Each request for an object is associated with an expiration timestamp, which declares the validity of the object, i.e. until when this object is valid. A request for an object in the cache that has not expired yet, incurs at no cost. When the requested object is not in the cache or it exists in the cache but has expired, we must fetch it into the cache at the cost of one unit. The cost of updating only the expiration time of an object is zero. When a new object or a new version of an object (that is the object exists in the cache, though it is expired) is to be inserted into a full cache, a replacement algorithm determines which of the currently cached objects to evict so that the new one is accommodated. At the beginning, the cache is empty. Your task is to devise the replacement algorithm that incurs the least cost. Note : All requests are known beforehand. Input Your program should read the input from a file "requests.in". The first line of the file contains an integer K representing the cache capacity in terms of the number of objects (where 6= K = 100). The second line contains an integer N representing the number of requests (where 61= N =1000). Each of the next N lines contains a pair of integers P and Q . P is the requested object, whereas Q is the expiration time (absolute time) of the object (inclusive). After each request, the absolute time advances by one unit. The first request occurs at time 1. Output Your program should write the output into a file "requests.out" with a single line containing an integer, the cost of the replacement algorithm. Example
Format : In both input and output files, all numbers in a line are separated with a single space and all lines terminate with a newline character. Time limit : 1 second DAY 1 :: Task 2 :: Desciption in greek Θέμα 2 - Απαιτήσεις ( Requests ) Υποθέστε ότι έχουμε μία συλλογή από αντικείμενα του ιδίου μεγέθους, μία λανθάνουσα μνήμη ( cache ) στην οποία μπορούν να αποθηκευτούν Κ αντικείμενα και μία σειρά ( sequence ) από Ν απαιτήσεις ( requests ) αντικειμένων από την συλλογή. Κάθε ζήτηση ( request ) ενός αντικειμένου συνδέεται με ένα χρόνο λήξεις, ο οποίος δείχνει την εγκυρότητα του αντικειμένου, δηλ. μέχρι το αντικείμενο να θεωρείτε έγκυρο. Η ζήτηση ( request ) ενός αντικειμένου που βρίσκεται ήδη στην λανθάνουσα μνήμη ( cache ) και του οποίου ο χρόνος δεν έχει ακόμη λήξει, εκπληρώνεται χωρίς κανένα κόστος. Εάν το ζητούμενο ( requested ) αντικείμενο δεν βρίσκεται στην λανθάνουσα μνήμη ( cache ) ή εάν βρίσκεται στην λανθάνουσα μνήμη ( cache ) αλλά ο χρόνος του έχει λήξει, πρέπει να το μεταφέρουμε ( fetch ) στην λανθάνουσα μνήμη ( cache ) με κόστος μιας μονάδας. Το κόστος ανανέωσης μόνο του χρόνου λήξεις ενός αντικειμένου είναι μηδέν. Εάν η λανθάνουσα μνήμη ( cache ) είναι γεμάτη και ένα αντικείμενο ή μία νέα έκδοση ενός αντικειμένου (Δηλ. το αντικείμενο υπάρχει στην λανθάνουσα μνήμη ( cache ), αλλά ο χρόνος του έχει λήξει) πρόκειται να εισαχθεί στην γεμάτη λανθάνουσα μνήμη ( cache ), τότε ένας αλγόριθμος αντικατάστασης θα αποφασίσει ποιο από τα αντικείμενα που βρίσκονται στην λανθάνουσα μνήμη ( cache ) θα αποσυρθεί για να εισαχθεί το νέο αντικείμενο. Αρχικά η λανθάνουσα μνήμη ( cache ) είναι άδεια. Ο στόχος σας είναι να δημιουργήσετε τον αλγόριθμο αντικατάστασης που θα απαιτήσει το ελάχιστο κόστος. Σημείωση: Όλες οι Απαιτήσεις ( requests ) είναι γνωστές εκ των προτέρων. Είσοδος Το πρόγραμμά σας πρέπει να διαβάζει τα δεδομένα από το αρχείο εισόδου "requests . in". Η πρώτη γραμμή του αρχείου περιέχει έναν ακέραιο αριθμό Κ ο οποίος αντιπροσωπεύει το μέγεθος της λανθάνουσα μνήμης ( cache ) σε σχέση με τον αριθμό των αντικειμένων (όπου 6?Κ?100). Η δεύτερη γραμμή περιέχει έναν ακέραιο αριθμό Ν ο οποίος αντιπροσωπεύει τον αριθμό των απαιτήσεων ( requests ) (όπου 61?Ν?1000). Κάθε μία από τις επόμενες Ν γραμμές περιέχει ένα ζεύγος ακεραίων αριθμών P και Q . P είναι το αντικείμενο που απαιτήθηκε ( requested ), ενώ Q είναι ο χρόνος λήξεις (απόλυτος χρόνος) του αντικειμένου (συμπεριλαμβανομένου). Μετά από κάθε απαίτηση ( request ), ο απόλυτος χρόνος αυξάνεται κατά μία μονάδα. Η πρώτη απαίτηση ( request) συμβαίνει στον χρόνο 1. Έξοδος Το πρόγραμμά σας πρέπει να γράψει τα αποτελέσματα στο αρχείο "requests . out" σε μία γραμμή η οποία να περιέχει έναν ακέραιο αριθμό, το κόστος του αλγόριθμου αντικατάστασης. Παράδειγμα
Μορφή: Και στα δύο αρχεία εισόδου και εξόδου, όλοι οι αριθμοί στην κάθε γραμμή διαχωρίζονται μεταξύ τους από ένα κενό χαρακτήρα, και όλες οι γραμμές τελειώνουν με το χαρακτήρα γραμμής ( newline character ). Χρονικό όριο: 1 δευτερόλεπτο DAY 1 :: Task 2 :: Solution This problem comes from the area of caching in telecommunication applications, with the extension of known expiration times of cached data. The classical caching problem is stated as follows: we have a database with n items, a cache that can store k items, and a sequence of requests for items in the database. When a requested item is in the cache we incur no cost, but when the requested item is not in the cache we must bring it into the cache at a cost of one unit. When a new item is to be inserted into a full cache, a caching algorithm determines which of the currently cached items to evict in order to accommodate the new one. The optimal offline solution is to evict the item in the cache whose next request is farthest forward, due to Belady . It is obvious that in the presence of expiration timestamps an expired version of a requested item cannot yield a cache hit and in this way cannot be used after it expires. Thus, a request incurs a fault unless the requested item is in the cache and has not yet expired The optimal offline algorithm in the presence of expiration timestamps
is a modification of the Belady algorithm: if there are items in the cache
that are expired at their next use, choose one of them to evict from the
cache. Otherwise, evict the item whose next use is farthest
forward. L. Belady, “A study of replacement algorithms for
virtual storage computers,” IBM Systems Journal, vol. 5, pp. 78–101,
1966 DAY 1 :: Task 2 :: Data sets
| ||||||||||
Organized by |
the Greek Computer Society |
and the |
|||||||||
![]() | |||||||||||
|