Jumlah cache FIFO hilang

35

Tantangan ini sangat sederhana (dan prekursor untuk tantangan yang lebih sulit!).

Diberikan array dari akses sumber daya (hanya dilambangkan dengan bilangan bulat tidak negatif) dan sebuah parameter n, kembalikan jumlah cache yang hilang dengan asumsi bahwa cache kita memiliki kapasitasn dan menggunakan skema ejeksi pertama-masuk-keluar-pertama (FIFO) saat penuh .

Contoh:

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]

Jadi dalam contoh ini ada 9 kesalahan. Mungkin contoh kode membantu menjelaskannya dengan lebih baik. Dengan 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

Beberapa testcases lebih lanjut (yang berisi petunjuk tentang tantangan berikutnya - perhatikan ada yang penasaran?):

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

Kode terpendek dalam byte menang.

orlp
sumber
15
Saya sedang melihat pernyataan terakhir notice anything curious?untuk sementara waktu sekarang ... dan baru saja memperhatikan, meningkatkan kapasitas cache tidak selalu mengurangi jumlah kesalahan ?!
JungHwan Min
@JungHwanMin Benar! Faktanya, seberapa parah hal itu dapat terjadi adalah tidak terbatas.
orlp
Bisakah kita menampilkan nomor di unary?
dylnan
9
Dikenal sebagai anomali Bélády dan FIFO adalah contoh klasiknya. Anomali tidak terbatas .
virtualirfan
@dylnan Tidak, maaf.
orlp

Jawaban:

11

JavaScript (ES6), 55 byte

Metode # 1: cache menimpa input

Mengambil input dalam sintaks currying (cache_size)(list).

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

Cobalah online!

Bagaimana?

Kami menimpa array input a [] dengan cache, menggunakan pointer terpisah k diinisialisasi ke 0 .

Kami gunakan a.indexOf(x, k > n && k - n) < kuntuk menguji apakah x ada dalam cache.

Cache tidak dapat tumbuh lebih cepat daripada array asli berjalan, sehingga setiap nilai dijamin akan ditemukan, baik di dalam atau di luar jendela cache (yaitu indexOf()tidak akan pernah mengembalikan -1 ).

Nilai ada dalam cache jika ditemukan pada indeks antara maks (0, k - n) dan k - 1 (keduanya termasuk batas), dalam hal ini kita melakukan [true] = x . Ini hanya memengaruhi properti objek yang mendasari di belakang [] tetapi tidak mengubah array a [] . Kalau tidak, kita melakukan [k ++] = x .

Contoh

Di bawah ini adalah langkah-langkah berbeda untuk input [1, 1, 2, 3, 3, 2, 1, 4]dengan ukuran cache 2 :

  • batas tebal: pointer peta ()
  • kurung: penunjuk cache k
  • oranye: jendela cache saat ini
  • kuning: nilai cache kedaluwarsa

metode # 1


JavaScript (ES6), 57 byte

Metode # 2: cache ditambahkan di akhir input

Mengambil input dalam sintaks currying (cache_size)(list).

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

Cobalah online!

Bagaimana?

Karena larik input a [] dijamin mengandung bilangan bulat non-negatif, kita dapat menambahkan cache dengan aman di akhir [] dengan menggunakan satu-pelengkap ~ x dari setiap nilai x .

Kami menggunakan n * ~a.indexOf(~x, -n)untuk menguji apakah ~ x ditemukan di antara nilai n terakhir . Setiap kali tes ini gagal, kami menambahkan ~ x ke [] dan menambah jumlah kesalahan k .

Contoh

Di bawah ini adalah langkah-langkah berbeda untuk contoh yang sama seperti di atas, menggunakan metode ini. Karena nilai-nilai cache hanya ditambahkan di akhir array, tidak ada pointer cache eksplisit.

metode # 2

Arnauld
sumber
9

Python 2 , 58 byte

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

Cobalah online!

Berkat ovs untuk 3 byte, dan xnor untuk 3 lebih.

Lynn
sumber
Anda harus dapat menyimpan byte dengan meletakkan satu set setelah c+=, karena untuk beberapa alasan itu dikonversi ke daftar untuk Anda.
xnor
(ah, ya, c+={i}-set(c[-n:])bekerja, untuk positif n. Tapi nimi menunjukkan bahwa c[-n:]itu salah untuk n == 0, jadi saya tidak dapat menggunakan +=, dan karenanya trik itu - sangat buruk.)
Lynn
1
@ Lynn Ah, begitu. reducemasih menyimpan byte: lambda n,a:len(reduce(lambda c,i:[i][i in c[:n]:]+c,a,[])).
xnor
7

R , 69 64 62 byte

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

Cobalah online!

Terima kasih kepada JayCe karena telah menyarankan beberapa perbaikan, dan DigEmAll untuk pasangan lain!

Giuseppe
sumber
Saya kira +di depan Fadalah untuk f(0,{})mengembalikan 0?
JayCe
@JayCe ya, golf klasik bersama dengan Fsebagai nilai pengembalian yang diinisialisasi.
Giuseppe
1
perbaikan kecil . Juga jika output unary diterima Anda mungkin dapat menyimpan beberapa byte.
JayCe
@JayCe menemukan beberapa byte lagi!
Giuseppe
1
@ JDL ya, memalukan tentang qtapi masih ide bagus! Menggunakan NAkurang baik daripada menggunakan {}karena saya benar-benar peduli tentang panjang di sini (dan saya tidak benar-benar muncul elemen dari cache).
Giuseppe
5

