cache_erec.h File Reference

Exact recursive normalizing constant of a multi-list cache model. More...

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

Include dependency graph for cache_erec.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::cache

Functions
template<class T>
T	line::cache::cache_erec (const Matrix< T > &gamma, const std::vector< int > &m)
	Exact recursive normalizing constant of a multi-list cache model.
template<class T>
T	line::cache::cache_erec (const Matrix< T > &gamma, const std::vector< int > &m, const std::vector< int > &sigma, const std::vector< int > &k)
	The normalizing constant under per-list storage cost caps.

Detailed Description

Exact recursive normalizing constant of a multi-list cache model.

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

The cache holds h lists of capacities m(1..h) filled from n items; the steady-state distribution of the list-based replacement model is proportional to prod over placed items of gamma(item,list), and E(gamma,m) is the sum of that product over every admissible placement, weighted by the list multiplicities. The recursion peels off item k:

E_k(m) = E_{k-1}(m) + sum_j gamma(k,j) m(j) E_{k-1}(m - e_j),

with E(0) = 1, E(m) = 0 whenever sum(m) exceeds the number of remaining items or any capacity is negative, and E_1(e_j) = gamma(1,j).

Every step is a multiplication and an addition, so the exact instantiation returns E as a rational with no rounding at all: for rational access factors that is the true normalizing constant, which is what makes it usable as the oracle for the approximate members of the family (cache_spm, cache_xi_fp).

DIVERGENCE, MATLAB vs JAR: the MATLAB entry point recurses from k = length(gamma), and MATLAB's length() on an (n x h) matrix is max(n,h). That is the item count n only while n >= h; for a cache with more lists than items MATLAB starts the recursion at h and reads gamma rows that do not exist. The JAR uses gamma.getNumRows() and is right. This port follows the JAR (n = number of rows).

Definition in file cache_erec.h.