Ce défi est vraiment simple (et un précurseur d'un plus difficile!).

Étant donné un tableau d'accès aux ressources (simplement désigné par des entiers non négatifs) et un paramètre n, renvoie le nombre d'occurrences manquées dans le cache, à supposer que notre cache ait une capacité suffisante net utilise un schéma d'éjection premier entré premier sorti (FIFO) lorsqu'il est plein. .

Exemple:

4, [0, 1, 2, 3, 0, 1, 2, 3, 4, 0, 0, 1, 2, 3]
0 = not in cache (miss), insert, cache is now [0]
1 = not in cache (miss), insert, cache is now [0, 1]
2 = not in cache (miss), insert, cache is now [0, 1, 2]
3 = not in cache (miss), insert, cache is now [0, 1, 2, 3]
0 = in cache (hit), cache unchanged
1 = in cache (hit), cache unchanged
2 = in cache (hit), cache unchanged
3 = in cache (hit), cache unchanged
4 = not in cache (miss), insert and eject oldest, cache is now [1, 2, 3, 4]
0 = not in cache (miss), insert and eject oldest, cache is now [2, 3, 4, 0]
0 = in cache (hit), cache unchanged
1 = not in cache (miss), insert and eject oldest, cache is now [3, 4, 0, 1]
2 = not in cache (miss), insert and eject oldest, cache is now [4, 0, 1, 2]
3 = not in cache (miss), insert and eject oldest, cache is now [0, 1, 2, 3]

Donc, dans cet exemple, il y a eu 9 ratés. Peut-être qu'un exemple de code aide à mieux l'expliquer. En Python:

def num_misses(n, arr):
    misses = 0
    cache = []
    for access in arr:
        if access not in cache:
            misses += 1
            cache.append(access)
            if len(cache) > n:
                cache.pop(0)
    return misses

Quelques autres cas de test (qui contiennent un indice pour le prochain défi - rien de curieux?):

0, [] -> 0
0, [1, 2, 3, 4, 1, 2, 3, 4] -> 8
2, [0, 0, 0, 0, 0, 0, 0] -> 1
3, [3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4] -> 9
4, [3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4] -> 10

Le code le plus court en octets gagne.

JavaScript (ES6), 55 octets

Méthode n ° 1: le cache écrase l'entrée

Prend la syntaxe de currying (cache_size)(list).

n=>a=>a.map(x=>a[a.indexOf(x,k>n&&k-n)<k||k++]=x,k=0)|k

Essayez-le en ligne!

Comment?

Nous écrasons le tableau d'entrée a [] avec le cache, en utilisant un pointeur séparé k initialisé à 0 .

Nous utilisons a.indexOf(x, k > n && k - n) < kpour tester si x est dans le cache.

Le cache ne peut pas croître plus rapidement que le tableau d'origine n'est parcouru. Par conséquent, chaque valeur est garantie, que ce soit dans ou au-delà de la fenêtre du cache (c'est indexOf()-à- dire qu'elle ne renverra jamais -1 ).

Une valeur est dans le cache si elle se trouve à un index compris entre max (0, k - n) et k - 1 (les deux bornes étant incluses), auquel cas on fait un [true] = x . Ceci n'affecte que la propriété de l'objet sous-jacent derrière un [] mais ne modifie pas le tableau a [] . Sinon, on fait un [k ++] = x .

Exemple

Voici les différentes étapes pour l’entrée [1, 1, 2, 3, 3, 2, 1, 4]avec une taille de cache de 2 :

• bordures en gras: pointeur map ()
• crochets: pointeur de cache k
• orange: fenêtre de cache actuelle
• jaune: valeurs de cache expirées

JavaScript (ES6), 57 octets

Méthode n ° 2: le cache est ajouté à la fin de l'entrée

Prend la syntaxe de currying (cache_size)(list).

n=>a=>a.map(x=>n*~a.indexOf(~x,-n)||a.push(~x)&k++,k=0)|k

Essayez-le en ligne!

Comment?

Etant donné que le tableau d'entrée a [] contient des entiers non négatifs, nous pouvons ajouter en toute sécurité le cache à la fin d' un [] en utilisant le complément à un x de chaque valeur x .

Nous utilisons n * ~a.indexOf(~x, -n)pour tester si ~ x est trouvé parmi les n dernières valeurs. Chaque fois que ce test échoue, nous ajoutons ~ x à un [] et incrémentons le nombre de ratés k .

Exemple

Voici les différentes étapes pour le même exemple que ci-dessus, en utilisant cette méthode. Comme les valeurs de cache sont simplement ajoutées à la fin du tableau, il n'y a pas de pointeur de cache explicite.

Haskell , 50 octets

f n=length.foldl(\r x->[x|all(/=x)$take n r]++r)[]

Essayez-le en ligne!

Basé sur la méthode de Lynn pour stocker la totalité de l'historique de cache et prendre sa longueur. La sortie unaire serait un peu plus courte:

Haskell , 47 octets

n?l=1<$foldl(\r x->[x|all(/=x)$take n r]++r)[]l

Essayez-le en ligne!

Python 2 , 58 octets

lambda n,a:len(reduce(lambda c,i:[i][i in c[:n]:]+c,a,[]))

Essayez-le en ligne!

Merci à ovs pour 3 octets et à xnor pour 3 autres.

R , 69 64 62 octets

function(n,A,K={}){for(i in A)K=c(i[!i%in%K[0:n]],K);sum(K|1)}

Essayez-le en ligne!

Merci à JayCe d’avoir suggéré quelques améliorations et à DigEmAll pour un autre couple!

Haskell, 61 58 octets

n!a|let(a:b)#c|elem a c=b#c|1<2=1+b#take n(a:c);_#_=0=a#[]

Essayez-le en ligne!

n!a|      =a#[]     -- take input 'n' and a list 'a'
                    -- and call # with the initial list and an empty cache
 let                -- bind function '#':
  (a:b)#c           -- if there's at least one element 'a' left in the list
     |elem a c=b#c  --  and it's in the cache, go on with the same cache
                    --  and the remainder of the list
     |1<2=          -- else (i.e. cache miss)
          1+        --  add one to the recursive call of
       b#           --  the remainder of the list and 
       take n(a:c)  --  the first n elements of 'a' prepended to the cach
 _#_=0              -- if there's no element in the list, return 0

Edit: -3 octets grâce à @Lynn.

05AB1E , 17 16 octets

)svDyå_i¼y¸ìI£]¾

