Se le dará una secuencia de solicitudes de memoria y un tamaño de caché. Debe devolver el menor número posible de errores de caché bajo cualquier estrategia de reemplazo de caché.

Una estrategia óptima es el algoritmo de Belady , que puede usar si lo desea.

Un sistema de almacenamiento en caché funciona de la siguiente manera: el caché comienza vacío. Las solicitudes de memoria entran. Si la solicitud solicita un dato en la memoria caché, todo está bien. De lo contrario, incurrirá en una pérdida de caché. En este punto, puede insertar los datos que se solicitaron en la memoria caché para su uso futuro. Si el caché estaba lleno y desea insertar nuevos datos, debe desalojar los datos que estaban previamente en el caché. Nunca puede insertar datos que no estén solo en la memoria caché.

Su objetivo es encontrar el número mínimo posible de errores de caché para una secuencia de solicitud de memoria y un tamaño de caché determinados.

Se le dará el tamaño de caché, un entero positivo y la secuencia de solicitud de memoria, que es una lista de tokens. Estos tokens pueden ser cualquier tipo de tokens que desee, siempre que sean posibles al menos 256 tokens diferentes (los bytes están bien, los bools no). Por ejemplo, ints, strings, lists están bien. Solicite aclaraciones si es necesario.

Casos de prueba:

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

6

Vea wikipedia para una política de reemplazo que logre esto.

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

3

Simplemente evite agregar 2al caché.

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

9

Una forma de lograr esto es por no desalojar 0y 2, desalojando y 1tan pronto como sea posible después de su último uso.

Puntuación: Este es el código de golf. Pocos bytes ganan.

JavaScript (ES6), 128 bytes

Toma entrada como (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

Pruébalo en línea!

Comentado

Esta es una implementación del algoritmo de Belady.

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
}

Pruébalo en línea!

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 sin sangría, líneas nuevas, espacios, comentarios:

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ÃÙ]¾

Pruébalo en línea!

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=(#[])

Pruébalo en línea!

Explicación

Funciona por fuerza bruta: se prueban todas las estrategias de caché y se devuelve el mejor resultado.

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};$!}

Pruébalo en línea!