Number of FIFO cache misses

Question

This challenge is really simple (and a precursor to a more difficult one!).

Given an array of resource accesses (simply denoted by nonnegative integers) and a parameter n, return the number of cache misses it would have assuming our cache has capacity n and uses a first-in-first-out (FIFO) ejection scheme when it is full.

Example:

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]

So in this example there were 9 misses. Maybe a code example helps explain it better. 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

Some further testcases (which contains a hint towards the next challenge - notice anything curious?):

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

Shortest code in bytes wins.

Answer 1

JavaScript (ES6), 55 bytes

Method #1: the cache overwrites the input

Takes input in currying syntax (cache_size)(list).

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

Try it online!

How?

We overwrite the input array a[ ] with the cache, using a separate pointer k initialized to 0.

We use a.indexOf(x, k > n && k - n) < k to test whether x is in the cache.

The cache can't grow faster than the original array is walked through, so each value is guaranteed to be found, either within or beyond the cache window (i.e. indexOf() will never return -1).

A value is in the cache if it is found at an index between max(0, k - n) and k - 1 (both bounds included), in which case we do a[true] = x. This only affects a property of the underlying object behind a[ ] but does not alter the array a[ ]. Otherwise, we do a[k++] = x.

Example

Below are the different steps for the input [1, 1, 2, 3, 3, 2, 1, 4] with a cache size of 2:

• bold borders: map() pointer
• brackets: cache pointer k
• orange: current cache window
• yellow: expired cache values

---

JavaScript (ES6), 57 bytes

Method #2: the cache is appended at the end of the input

Takes input in currying syntax (cache_size)(list).

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

Try it online!

How?

Because the input array a[ ] is guaranteed to contain non-negative integers, we can safely append the cache at the end of a[ ] by using the one-complement ~x of each value x.

We use n * ~a.indexOf(~x, -n) to test whether ~x is found among the last n values. Whenever this test fails, we append ~x to a[ ] and increment the number of misses k.

Example

Below are the different steps for the same example as above, using this method. Because cache values are simply appended at the end of the array, there is no explicit cache pointer.

Answer 2

Haskell, 50 bytes

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

Try it online!

Based on Lynn's method of storing the whole cache history and taking its length. Unary output would be a bit shorter:

Haskell, 47 bytes

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

Try it online!

Answer 3

Python 2, 58 bytes

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

Try it online!

Thanks to ovs for 3 bytes, and xnor for 3 more.

Answer 4

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

Try it online!

Thanks to JayCe for suggesting some improvements, and DigEmAll for another couple!

Answer 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#[]

Try it 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 thanks to @Lynn.

Answer 6

05AB1E, 17 16 bytes

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

Try it online!

Explanation

)                   # 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

Answer 7

Kotlin, 82 69 bytes

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

Takes input as an IntArray, not the typical List<Int> (which shouldn't be a problem.) This uses the approach of "build a cache history and count its length".

Try it online!

Explanation

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

Creating an empty list

Kotlin does not have collection literals, but it does have some functions to create new collections.

The proper way to create an empty List<Int> is simply:

List<Int>()

but it is shorter if we abuse the size and initializer args to do this:

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

Because the generator lambda returns 0, Kotlin infers the type of this list as List<Int>, and the size of 0 means this list is empty.

Answer 8

Perl 6, 48 bytes

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

Test it

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

Answer 9

Java 8, 96 bytes

A curried lambda taking a cache size (int) and access list (mutable java.util.List<Integer>) and returning an 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;}

Try It Online

Ungolfed

This uses the first (up to) s slots in the input list for the 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;
    }

Acknowledgments

• bugfix thanks to nimi

Answer 10

Pyth,  16 15 18 14  13 bytes

Saved 1 byte thanks to isaacg.

luaW-H>QGGHEY

Test suite!

This challenge is very well suited to Pyth's u structure.

How it works

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.

Answer 11

Wolfram Language (Mathematica), 60 59 bytes

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

Try it online!

Using pattern-matching, 60 bytes

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

I really like this one better, but it's 1 byte longer...

Try it online!

Answer 12

Japt, 16 bytes

;£A¯V øX ªAiXÃAl

Try it

---

Explanation

                     :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

Answer 13

K4, 42 40 bytes

Solution:

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

Examples:

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

Explanation:

For the inner function, y is the cache, z is the request and x is the cache size.

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

Notes:

There is probably a nicer way to do all of this, but this is the first way that came to mind.

The function can be ran like this for 36 bytes:

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 - using a global variable to store state (not very K-like), 42 bytes:

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

Answer 14

Brain-Flak, 172 bytes

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

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

Answer 15

Jelly, 18 bytes

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

Try it online!

Takes the list as the first argument and cache capacity as 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

Answer 16

Ruby, 43 40 bytes

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

Try it online!

Thanks histocrat for shaving 3 bytes.

Answer 17

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

Try it online!

Slightly less golfed

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

Answer 18

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

Try it online!

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

Answer 19

JavaScript (Node.js), 44 bytes

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

Try it online!

Answer 20

Jelly, 17 bytes

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

Try it online!

Full program.

Argument 1: stack (Python 3 list of integers)
Argument 2: n (Python 3 integer)

Answer 21

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

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

Answer 22

Stax, 15 bytes

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

Run and debug it