Essayez-le en ligne!

Explication

)                   # wrap the stack in a list
 sv                 # for each item y in input list
   D                # duplicate current list
    yå_i            # if y is not contained in the current list
        ¼           # increment counter
         y¸ì        # prepend y to the current list
            I£      # keep the first input elements
              ]¾    # end loop and push counter

Kotlin , 82 69 octets

{a,n->a.fold(List(0){0}){c,v->if(v!in c.takeLast(n))c+v else c}.size}

Prend les entrées comme un type IntArray, pas comme le type List<Int>(ce qui ne devrait pas poser de problème). Il utilise l'approche suivante: "créer un historique du cache et compter sa longueur".

Essayez-le en ligne!

Explication

{ a, n ->                         // lambda where a is accesses and n is cache size
    a.fold(List(0){0}) { c, v ->  // fold on empty list
        if(v !in c.takeLast(n))   // if resource is not in last n cache inserts
            c + v                 // insert to cache list
        else
            c                     // return cache as is
    }.size                        // length of cache list is number of inserts
}

Créer une liste vide

Kotlin n'a pas de littéraux de collection, mais certaines fonctions lui permettent de créer de nouvelles collections.

La bonne façon de créer un vide List<Int>est simplement:

List<Int>()

mais il est plus court si nous abusons de la taille et des arguments de l'initialiseur pour le faire:

List(0){0}
List(0)       // List of size 0
       { 0 }  // with generator returning 0

Comme le générateur lambda renvoie 0, Kotlin en déduit le type List<Int>, et sa taille égale à 0 signifie que cette liste est vide.

Perl 6 , 48 octets

{my@c;$_∈@c.tail($^n)||push @c,$_ for @^o;+@c}

Essaye-le

{  # bare block with placeholder params $n,@o

  my @c; # cache


      $_ ∈ @c.tail($^n) # is the current value in the last bit of the cache
    ||
      push @c, $_       # if not add it to the cache

  for                   # do this for all of

    @^o;                # the input array


  +@c                   # numify the cache (the count)
}

Java 8, 96 octets

Un lambda au curry prenant une taille de cache ( int) et une liste d’accès (mutable java.util.List<Integer>) et retournant un int.

s->a->{int w=0,m=0,i;for(int r:a)m+=(i=a.indexOf(r))<w&i<s?0:s<1?1:1+0*a.set(w++%s,r);return m;}

Essayez-le en ligne

Ungolfed

Ceci utilise les premiers (au maximum) semplacements de la liste d'entrée pour le cache.

s ->
    a -> {
        int
            w = 0,
            m = 0,
            i
        ;
        for (int r : a)
            m +=
                (i = a.indexOf(r)) < w & i < s ?
                    0
                    s < 1 ?
                        1
                        : 1 + 0*a.set(w++ % s, r)
            ;
        return m;
    }

