Sie erhalten eine Folge von Speicheranforderungen und eine Cache-Größe. Sie müssen die geringstmögliche Anzahl von Cache-Fehlern unter einer Cache-Ersetzungsstrategie zurückgeben.

Eine optimale Strategie ist Beladys Algorithmus , den Sie verwenden können, wenn Sie möchten.

Ein Cachesystem funktioniert folgendermaßen: Der Cache beginnt leer. Speicheranforderungen kommen herein. Wenn die Anforderung nach einem Datenelement im Cache fragt, ist alles in Ordnung. Andernfalls tritt ein Cache-Fehler auf. An dieser Stelle können Sie die angeforderten Daten zur späteren Verwendung in den Cache einfügen. Wenn der Cache voll war und Sie neue Daten einfügen möchten, müssen Sie die zuvor im Cache befindlichen Daten löschen. Sie dürfen niemals Daten einfügen, die sich nicht nur im Cache befanden.

Ihr Ziel ist es, die minimal mögliche Anzahl von Cache-Fehlern für eine bestimmte Speicheranforderungssequenz und Cache-Größe zu finden.

Sie erhalten die Cachegröße, eine positive Ganzzahl und die Speicheranforderungssequenz, bei der es sich um eine Liste von Tokens handelt. Diese Token können jede Art von Token sein, die Sie mögen, solange mindestens 256 verschiedene Token möglich sind (Bytes sind in Ordnung, Bools nicht). Zum Beispiel sind Ints, Strings und Listen in Ordnung. Bitten Sie bei Bedarf um Klärung.

Testfälle:

3
[5, 0, 1, 2, 0, 3, 1, 2, 5, 2]

6

Eine entsprechende Ersatzrichtlinie finden Sie in Wikipedia .

2
[0, 1, 2, 0, 1, 0, 1]

3

Vermeiden Sie einfach das Hinzufügen 2zum Cache.

3
[0, 1, 2, 1, 4, 3, 1, 0, 2, 3, 4, 5, 0, 2, 3, 4]

9

Eine Möglichkeit, dies zu erreichen, besteht darin, niemals 0und so bald wie möglich nach seiner letzten Verwendung zu 2vertreiben 1.

Wertung: Dies ist Codegolf. Wenigste Bytes gewinnt.

JavaScript (ES6), 128 Byte

Übernimmt die Eingabe als (size)(list).

s=>a=>a.map((x,i)=>c.includes(x)?0:c[e++,[x,...c].map(m=(x,j)=>(k=[...a,x].indexOf(x,i+1))<m||(p=j,m=k)),i<s?i:p-1]=x,e=c=[])&&e

Probieren Sie es online!

Kommentiert

Dies ist eine Implementierung von Beladys Algorithmus.

s => a =>                      // s = cache size; a[] = token list
  a.map((x, i) =>              // for each token x at position i in a[]:
    c.includes(x) ?            //   if x is currently stored in the cache:
      0                        //     do nothing
    :                          //   else:
      c[                       //     update the cache:
        e++,                   //       increment the number of errors (cache misses)
        [x, ...c]              //       we want to find which value among x and all current
                               //       cache values will be needed for the longest time in
                               //       the future (or not needed anymore at all)
        .map(m =               //       initialize m to a non-numeric value
                 (x, j) =>     //       for each x at position j in this array:
          ( k = [...a, x]      //         k = position of x in the array made of all values
            .indexOf(x, i + 1) //         of a[] followed by x, starting at i + 1
          ) < m                //         if it's greater than or equal to m, or m is
          || (p = j, m = k)    //         still non-numeric: set p to j and m to k
        ),                     //       end of inner map()
        i < s ?                //       if i is less than the cache size:
          i                    //         just fill the cache by using the next cache slot
        :                      //       else:
          p - 1                //         use the slot that was found above
                               //         special case: if p = 0, x was the best candidate
                               //         and we're going to store it at c[-1], which is
                               //         simply ignored (it will not trigger c.includes(x))
      ] = x,                   //     store x at this position
      e = c = []               //     start with e = [] (coerced to 0) and c = []
  ) && e                       // end of outer map; return e

Perl 5 , 193 Bytes

sub g{
  my($i,$m,$s,@a,%c)=(-1,0,@_);
  for(@a){
    $i++;
    next if $c{$_}++ || ++$m && keys%c <= $s;
    my($x,$d);
    for $k (sort keys %c){  #find which to delete, the one furtherst away
      my $n=0;
      ++$n && /^$k$/ && last for @a[$i+1..$#a];
      ($x,$d)=($n,$k) if $n>$x
    }
    delete $c{$d}
  }
  $m
}

Probieren Sie es online!

print g(3,  5, 0, 1, 2, 0, 3, 1, 2, 5, 2),"\n";                     # 6
print g(2,  0, 1, 2, 0, 1, 0, 1),"\n";                              # 3
print g(3,  0, 1, 2, 1, 4, 3, 1, 0, 2, 3, 4, 5, 0, 2, 3, 4),"\n";   # 9

193 Bytes ohne Einrückung, Zeilenumbrüche, Leerzeichen, Kommentare:

sub g{my($i,$m,$s,@a,%c)=(-1,0,@_);for(@a){$i++;next if$c{$_}++||++$m&&keys%c<=$s;my($x,$d);for$k(sort keys%c){my$n=0;++$n&&/^$k$/&&last for@a[$i+1..$#a];($x,$d)=($n,$k)if$n>$x}delete$c{$d}}$m}

05AB1E , 20 Bytes

vI∍Dyå≠i¼yª¹N.$sÃÙ]¾

Probieren Sie es online!

Haskell , 82 Bytes

f n|let(d:t)#c=1-sum[1|elem d c]+minimum[t#take n e|e<-scanr(:)(d:c)c];_#_=0=(#[])

Probieren Sie es online!

Erläuterung

Funktioniert mit brachialer Gewalt: Alle Cache-Strategien werden ausprobiert und das beste Ergebnis wird zurückgegeben.

f n            Define a function f on argument n (cache size) and a list (implicit).
 |let(d:t)#c=  Define binary helper function #.
               Arguments are list with head d (current data) and tail t (remaining data), and list c (cache).
 1-            It returns 1 minus
 sum[1|        1 if
 elem d c]+    d is in the cache, plus
 minimum[      minimum of
 t#            recursive calls to # with list t
 take n e|     and cache being the first n values of e, where
 e<-           e is drawn from
 scanr(:)  c]  the prefixes of c
 (d:c)         with d and c tacked to the end.
 ;_#_=0        If the first list is empty, return 0.
 =(#[])        f then calls # with the list argument and empty cache.

Perl 6 , 146 Bytes

->\a,\b {$_=set();$!=0;for b.kv ->\i,\v {$_{v}&&next;++$!;v∈b[i^..*]||next;$_∖=.keys.max({(grep $_,:k,b[i^..*])[0]//Inf})if $_>=a;$_∪=v};$!}

Probieren Sie es online!