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.
notice anything curious?
untuk sementara waktu sekarang ... dan baru saja memperhatikan, meningkatkan kapasitas cache tidak selalu mengurangi jumlah kesalahan ?!Jawaban:
JavaScript (ES6), 55 byte
Metode # 1: cache menimpa input
Mengambil input dalam sintaks currying
(cache_size)(list)
.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) < k
untuk 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 :JavaScript (ES6), 57 byte
Metode # 2: cache ditambahkan di akhir input
Mengambil input dalam sintaks currying
(cache_size)(list)
.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.
sumber
Haskell , 50 byte
Cobalah online!
Berdasarkan metode Lynn untuk menyimpan seluruh sejarah cache dan mengambilnya. Output unary akan sedikit lebih pendek:
Haskell , 47 byte
Cobalah online!
sumber
Python 2 , 58 byte
Cobalah online!
Berkat ovs untuk 3 byte, dan xnor untuk 3 lebih.
sumber
c+=
, karena untuk beberapa alasan itu dikonversi ke daftar untuk Anda.c+={i}-set(c[-n:])
bekerja, untuk positifn
. Tapi nimi menunjukkan bahwac[-n:]
itu salah untukn == 0
, jadi saya tidak dapat menggunakan+=
, dan karenanya trik itu - sangat buruk.)reduce
masih menyimpan byte:lambda n,a:len(reduce(lambda c,i:[i][i in c[:n]:]+c,a,[]))
.R ,
696462 byteCobalah online!
Terima kasih kepada JayCe karena telah menyarankan beberapa perbaikan, dan DigEmAll untuk pasangan lain!
sumber
+
di depanF
adalah untukf(0,{})
mengembalikan 0?F
sebagai nilai pengembalian yang diinisialisasi.q
tapi masih ide bagus! MenggunakanNA
kurang baik daripada menggunakan{}
karena saya benar-benar peduli tentang panjang di sini (dan saya tidak benar-benar muncul elemen dari cache).Haskell,
6158 byteCobalah online!
Edit: -3 byte terima kasih kepada @Lynn.
sumber
05AB1E ,
1716 byteCobalah online!
Penjelasan
sumber
Kotlin ,
8269 byteMengambil input sebagai
IntArray
, bukan tipikalList<Int>
(yang seharusnya tidak menjadi masalah.) Ini menggunakan pendekatan "bangun riwayat cache dan hitung panjangnya".Cobalah online!
Penjelasan
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:tetapi lebih pendek jika kita menyalahgunakan ukuran dan penginisialisasi argumen untuk melakukan ini:
Karena generator lambda mengembalikan 0, Kotlin menyimpulkan tipe daftar ini sebagai
List<Int>
, dan ukuran 0 berarti daftar ini kosong.sumber
Perl 6 , 48 byte
Menguji
sumber
Java 8, 96 byte
Lambda kari mengambil ukuran cache (
int
) dan daftar akses (bisa berubahjava.util.List<Integer>
) dan mengembalikan sebuahint
.Cobalah secara Online
Tidak disatukan
Ini menggunakan
s
slot pertama (hingga) dalam daftar input untuk cache.Ucapan Terima Kasih
sumber
Pyth ,
16 15 18 1413 byteDisimpan 1 byte berkat isaacg .
Suite uji!
Tantangan ini sangat cocok untuk
u
struktur Pyth .Bagaimana itu bekerja
sumber
aW-H>QGGH
beats?}H<GQG+HG
by 1+G*]H!}H>QG
, tetapi ketika saya bermain golf saya benar-benar tidak memikirkanW
... Bagus!u
dilakukan?u
adalah pengurangan dengan operator nilai awal. Sama seperti Jellyƒ
Bahasa Wolfram (Mathematica) ,
6059 byteCobalah online!
Menggunakan pencocokan pola, 60 byte
Saya sangat suka yang ini, tapi 1 byte lebih lama ...
Cobalah online!
sumber
Japt, 16 byte
Cobalah
Penjelasan
sumber
K4 ,
4240 byteLarutan:
Contoh:
Penjelasan:
Untuk fungsi dalam, y adalah cache, z adalah permintaan dan x adalah ukuran cache.
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 :
Alternatif - menggunakan variabel global untuk menyimpan status (tidak terlalu mirip K), 42 byte :
sumber
Brain-Flak , 172 byte
Cobalah online!
sumber
Jelly , 18 byte
Cobalah online!
Mengambil daftar sebagai argumen pertama dan kapasitas cache sebagai argumen kedua.
sumber
Ruby ,
4340 byteCobalah online!
Terima kasih histokrat untuk mencukur 3 byte.
sumber
->s,a,*r
yang juga menyediakan fitur bonus bahwa pemanggil dapatx
ke dalam array:.count{|*x|
C (gcc) ,
112 110108 byteCobalah online!
Sedikit kurang golf
sumber
C (gcc) , 156 byte
Cobalah online!
Deskripsi:
sumber
wmemset(c,-1,x)
bukann=m=0;for(i=0;i<x;++i)c[i]=-1
,n=m=i=s=0
bukani=s=0
,for(j=x;j--;)
bukanfor(j=0;j<x;++j)
, dans||(c[n++]=_[i],m++,n%=x);
bukannyaif(!s){c[n++]=_[i];m++;n%=x;}
JavaScript (Node.js) , 44 byte
Cobalah online!
sumber
Jelly , 17 byte
Cobalah online!
Program lengkap.
Argumen 1: tumpukan (Python 3
list
dariint
egers)Argumen 2:
n
(Python 3int
eger)sumber
Karat , 129 byte
Cobalah online!
Tidak disatukan
sumber
Stax , 15 byte
Jalankan dan debug itu
sumber