(reprise et modification du code donné en TD, code écrit par Arnaud Legrand disponible sur son site
N = 100
a = 0.1
b = (1-a)/(N-1)
K = 20
T = 10000
access = sample(c(1:N), T, prob=c(a,rep(b,N-1)), replace=TRUE)
head(access)
## [1] 60 92 70 58 93 57
cache = sample(c(1:N), K, prob=c(a,rep(b,N-1)), replace=FALSE) # Un cache initial
cacheTFront = cache
posA = c() ;
missA = c() ;
miss = c()
for(obj in access) {
if(obj %in% cache) {
pos = (1:K)[cache==obj];
if(pos != 1 ){
tmp = cache[pos]
cache[pos] = cache [pos-1]
cache[pos-1] = tmp
}
#cache = c(obj,cache[-pos])
miss=c(miss,0);
if(1 %in% cache) {
posA = c(posA,((1:K)[!is.na(cache) & cache==1]));
} else {
posA = c(posA,NA);
}
} else {
cache = c(cache[-K],obj)
miss=c(miss,1);
if(obj==1) {
missA=c(missA,1);
} else {
missA=c(missA,0);
}
}
}
head(cache)
## [1] 1 65 46 64 72 16
head(posA)
## [1] 7 6 6 6 6 6
head(miss)
## [1] 1 1 1 1 1 1
head(miss)
## [1] 1 1 1 1 1 1
plot(posA); lines(posA);
err = sd(miss)/sqrt(length(miss));
mean(miss)-2*err;
## [1] 0.7192008
mean(miss)+2*err
## [1] 0.7369992
on va considerer un élement e situé à la ième position du cache et soit p sa probabilité d’apparition dans access ( donc p = a si e = 1 sinon p = b )
la position de e dans le cache sera k avec une probabilité de p et sera i+1 avec une probabilité 1-p
Soit l’élement courant c qui est en position j
si j > i+1 : la position de e dans le cache sera i-1 avec un proba p et restera i autrement
si j <= i+1 : la position de e dans le cache sera i-1 avec une probabilité p et i+1 si j et en position i+1.
si i = 1 : la position de e restera 1 sauf si c est en deuxième position alors e sera en deuxième position ( avec une probabilité 1-p )
markov=matrix(rep(0,N*N),nrow=N);
markov[1,1] = 1-b;
markov[1,2] = b
for(i in 2:(N-1)) {
if(i<K){
markov[i,i-1] = a ;
markov[i,i+1] = b
markov[i,i]= 1-b-a
}
if(i>K){
markov[i,K] = a ;
markov[i,i]= 1-a ;
}
}
options(digits = 2)
E=head(eigen(t(markov)))
head(E$values)
## [1] 1.00 0.95 0.95 0.94 0.94 0.93
ssp=E$vectors[,1];
ssp = Re(ssp/(sum(ssp)))
options(digits=7);
ssp
## [1] 9.090909e-01 8.264463e-02 7.513148e-03 6.830135e-04 6.209213e-05
## [6] 5.644739e-06 5.131581e-07 4.665074e-08 4.240976e-09 3.855433e-10
## [11] 3.504939e-11 3.186308e-12 2.896644e-13 2.633311e-14 2.393906e-15
## [16] 2.176143e-16 1.976959e-17 1.783718e-18 1.486355e-19 1.351232e-21
## [21] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
## [26] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
## [31] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
## [36] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
## [41] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
## [46] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
## [51] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
## [56] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
## [61] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
## [66] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
## [71] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
## [76] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
## [81] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
## [86] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
## [91] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
## [96] 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00
puis on calucule la probabilité de A d’être dans le cache :
sum(ssp[1:K])
## [1] 1
On arrive a une probabilité très proche de 1.
missTFront=c()
missATFront=c()
posATFront=c();
for(obj in access) {
if(obj %in% cacheTFront) {
pos = (1:K)[cacheTFront==obj];
cacheTFront = c(obj,cacheTFront[-pos])
missTFront=c(missTFront,0);
missATFront=c(missATFront,0);
} else {
cacheTFront = c(obj,cacheTFront[-K])
missTFront=c(missTFront,1);
if(obj == 1) {
missATFront=c(missATFront,1);
} else {
missATFront=c(missATFront,0);
}
}
if(1 %in% cacheTFront) {
posATFront = c(posATFront, (1:K)[cacheTFront==1]);
} else {
posATFront = c(posATFront, NA);
}
}
sum(miss)
## [1] 7281
sum(missA)
## [1] 0
sum(missTFront)
## [1] 7357
sum(missATFront)
## [1] 90
On peut voir que le nombre de miss total est très proche, ce qui est normal car il y’a beacoup d’élément pour une taille de cache assez petite.
Pour les miss d’un élément fréquent ( a ) on voit que move ahead est bien plus efficace car l’élement à plus de chance de rester dans le cache et on peut voir que la position de A est souvent dans les premiers élement du cache pour le move ahead (voir au deussus )
sum(missATFront) - sum(missA)
## [1] 90
plot(posATFront); lines(posATFront)