14
\$\begingroup\$

You will be given a sequence of memory requests and a cache size. You must return the least possible number of cache misses under any cache replacement strategy.

An optimal strategy is Belady's algorithm, which you can use if you want to.


A caching system works as follows: The cache starts out empty. Memory requests come in. If the request asks for a piece of data in the cache, all is well. If not, you incur a cache miss. At this point you may insert the data that was request into the cache for future use. If the cache was full and you want to insert new data, you must evict data that was previously in the cache. You may never insert data that was not just in the cache.

Your goal is to find the minimum possible number of cache misses for a given memory request sequence and cache size.


You will be given the cache size, a positive integer, and the memory request sequence, which is a list of tokens. These tokens can be whatever kind of tokens you like, as long as at least 256 different tokens are possible (bytes are fine, bools are not). For instance, ints, strings, lists are all fine. Ask for clarification if needed.


Test cases:

3
[5, 0, 1, 2, 0, 3, 1, 2, 5, 2]

6

See wikipedia for a replacement policy that achieves this.

2
[0, 1, 2, 0, 1, 0, 1]

3

Simply avoid adding 2 to the cache.

3
[0, 1, 2, 1, 4, 3, 1, 0, 2, 3, 4, 5, 0, 2, 3, 4]

9

One way to achieve this is by never evicting 0 and 2, and evicting 1 as soon as possible after its last use.


Scoring: This is code golf. Fewest bytes wins.

\$\endgroup\$
  • \$\begingroup\$ Can we assume that the list contains at least 2 tokens? \$\endgroup\$ – Arnauld Aug 4 '18 at 8:35
  • \$\begingroup\$ @Arnauld I'm going to say no, though if there's only 1 solution, the answer is of course always 1. \$\endgroup\$ – isaacg Aug 4 '18 at 10:30
4
\$\begingroup\$

JavaScript (ES6), 128 bytes

Takes input as (size)(list).

s=>a=>a.map((x,i)=>c.includes(x)?0:c[e++,[x,...c].map(m=(x,j)=>(k=[...a,x].indexOf(x,i+1))<m||(p=j,m=k)),i<s?i:p-1]=x,e=c=[])&&e

Try it online!

Commented

This is an implementation of Belady's algorithm.

s => a =>                      // s = cache size; a[] = token list
  a.map((x, i) =>              // for each token x at position i in a[]:
    c.includes(x) ?            //   if x is currently stored in the cache:
      0                        //     do nothing
    :                          //   else:
      c[                       //     update the cache:
        e++,                   //       increment the number of errors (cache misses)
        [x, ...c]              //       we want to find which value among x and all current
                               //       cache values will be needed for the longest time in
                               //       the future (or not needed anymore at all)
        .map(m =               //       initialize m to a non-numeric value
                 (x, j) =>     //       for each x at position j in this array:
          ( k = [...a, x]      //         k = position of x in the array made of all values
            .indexOf(x, i + 1) //         of a[] followed by x, starting at i + 1
          ) < m                //         if it's greater than or equal to m, or m is
          || (p = j, m = k)    //         still non-numeric: set p to j and m to k
        ),                     //       end of inner map()
        i < s ?                //       if i is less than the cache size:
          i                    //         just fill the cache by using the next cache slot
        :                      //       else:
          p - 1                //         use the slot that was found above
                               //         special case: if p = 0, x was the best candidate
                               //         and we're going to store it at c[-1], which is
                               //         simply ignored (it will not trigger c.includes(x))
      ] = x,                   //     store x at this position
      e = c = []               //     start with e = [] (coerced to 0) and c = []
  ) && e                       // end of outer map; return e
\$\endgroup\$
4
\$\begingroup\$

Perl 5, 193 bytes

sub g{
  my($i,$m,$s,@a,%c)=(-1,0,@_);
  for(@a){
    $i++;
    next if $c{$_}++ || ++$m && keys%c <= $s;
    my($x,$d);
    for $k (sort keys %c){  #find which to delete, the one furtherst away
      my $n=0;
      ++$n && /^$k$/ && last for @a[$i+1..$#a];
      ($x,$d)=($n,$k) if $n>$x
    }
    delete $c{$d}
  }
  $m
}

Try it online!

print g(3,  5, 0, 1, 2, 0, 3, 1, 2, 5, 2),"\n";                     # 6
print g(2,  0, 1, 2, 0, 1, 0, 1),"\n";                              # 3
print g(3,  0, 1, 2, 1, 4, 3, 1, 0, 2, 3, 4, 5, 0, 2, 3, 4),"\n";   # 9

193 bytes without indentation, newlines, spaces, comments:

sub g{my($i,$m,$s,@a,%c)=(-1,0,@_);for(@a){$i++;next if$c{$_}++||++$m&&keys%c<=$s;my($x,$d);for$k(sort keys%c){my$n=0;++$n&&/^$k$/&&last for@a[$i+1..$#a];($x,$d)=($n,$k)if$n>$x}delete$c{$d}}$m}
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 20 bytes

vI∍Dyå≠i¼yª¹N.$sÃÙ]¾

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Haskell, 82 bytes

f n|let(d:t)#c=1-sum[1|elem d c]+minimum[t#take n e|e<-scanr(:)(d:c)c];_#_=0=(#[])

Try it online!

Explanation

Works by brute force: all cache strategies are tried and the best result is returned.

f n            Define a function f on argument n (cache size) and a list (implicit).
 |let(d:t)#c=  Define binary helper function #.
               Arguments are list with head d (current data) and tail t (remaining data), and list c (cache).
 1-            It returns 1 minus
 sum[1|        1 if
 elem d c]+    d is in the cache, plus
 minimum[      minimum of
 t#            recursive calls to # with list t
 take n e|     and cache being the first n values of e, where
 e<-           e is drawn from
 scanr(:)  c]  the prefixes of c
 (d:c)         with d and c tacked to the end.
 ;_#_=0        If the first list is empty, return 0.
 =(#[])        f then calls # with the list argument and empty cache.
\$\endgroup\$
0
\$\begingroup\$

Perl 6, 146 bytes

->\a,\b {$_=set();$!=0;for b.kv ->\i,\v {$_{v}&&next;++$!;v∈b[i^..*]||next;$_∖=.keys.max({(grep $_,:k,b[i^..*])[0]//Inf})if $_>=a;$_∪=v};$!}

Try it online!

\$\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.