Vous recevrez une séquence de demandes de mémoire et une taille de cache. Vous devez renvoyer le moins possible d'échecs de cache dans toute stratégie de remplacement de cache.

Une stratégie optimale est l'algorithme de Belady , que vous pouvez utiliser si vous le souhaitez.

Un système de mise en cache fonctionne comme suit: Le cache commence vide. Les demandes de mémoire entrent. Si la demande demande un morceau de données dans le cache, tout va bien. Sinon, vous encourez un échec de cache. À ce stade, vous pouvez insérer les données demandées dans le cache pour une utilisation future. Si le cache était plein et que vous souhaitez insérer de nouvelles données, vous devez supprimer les données qui se trouvaient précédemment dans le cache. Vous ne pouvez jamais insérer de données qui n'étaient pas uniquement dans le cache.

Votre objectif est de trouver le nombre minimum possible de cache manquant pour une séquence de demande de mémoire et une taille de cache données.

Vous recevrez la taille du cache, un entier positif et la séquence de demande de mémoire, qui est une liste de jetons. Ces jetons peuvent être n'importe quel type de jetons que vous aimez, tant qu'au moins 256 jetons différents sont possibles (les octets sont bons, les bools ne le sont pas). Par exemple, les entiers, les chaînes, les listes sont très bien. Demandez des éclaircissements si nécessaire.

Cas de test:

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

6

Voir wikipedia pour une politique de remplacement qui y parvient.

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

3

Évitez simplement d'ajouter 2au cache.

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

9

Une façon d' y parvenir est de ne jamais expulsant 0et 2, et expulsant 1le plus tôt possible après sa dernière utilisation.

Notation: Il s'agit du code golf. Le moins d'octets gagne.

JavaScript (ES6), 128 octets

Prend l'entrée comme (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

Essayez-le en ligne!

Commenté

Il s'agit d'une implémentation de l'algorithme 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 octets

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
}

Essayez-le en ligne!

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 octets sans retrait, nouvelles lignes, espaces, commentaires:

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 octets

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

Essayez-le en ligne!

Haskell , 82 octets

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

Essayez-le en ligne!

Explication

Fonctionne par force brute: toutes les stratégies de cache sont essayées et le meilleur résultat est renvoyé.

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 octets

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

Essayez-le en ligne!