Anzahl der FIFO-Cache-Fehlschläge

35

Diese Herausforderung ist wirklich einfach (und ein Vorläufer einer schwierigeren!).

Bei einem Array von Ressourcenzugriffen (einfach durch nichtnegative Ganzzahlen angegeben) und einem Parameter ngeben Sie die Anzahl der Cachefehler zurück, sofern der Cache über Kapazität verfügt nund ein FIFO-Auswurfschema (First-In-First-Out) verwendet, wenn er voll ist .

Beispiel:

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]

In diesem Beispiel gab es also 9 Fehler. Vielleicht hilft ein Codebeispiel, es besser zu erklären. In 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

Einige weitere Testfälle (die einen Hinweis auf die nächste Herausforderung enthalten - etwas Merkwürdiges feststellen?):

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

Kürzester Code in Bytes gewinnt.

orlp
quelle
15
Ich habe mir die letzte Aussage schon notice anything curious?eine Weile angesehen ... und gerade bemerkt, dass das Erhöhen der Cache-Kapazität nicht unbedingt die Anzahl der Fehler verringert ?!
JungHwan Min
@JungHwanMin Richtig! In der Tat ist es unbegrenzt, wie viel schlimmer es werden kann.
Orlp
Können wir die Zahl unär ausgeben?
Dylnan
9
Bekannt als Béládys Anomalie und FIFO ist dies das klassische Beispiel. Die Anomalie ist unbegrenzt .
virtualirfan
@ Dylnan Nein, tut mir leid.
Orlp

Antworten:

11

JavaScript (ES6), 55 Byte

Methode 1: Der Cache überschreibt die Eingabe

Übernimmt Eingaben in der Currying-Syntax (cache_size)(list).

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

Probieren Sie es online!

Wie?

Wir überschreiben das Eingabearray a [] mit dem Cache unter Verwendung eines separaten Zeigers k, der auf 0 initialisiert ist .

Wir a.indexOf(x, k > n && k - n) < ktesten, ob sich x im Cache befindet.

Der Cache kann nicht schneller wachsen, als das ursprüngliche Array durchlaufen wurde. Daher wird garantiert jeder Wert innerhalb oder außerhalb des Cache-Fensters gefunden (dh er indexOf()gibt niemals -1 zurück ).

Ein Wert befindet sich im Cache, wenn er an einem Index zwischen max (0, k - n) und k - 1 (beide Grenzen eingeschlossen) gefunden wird. In diesem Fall ist a [true] = x . Dies betrifft nur eine Eigenschaft des zugrunde liegenden Objekts hinter einem [] , ändert jedoch nicht das Array a [] . Ansonsten machen wir a [k ++] = x .

Beispiel

Nachfolgend sind die verschiedenen Schritte für die Eingabe [1, 1, 2, 3, 3, 2, 1, 4]mit einer Cache-Größe von 2 aufgeführt :

  • fette Ränder: map () Zeiger
  • Klammern: Cache-Zeiger k
  • orange: aktuelles Cache-Fenster
  • gelb: abgelaufene Cache-Werte

Methode 1


JavaScript (ES6), 57 Byte

Methode 2: Der Cache wird am Ende der Eingabe angehängt

Übernimmt Eingaben in der Currying-Syntax (cache_size)(list).

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

Probieren Sie es online!

Wie?

Da das Eingabearray a [] garantiert nicht negative Ganzzahlen enthält, können wir den Cache sicher am Ende von a [] anhängen, indem wir das Ein-Komplement ~ x jedes Werts x verwenden .

Wir n * ~a.indexOf(~x, -n)testen, ob ~ x unter den letzten n Werten gefunden wird. Wenn dieser Test fehlschlägt, hängen wir ~ x an a [] an und erhöhen die Anzahl der Fehler k .

Beispiel

Nachfolgend sind die verschiedenen Schritte für dasselbe Beispiel wie oben unter Verwendung dieser Methode aufgeführt. Da Cache-Werte einfach am Ende des Arrays angehängt werden, gibt es keinen expliziten Cache-Zeiger.

Methode # 2

Arnauld
quelle
9

Python 2 , 58 Bytes

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

Probieren Sie es online!

Danke an ovs für 3 Bytes und xnor für 3 weitere.

Lynn
quelle
Sie sollten in der Lage sein, Bytes zu sparen, indem Sie einen Satz nach dem anderen setzen c+=, da dieser aus irgendeinem Grund in eine Liste für Sie konvertiert wird.
Donnerstag,
(ach ja, c+={i}-set(c[-n:])funktioniert, zum Positiven n. Aber nimi wies darauf hin, dass c[-n:]das falsch ist n == 0, also kann ich nicht +=und daher diesen Trick - schade.)
Lynn
1
@Lynn Ah, ich verstehe. reducenoch speichert Bytes: lambda n,a:len(reduce(lambda c,i:[i][i in c[:n]:]+c,a,[])).
Xnor
7

R , 69 64 62 Bytes

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

Probieren Sie es online!

Vielen Dank an JayCe für die Verbesserungsvorschläge und DigEmAll für ein weiteres Paar!

