To wyzwanie jest naprawdę proste (i jest prekursorem trudniejszego!).

Biorąc pod uwagę tablicę dostępu do zasobów (po prostu oznaczoną nieujemnymi liczbami całkowitymi) i parametr n, zwróć liczbę braków pamięci podręcznej, które miałoby przy założeniu, że nasza pamięć podręczna ma pojemność ni korzysta ze schematu wyrzucania FIFO, gdy jest pełna .

Przykład:

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]

Tak więc w tym przykładzie było 9 nieudanych prób. Może przykład kodu pomaga lepiej to wyjaśnić. W Pythonie:

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

Kilka dalszych przypadków testowych (które zawierają wskazówkę do następnego wyzwania - czy zauważyłeś coś ciekawego?):

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

Najkrótszy kod w bajtach wygrywa.

JavaScript (ES6), 55 bajtów

Metoda nr 1: pamięć podręczna zastępuje dane wejściowe

Pobiera dane wejściowe w składni curry (cache_size)(list).

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

Wypróbuj online!

W jaki sposób?

Nadpisujemy tablicę wejściową a [] pamięcią podręczną, używając osobnego wskaźnika k zainicjowanego na 0 .

Używamy a.indexOf(x, k > n && k - n) < kdo testowania, czy x jest w pamięci podręcznej.

Pamięć podręczna nie może rosnąć szybciej niż przeglądana jest oryginalna tablica, więc gwarantuje się, że każda wartość zostanie znaleziona w oknie pamięci podręcznej lub poza nim (tzn. indexOf()Nigdy nie zwróci -1 ).

Wartość znajduje się w pamięci podręcznej, jeśli zostanie znaleziona przy indeksie między max (0, k - n) i k - 1 (obie granice włącznie), w którym to przypadku wykonujemy [prawda] = x . Wpływa to tylko na właściwość obiektu leżącego za [], ale nie zmienia tablicy a [] . W przeciwnym razie robimy [k ++] = x .

Przykład

Poniżej znajdują się różne kroki dla danych wejściowych [1, 1, 2, 3, 3, 2, 1, 4]o wielkości pamięci podręcznej 2 :

• pogrubione ramki: wskaźnik map ()
• nawiasy: wskaźnik pamięci podręcznej k
• pomarańczowy: bieżące okno pamięci podręcznej
• żółty: wygasły wartości pamięci podręcznej

JavaScript (ES6), 57 bajtów

Metoda nr 2: pamięć podręczna jest dodawana na końcu danych wejściowych

Pobiera dane wejściowe w składni curry (cache_size)(list).

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

Wypróbuj online!

W jaki sposób?

Ponieważ tablica wejściowa a [] zawiera nieujemne liczby całkowite, możemy bezpiecznie dołączyć pamięć podręczną na końcu [] , stosując uzupełnienie ~ x każdej wartości x .

Używamy n * ~a.indexOf(~x, -n)do sprawdzenia, czy ~ x znajduje się wśród ostatnich n wartości. Ilekroć ten test się nie powiedzie, dołączamy ~ x do [] i zwiększamy liczbę braków k .

Przykład

Poniżej znajdują się różne kroki dla tego samego przykładu jak powyżej, przy użyciu tej metody. Ponieważ wartości pamięci podręcznej są po prostu dołączane na końcu tablicy, nie ma wyraźnego wskaźnika pamięci podręcznej.

Haskell , 50 bajtów

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

Wypróbuj online!

Oparty na metodzie Lynna przechowywania całej historii pamięci podręcznej i jej długości. Jednoargumentowy wynik byłby nieco krótszy:

Haskell , 47 bajtów

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

Wypróbuj online!

Python 2 , 58 bajtów

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

Wypróbuj online!

Dzięki ovs za 3 bajty i xnor za 3 kolejne.

R , 69 64 62 bajtów

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

Wypróbuj online!

Dzięki JayCe za zasugerowanie ulepszeń, a DigEmAll dla kolejnej pary!

Haskell, 61 58 bajtów

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

Wypróbuj online!

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

Edycja: -3 bajty dzięki @Lynn.

05AB1E , 17 16 bajtów

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

Wypróbuj online!

Wyjaśnienie

)                   # 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 bajtów

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

Staje jako wejście IntArray, nie typoweList<Int> (co nie powinno być problemem.) Ta wykorzystuje podejście „zbudować historię cache i liczyć jej długość”.

Wypróbuj online!

Wyjaśnienie

{ 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
}

Tworzenie pustej listy

Kotlin nie ma literałów kolekcji, ale ma pewne funkcje do tworzenia nowych kolekcji.

Właściwym sposobem utworzenia pustego List<Int>jest po prostu:

List<Int>()

ale jest krótszy, jeśli nadużywamy rozmiaru i argumentów inicjalizatora, aby to zrobić:

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

Ponieważ generator lambda zwraca 0, Kotlin określa typ tej listy jako List<Int>, a rozmiar 0 oznacza, że ​​ta lista jest pusta.

Perl 6 , 48 bajtów

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

Sprawdź to

{  # 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 bajtów

Curried lambda biorąc rozmiar pamięci podręcznej ( int) i listę dostępu (zmienną java.util.List<Integer>) i zwracając 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;}

Wypróbuj online

Bez golfa

Wykorzystuje pierwsze (maksymalnie) smiejsca na liście danych wejściowych dla pamięci podręcznej.

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

Podziękowanie

• naprawiające błędy dzięki Nimi

Pyth ,  16 15 18 14  13 bajtów

Oszczędność 1 bajtu dzięki isaacg .

luaW-H>QGGHEY

Zestaw testowy!

To wyzwanie bardzo dobrze pasuje do Pytha u struktury .

Jak to działa

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 bajtów

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

Wypróbuj online!

Korzystanie z dopasowania wzorca, 60 bajtów

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

Naprawdę podoba mi się ten, ale jest o 1 bajt dłużej ...

Wypróbuj online!

Japt, 16 bajtów

;£A¯V øX ªAiXÃAl

Spróbuj

Wyjaśnienie

                     :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 bajtów

Rozwiązanie:

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

Przykłady:

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

Wyjaśnienie:

Dla funkcji wewnętrznej y jest pamięcią podręczną, z jest żądaniem, a x jest wielkością pamięci podręcznej.

{*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

Uwagi:

Jest prawdopodobnie lepszy sposób, aby to wszystko zrobić, ale to pierwszy sposób, jaki przyszedł mi do głowy.

Funkcję można uruchomić w następujący sposób dla 36 bajtów :

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

Alternatywnie - użycie zmiennej globalnej do przechowywania stanu (niezbyt podobny do K), 42 bajty :

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

Brain-Flak , 172 bajty

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

Wypróbuj online!

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

Galaretka , 18 bajtów

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

Wypróbuj online!

Traktuje listę jako pierwszy argument, a pojemność pamięci podręcznej jako drugi 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

Rubinowy , 43 40 bajtów

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

Wypróbuj online!

Dzięki histocrat za golenie 3 bajtów.

C (gcc) , 112 110 108 bajtów

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

Wypróbuj online!

Nieco mniej golfa

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 bajtów

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

Wypróbuj online!

Opis:

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 bajty

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

Wypróbuj online!

Galaretka , 17 bajtów

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

Wypróbuj online!

Pełny program

Argument 1: stos (Python 3 listz integers)
Argument 2: n(Python 3 integer)

Rdza , 129 bajtów

|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()}

Wypróbuj online!

Bez golfa

|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 bajtów

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

Uruchom i debuguj