35
\$\begingroup\$

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.

\$\endgroup\$
  • 15
    \$\begingroup\$ I was looking at the last statement notice anything curious? for a while now... and just noticed, increasing the cache capacity doesn't necessarily decrease the number of misses?! \$\endgroup\$ – JungHwan Min Jun 11 '18 at 19:37
  • \$\begingroup\$ @JungHwanMin Correct! In fact, how much worse it can get is unbounded. \$\endgroup\$ – orlp Jun 11 '18 at 19:45
  • \$\begingroup\$ Can we output the number in unary? \$\endgroup\$ – dylnan Jun 11 '18 at 22:26
  • 9
    \$\begingroup\$ Known as Bélády's anomaly and FIFO is the classic example. The anomaly is unbounded. \$\endgroup\$ – virtualirfan Jun 11 '18 at 23:05
  • \$\begingroup\$ @dylnan No, sorry. \$\endgroup\$ – orlp Jun 12 '18 at 6:56

22 Answers 22

11
\$\begingroup\$

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

method #1


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.

method #2

\$\endgroup\$
10
\$\begingroup\$

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!

\$\endgroup\$
9
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You should be able to save bytes by putting a set after c+=, since for some reason it converts to a list for you. \$\endgroup\$ – xnor Jun 11 '18 at 20:17
  • \$\begingroup\$ (ah, yes, c+={i}-set(c[-n:]) works, for positive n. But nimi pointed out that c[-n:] is wrong for n == 0, so I can’t use +=, and hence that trick – too bad.) \$\endgroup\$ – Lynn Jun 11 '18 at 20:58
  • 1
    \$\begingroup\$ @Lynn Ah, I see. reduce still saves bytes: lambda n,a:len(reduce(lambda c,i:[i][i in c[:n]:]+c,a,[])). \$\endgroup\$ – xnor Jun 11 '18 at 22:51
7
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ I guess the + in front of Fis for f(0,{}) to return 0? \$\endgroup\$ – JayCe Jun 11 '18 at 19:28
  • \$\begingroup\$ @JayCe yep, a classic golf in tandem with F as a pre-initialized return value. \$\endgroup\$ – Giuseppe Jun 11 '18 at 19:30
  • 1
    \$\begingroup\$ a small improvemement. Also if unary output is accepted you can probably save some bytes. \$\endgroup\$ – JayCe Jun 12 '18 at 0:29
  • \$\begingroup\$ @JayCe found some more bytes! \$\endgroup\$ – Giuseppe Jun 12 '18 at 0:36
  • 1
    \$\begingroup\$ @JDL yeah, a shame about the q but still a nice idea! Using NA is less good than using {} since I actually care about the length here (and I'm not actually popping elements from the cache). \$\endgroup\$ – Giuseppe Jun 13 '18 at 10:28
5
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ @nimi: Thanks! Fixed while saving a byte :) \$\endgroup\$ – Emigna Jun 12 '18 at 6:05
5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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)
}
\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ aW-H>QGGH beats ?}H<GQG+HG by 1 \$\endgroup\$ – isaacg Jun 12 '18 at 4:04
  • \$\begingroup\$ @isaacg Thanks! I initially had +G*]H!}H>QG, but when I golfed it I really haven't thought of W... Nice! \$\endgroup\$ – Mr. Xcoder Jun 12 '18 at 6:12
  • \$\begingroup\$ What exactly does u do? \$\endgroup\$ – dylnan Jun 12 '18 at 15:06
  • \$\begingroup\$ @dylnan u is a reduce with intial value operator. Just like Jelly's ƒ \$\endgroup\$ – Mr. Xcoder Jun 12 '18 at 15:29
3
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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}
\$\endgroup\$
1
\$\begingroup\$

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)
<>({}[]<>)
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Nice answer! You can save a couple bytes by initializing r as part of the argument list: ->s,a,*r which also provides the bonus feature that the caller can prime the cache by passing extra arguments :) \$\endgroup\$ – histocrat Jun 13 '18 at 20:17
  • \$\begingroup\$ Oh, and similarly to cast x into an array: .count{|*x| \$\endgroup\$ – histocrat Jun 13 '18 at 20:29
1
\$\begingroup\$

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;
}
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Suggest wmemset(c,-1,x) instead of n=m=0;for(i=0;i<x;++i)c[i]=-1, n=m=i=s=0 instead of i=s=0, for(j=x;j--;) instead of for(j=0;j<x;++j), and s||(c[n++]=_[i],m++,n%=x); instead of if(!s){c[n++]=_[i];m++;n%=x;} \$\endgroup\$ – ceilingcat Jun 12 '18 at 0:34
0
\$\begingroup\$

JavaScript (Node.js), 44 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Jelly, 17 bytes

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

Try it online!

Full program.

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

\$\endgroup\$
0
\$\begingroup\$

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()
    }
}
\$\endgroup\$
0
\$\begingroup\$

Stax, 15 bytes

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

Run and debug it

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.