Giuseppe
quelle
Ich vermute, die +vor Fist für f(0,{})0 zurückzugeben?
JayCe
@JayCe yep, ein klassischer Golf zusammen mit Feinem vorinitialisierten Rückgabewert.
Giuseppe,
1
eine kleine Verbesserung . Auch wenn eine unäre Ausgabe akzeptiert wird, können Sie wahrscheinlich einige Bytes sparen.
JayCe
@JayCe hat noch mehr Bytes gefunden!
Giuseppe
1
@JDL ja, schade um die qaber trotzdem eine nette idee! Die Verwendung NAist weniger gut als die Verwendung, {}da mir die Länge hier wirklich wichtig ist (und ich keine Elemente aus dem Cache lösche).
Giuseppe
5

Haskell, 61-58 Bytes

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

Probieren Sie es 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

Edit: -3 Bytes dank @Lynn.

nimi
quelle
5

05AB1E , 17 16 Bytes

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

Probieren Sie es online!

Erläuterung

)                   # 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
Emigna
quelle
@nimi: Danke!
Behoben
5

Kotlin , 82-69 Bytes

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

Nimmt Eingaben als ein IntArray, nicht das typische List<Int>(was kein Problem sein sollte.) Dies verwendet den Ansatz "Erstellen eines Cache-Verlaufs und Zählen seiner Länge".

Probieren Sie es online!

Erläuterung

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

Eine leere Liste erstellen

Kotlin verfügt nicht über Sammlungsliterale, hat jedoch einige Funktionen zum Erstellen neuer Sammlungen.

Der richtige Weg, um eine leere zu erstellen, List<Int>ist einfach:

List<Int>()

Es ist jedoch kürzer, wenn wir die Argumente size und initializer dazu missbrauchen:

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

Da der Generator lambda 0 zurück, folgert Kotlin den Typ dieser Liste als List<Int>und die Größe von 0 bedeutet diese Liste leer ist .

Schnecke_
quelle
4

Perl 6 , 48 Bytes

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

Probier es aus

{  # 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)
}
Brad Gilbert b2gills
quelle
4

Java 8, 96 Bytes

Ein Curry-Lambda, das eine Cache-Größe ( int) und eine Zugriffsliste (veränderlich java.util.List<Integer>) annimmt und ein zurückgibt 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;}

Probieren Sie es online

Ungolfed

Dies verwendet die ersten (bis zu) sSlots in der Eingabeliste für den 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;
    }

Danksagung

  • Bugfix dank Nimi
Jakob
quelle
4

Pyth ,  16 15 18 14  13 Bytes

Dank isaacg 1 Byte gespeichert .

luaW-H>QGGHEY

Testsuite!

Diese Herausforderung passt sehr gut zu Pyths uStruktur.

Wie es funktioniert

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.
Mr. Xcoder
quelle
aW-H>QGGHschlägt ?}H<GQG+HGum 1
isaacg
@isaacg Danke! Anfangs hatte ich +G*]H!}H>QG, aber als ich Golf gespielt habe, habe ich wirklich nicht daran gedacht W... Schön!
Mr. Xcoder
Was genau macht udas?
dylnan
@dylnan uist ein Reduktionsoperator mit Anfangswert. Genau wie bei Jelly'sƒ
Mr. Xcoder am
2

Japt, 16 Bytes

;£A¯V øX ªAiXÃAl

Versuch es


Erläuterung

                     :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
Zottelig
quelle
1

K4 , 42 40 Bytes

Lösung:

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

Beispiele:

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

Erläuterung:

Für die innere Funktion ist y der Cache, z ist die Anforderung und x ist die Cache-Größe.

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

Anmerkungen:

Es gibt wahrscheinlich einen schöneren Weg, dies alles zu tun, aber dies ist der erste Weg, der mir in den Sinn gekommen ist.

Die Funktion kann für 36 Bytes so ausgeführt werden :

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 - Verwendung einer globalen Variablen zum Speichern des Zustands (nicht sehr K-ähnlich), 42 Bytes :

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

Brain-Flak , 172 Bytes

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

Probieren Sie es 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)
<>({}[]<>)
Nitrodon
quelle
1

Jelly , 18 Bytes

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

Probieren Sie es online!

Nimmt die Liste als erstes Argument und die Cache-Kapazität als zweites 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
dylnan
quelle
1

Ruby , 43 40 Bytes

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

Probieren Sie es online!

Vielen Dank, Histocrat, für das Rasieren von 3 Bytes.

GB
quelle
1
Gute Antwort! Sie können ein paar Bytes sparen, indem Sie r als Teil der Argumentliste initialisieren ->s,a,*r:
Dies
Oh, und ähnlich xin eine Reihe zu werfen :.count{|*x|
Histokrat
1

C (GCC) , 112 110 108 Bytes

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

Probieren Sie es online!

Etwas weniger golfen

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;
}
Ceilingcat
quelle
0

C (gcc) , 156 Bytes

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

Probieren Sie es online!

Beschreibung:

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
LambdaBeta
quelle
Schlagen Sie wmemset(c,-1,x)anstelle von n=m=0;for(i=0;i<x;++i)c[i]=-1, n=m=i=s=0anstelle von i=s=0, for(j=x;j--;)anstelle von for(j=0;j<x;++j)und s||(c[n++]=_[i],m++,n%=x);anstelle vonif(!s){c[n++]=_[i];m++;n%=x;}
Ceilingcat
0

Gelee , 17 Bytes

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

Probieren Sie es online!

Volles Programm.

Argument 1: Stapel (Python 3 listvon integers)
Argument 2: n(Python 3 von egers int)

Erik der Outgolfer
quelle
0

Rust , 129 Bytes

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

Probieren Sie es online!

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()
    }
}
Herman L
quelle