Remerciements

• correction de bug grâce à nimi

Pyth ,  16 15 18 14  13 octets

Enregistré 1 octet grâce à isaacg .

luaW-H>QGGHEY

Suite de tests!

Ce défi est très bien adapté à la ustructure de Pyth .

Comment ça marche

luaW-H>QGGHEY     Full program. Q = the cache length, E = the list.
 u         E      Reduce E with G = current value and H = corresponding element
            Y     With starting value Y, which is preinitialised to [] (empty list).
   W              Conditional application. If...
    -H            ... Filtering H on absence of...
      >QG         ... The last Q elements of G... 
                  ... Yields a truthy value (that is, H is not in G[-Q:]), then...
  a      GH       ... Append H to G.
                  ... Otherwise, return G unchanged (do not append H at all).
l                  Get the length of the result.

Wolfram Language (Mathematica) , 60 59 octets

Tr[k={};n=#;k~Take~UpTo@n~FreeQ~#&&k~PrependTo~#&/@#2;1^k]&

Essayez-le en ligne!

Utilisation de la correspondance de modèle, 60 octets

Length[#2//.{p___,a_,q___,a_,r___}/;Tr[1^{q}]<#:>{p,a,q,r}]&

J'aime beaucoup mieux celui-ci, mais c'est 1 octet de plus ...

Essayez-le en ligne!

Japt, 16 octets

;£A¯V øX ªAiXÃAl

L'essayer

Explication

                     :Implicit input of array U and integer V
 £                   :Map over each X in U
; A                  :  Initially the empty array
   ¯V                :  Slice to the Vth element
      øX             :  Contains X?
         ª           :  Logical OR
          AiX        :  Prepend X to A
             Ã       :End map
              Al     :Length of A

K4 , 42 à 40 octets

Solution:

{*1+/1_{r,,(y;x#z,y)r:~z in y:*|y}[x]\y}

Exemples:

q)k)f:{*1+/1_{r,,(y;x#z,y)r:~z in y:*|y}[x]\y}
q)f[0;1 2 3 4 1 2 3 4]
8
q)f[2;0 0 0 0 0 0 0]
1
q)f[3;3 2 1 0 3 2 4 3 2 1 0 4]
9
q)f[4;3 2 1 0 3 2 4 3 2 1 0 4]
10

Explication:

Pour la fonction interne, y est le cache, z est la demande et x est la taille du cache.

{*1+/1_{r,,(y;x#z,y)r:~z in y:*|y}[x]\y} / the solution
{                                      } / lambda taking 2 args
       {                         }       / lambda taking 3 args
                                  [x]\y  / iterate over lambda with each y
                              *|y        / last (reverse, first) y
                            y:           / assign to y
                       z in              / is z in y?
                      ~                  / not 
                    r:                   / assign result to r (true=1,false=0)
           ( ;     )                     / 2-element list
                z,y                      / join request to cache
              x#                         / take x from cache (limit size)
            y                            / (else) return cache unchanged
          ,                              / enlist this result
        r,                               / join with r
     1_                                  / drop the first result
  1+/                                    / sum up (starting from 1)
 *                                       / take the first result

Remarques:

Il y a probablement une meilleure façon de faire tout cela, mais c'est la première façon qui m'est venue à l'esprit.

La fonction peut être exécutée comme ceci pour 36 octets :

q)k)*1+/1_{r,,(y;x#z,y)r:~z in y:*|y}[4]\3 2 1 0 3 2 4 3 2 1 0 4
10

Alternative - utilisation d'une variable globale pour stocker l'état (très peu similaire à K), 42 octets :

{m::0;(){$[z in y;y;[m+:1;x#z,y]]}[x]\y;m}

Brain-Flak , 172 octets

(([{}]<>)<{({}(()))}{}>)<>([]){{}<>((({})<{({}()<<>(({})<({}<>({}<>))>)<>>)}{}>)<<>(({})([{}]<>{<>(){[()](<{}>)}{}<><({}()<<>({}<>)>)>}{})){(<{}{}>)}{}>)<>([])}{}<>({}[]<>)

Essayez-le en ligne!

# Initialize cache with n -1s (represented as 1s)
(([{}]<>)<{({}(()))}{}>)<>

# For each number in input
([]){{}

    # Keep n on third stack
    <>((({})<

        # For last n cache entries, compute difference between entry and new value
        {({}()<<>(({})<({}<>({}<>))>)<>>)}{}

    >)<

        # Get negation of current entry and...
        <>(({})([{}]<>

            {

                # Count cache hits (total will be 1 or 0)
                <>(){[()](<{}>)}{}

                # while moving entries back to right stack
                <><({}()<<>({}<>)>)>

            }{}

        ))

        # If cache hit, don't add to cache
        {(<{}{}>)}{}

    >)

<>([])}{}

# Compute cache history length minus cache size (to account for the initial -1s)
<>({}[]<>)

Gelée , 18 octets

Ṗɼṛ;ɼe®Uḣ⁴¤C$¡€ṛLɼ

Essayez-le en ligne!

Prend la liste comme premier argument et la capacité de cache comme second argument.

Ṗɼṛ;ɼe®Uḣ⁴¤C$¡€ṛLɼ
 ɼ                 Apply to the register:
Ṗ                  Pop. This initializes the register to the empty list.
  ṛ                Right argument. Yields the list of addresses.
              €    For each element in the list
             ¡     If{
     e                 the element is in
          ¤            nilad{
      ®                      the register
       U                     reversed
        ḣ                    first...
         ⁴                   (cache depth) number of elements
                             }
           C           Complement. 1 <-> 0. Easier to type this than "not".
            $          Combines everything up to `e` into a monad
                      }
                    Then{
    ɼ                    Apply to the register and store the result
   ;                     Append the element
                        }
                ṛ   Right argument:
                  ɼ Apply to the register:
                 L  Length

Ruby , 43 à 40 octets

->s,a,*r{a.count{|*x|r!=r=(r|x).pop(s)}}

Essayez-le en ligne!

Merci histocrat pour avoir rasé 3 octets.

C (gcc) , 112 110 108 octets

f(x,y,z)int*y;{int*i=y+z,b[x],m=0;for(wmemset(b,z=-1,x);i-y;y++)wmemchr(b,*y,x)?:++m*x?b[z=++z%x]=*y:0;x=m;}

Essayez-le en ligne!

Un peu moins golfé

f(x,y,z)int*y;{
 int*i=y+z,b[x],m=0;
 for(wmemset(b,z=-1,x);i-y;y++)
  wmemchr(b,*y,x)?:
   ++m*
   x?
    b[z=++z%x]=*y
   :
    0;
 x=m;
}

C (gcc) , 156 octets

s,n,m,i,j;f(x,_)int*_;{int c[x];n=m=0;for(i=0;i<x;++i)c[i]=-1;for(i=s=0;_[i]>=0;++i,s=0){for(j=0;j<x;++j)s|=(c[j]==_[i]);if(!s){c[n++]=_[i];m++;n%=x;}}x=m;}

Essayez-le en ligne!

La description:

s,n,m,i,j;                       // Variable declaration
f(x,_)int*_;{                    // F takes X (the cache size) and _ (-1-terminated data)
    int c[x];                    // declare the cache
    n=m=0;                       // next queue insert pos = 0, misses = 0
    for(i=0;i<x;++i)c[i]=-1;     // initialize the cache to -1 (invalid data)
    for(i=s=0;_[i]>=0;++i,s=0){  // for each datum in _ (resetting s to 0 each time)
        for(j=0;j<x;++j)         // for each datum in cache
            s|=(c[j]==_[i]);     // set s if item found
        if(!s){                  // if no item found
            c[n++]=_[i];         // add it to the cache at position n
            m++;                 // add a mis
            n%=x;                // move to next n position (with n++)
        }} x=m;}                 // 'return' m by assigning to first argument

JavaScript (Node.js) , 44 octets

n=>a=>a.map(y=t=>y[t]+n>p||(y[t]=++p),p=0)|p

Essayez-le en ligne!

Gelée , 17 octets

Ṗœ|Ṛḣ⁴$Ṛʋ\-;⁸e"ċ0

Essayez-le en ligne!

Programme complet.

Argument 1: pile (Python 3 listd' integers)
Argument 2: n(Python 3 integer)

Rouille , 129 octets

|l:&[_],s|if s>0{let(mut c,mut m)=(vec![-1;s],0);for n in l.iter(){if!c.contains(n){c.remove(0);c.push(*n);m+=1;}}m}else{l.len()}

Essayez-le en ligne!

Ungolfed

|l: &[isize], s: usize| {
    if s > 0 {
        let mut c = vec![-1; s];
        let mut m = 0;
        for n in l.iter() {
            if !c.contains(n) {
                c.remove(0);
                c.push(*n);
                m += 1;
            }
        }
        m
    } else {
        l.len()
    }
}

Stax , 15 octets

Ç═╛¢s▲▬╓í±°☻÷hi

Exécuter et déboguer