Beschouw een collectie \(U\) van \(n\) data-elementen (items) die in het centrale geheugen opgeslagen zijn. Er is ook een snellere cache beschikbaar, waarin \(k<n\) items tegelijkertijd kunnen in opgeslagen worden. Veronderstel dat de cache aanvankelijk \(k\) items bevat.

Gegeven is een reeks items \(D = d_1,d_2,\ldots,d_m\) van items uit \(U\) die achtereenvolgens opgevraagd worden. Voor elk moment moeten we beslissen welke items in de cache te bewaren. Wanneer item \(d_i\) opgevraagd wordt, hebben we zeer snelle toegang als het zich in de cache bevindt; anders moet het naar de cache gebracht worden en een ander item moet uit de cache verwijderd worden om plaats te maken voor \(d_i\) (wanneer de cache vol is) - dit wordt een uitzetting (of eviction) genoemd.

Het is de bedoeling een uitzettingsschema op te stellen dat voor een gegeven reeks opvragingen zo weinig mogelijk uitzettingen gebruikt.

Opgave

Schrijf een Python-functie optimaliseer(elementen: list, cache: set, k: int) met als parameters een reeks van elementen, een begintoestand van de cache en een getal \(k\) dat de grootte van de cache voorstelt. De functie moet een lijst teruggeven die voor elke stap \(i\) het element weergeeft dat op stap \(i\) uit de cache wordt verwijderd. Indien er geen element in stap \(i\) wordt verwijderd moet er None staan.

Voorbeelden

>>> optimaliseer(['a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c'], {'b', 'c'}, 2)
['c', None, 'b', None, 'a', None, 'c', None, 'a']
>>> optimaliseer(['a', 'b', 'a', 'b', 'a', 'b', 'a', 'b'], {'a'}, 1)
[None, 'a', 'b', 'a', 'b', 'a', 'b', 'a']
>>> optimaliseer(['a', 'b', 'c', 'b', 'c', 'a', 'b'], {'a', 'b'}, 2)
[None, None, 'a', None, None, 'c', None]
>>> optimaliseer(['a', 'b', 'c', 'd', 'a', 'd', 'e', 'a', 'd', 'b', 'c'], {'a', 'b', 'c'}, 3)
[None, None, None, 'c', None, None, 'b', None, None, 'e', 'b']
>>> optimaliseer(['a', 'b', 'a', 'b'], {'a', 'b'}, 2)
[None, None, None, None]
>>> optimaliseer(['a', 'b', 'c', 'd'], set(), 2)
[None, None, 'a', 'c']