cache_prob_erec.h File Reference

Exact per-item hit and miss probabilities of a multi-list cache. More...

#include <cstddef>
#include <vector>
#include "line/api/cache/cache_erec.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for cache_prob_erec.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::cache

Functions
template<class T>
Matrix< T >	line::cache::cache_prob_erec (const Matrix< T > &gamma, const std::vector< int > &m, const std::vector< int > &sigma, const std::vector< int > &k)
	Per-item hit and miss probabilities under per-list storage cost caps, pi_ij = m_j gamma(i,j) E_i(m - e_j, k - sigma_i e_j) / E(m,k).
template<class T>
Matrix< T >	line::cache::cache_prob_erec (const Matrix< T > &gamma, const std::vector< int > &m)
	Exact per-item hit and miss probabilities of a multi-list cache.

Detailed Description

Exact per-item hit and miss probabilities of a multi-list cache.

Templated port of matlab/src/api/cache/cache_prob_erec.m, cross-checked against jar/src/main/java/jline/api/cache/Cache_prob_erec.java.

The probability that item i sits in list j is the ratio of normalizing constants

prob(i,1+j) = m(j) gamma(i,j) E(gamma without item i, m - e_j) / E(gamma,m)

and prob(i,1) = 1 - sum_j prob(i,1+j) is the miss probability. Both constants come from cache_erec, so every operation is a field operation and the exact instantiation returns the probabilities as rationals; in that arithmetic the row sums are exactly one, which is the conservation law the test suite asserts with == rather than a tolerance.

The MATLAB reference wraps the miss probability in abs(), which only matters when the hit probabilities sum above one – impossible in exact arithmetic and a rounding artefact in double. The abs() is kept for bit-compatibility with MATLAB and the JAR.

Definition in file cache_prob_erec.h.