Haskell, 61 58 byte

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

Cobalah 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 byte terima kasih kepada @Lynn.

nimi
sumber
5

05AB1E , 17 16 byte

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

Cobalah online!

Penjelasan

)                   # 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
sumber
@nimi: Terima kasih! Diperbaiki sambil menyimpan byte :)
Emigna
5

Kotlin , 82 69 byte

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

Mengambil input sebagai IntArray, bukan tipikal List<Int>(yang seharusnya tidak menjadi masalah.) Ini menggunakan pendekatan "bangun riwayat cache dan hitung panjangnya".

Cobalah online!

Penjelasan

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

Membuat daftar kosong

Kotlin tidak memiliki koleksi literal, tetapi memang memiliki beberapa fungsi untuk membuat koleksi baru.

Cara yang tepat untuk membuat yang kosong List<Int>hanyalah:

List<Int>()

tetapi lebih pendek jika kita menyalahgunakan ukuran dan penginisialisasi argumen untuk melakukan ini:

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

Karena generator lambda mengembalikan 0, Kotlin menyimpulkan tipe daftar ini sebagai List<Int>, dan ukuran 0 berarti daftar ini kosong.

siput_
sumber
4

Perl 6 , 48 byte

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

Menguji

{  # 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
sumber
4

Java 8, 96 byte

Lambda kari mengambil ukuran cache ( int) dan daftar akses (bisa berubah java.util.List<Integer>) dan mengembalikan sebuah 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;}

Cobalah secara Online

Tidak disatukan

Ini menggunakan sslot pertama (hingga) dalam daftar input untuk 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;
    }

Ucapan Terima Kasih

  • perbaikan bug berkat nimi
Jakob
sumber
4

Pyth ,  16 15 18 14  13 byte

Disimpan 1 byte berkat isaacg .

luaW-H>QGGHEY

Suite uji!

Tantangan ini sangat cocok untuk ustruktur Pyth .

Bagaimana itu bekerja

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.
Tuan Xcoder
sumber
aW-H>QGGHbeats ?}H<GQG+HGby 1
isaacg
@isaacg Terima kasih! Awalnya saya miliki +G*]H!}H>QG, tetapi ketika saya bermain golf saya benar-benar tidak memikirkan W... Bagus!
Tn. Xcoder
Apa yang sebenarnya udilakukan?
dylnan
@dylnan uadalah pengurangan dengan operator nilai awal. Sama seperti Jellyƒ
Tn. Xcoder
2

Japt, 16 byte

;£A¯V øX ªAiXÃAl

Cobalah


Penjelasan

                     :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
Shaggy
sumber
1

K4 , 42 40 byte

Larutan:

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

Contoh:

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

Penjelasan:

Untuk fungsi dalam, y adalah cache, z adalah permintaan dan x adalah ukuran cache.

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

Catatan:

Mungkin ada cara yang lebih baik untuk melakukan semua ini, tetapi ini adalah cara pertama yang terlintas dalam pikiran.

Fungsi ini dapat dijalankan seperti ini selama 36 byte :

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

Alternatif - menggunakan variabel global untuk menyimpan status (tidak terlalu mirip K), 42 byte :

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

Brain-Flak , 172 byte

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

Cobalah 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
sumber
1

Jelly , 18 byte

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

Cobalah online!

Mengambil daftar sebagai argumen pertama dan kapasitas cache sebagai argumen kedua.

Ṗɼṛ;ɼ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
sumber
1

Ruby , 43 40 byte

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

Cobalah online!

Terima kasih histokrat untuk mencukur 3 byte.

GB
sumber
1
Jawaban bagus! Anda dapat menyimpan beberapa byte dengan menginisialisasi r sebagai bagian dari daftar argumen: ->s,a,*ryang juga menyediakan fitur bonus bahwa pemanggil dapat
mengunggah
Oh, dan demikian pula untuk dilemparkan xke dalam array:.count{|*x|
histokrat
1

C (gcc) , 112 110 108 byte

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

Cobalah online!

Sedikit kurang golf

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;
}
plafon
sumber
0

C (gcc) , 156 byte

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

Cobalah online!

Deskripsi:

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
sumber
Sarankan wmemset(c,-1,x)bukan n=m=0;for(i=0;i<x;++i)c[i]=-1, n=m=i=s=0bukan i=s=0, for(j=x;j--;)bukan for(j=0;j<x;++j), dan s||(c[n++]=_[i],m++,n%=x);bukannyaif(!s){c[n++]=_[i];m++;n%=x;}
ceilingcat
0

Jelly , 17 byte

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

Cobalah online!

Program lengkap.

Argumen 1: tumpukan (Python 3 listdari integers)
Argumen 2: n(Python 3 integer)

Erik the Outgolfer
sumber
0

Karat , 129 byte

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

Cobalah online!

Tidak disatukan

|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.
sumber