cache_gamma_lp.h File Reference

Access factors of a tree-structured multi-list cache. 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_gamma_lp.h:

Go to the source code of this file.

Classes
struct	line::cache::CacheGammaResult< T >
	Return value of cache_gamma_lp, mirroring [gamma,u,n,h]. More...

Namespaces
namespace	line
namespace	line::cache

Functions
template<class T>
CacheGammaResult< T >	line::cache::cache_gamma_lp (const std::vector< Matrix< T > > &lambda, const std::vector< std::vector< Matrix< T > > > &R)
	Access factors of a tree-structured multi-list cache.

Detailed Description

Access factors of a tree-structured multi-list cache.

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

The lists of the cache form a tree rooted at node 0 ("not cached"), list l being node l+1. The access factor gamma(i,l) of item i at list l is the product, along the unique path from the root to node l+1, of the aggregate request flow crossing each edge:

gamma(i,l) = prod_{edges (a,b) of the path} sum_v sum_{t<=a} lambda(v,i,t) R{v,i}(a,b)

The path is recovered by walking up from node l+1 through the parent relation, the parent of a node being the unique earlier node with a nonzero routing probability into it; more than one parent means the structure is not a tree and is an error, as in both reference implementations.

Only sums and products, so this instantiates at exact arithmetic and the access factors of a rational model are exact rationals.

REFERENCE DEFECT (both codebases): the isempty(Pij) branch that sets gamma(i,l) = 0 is unreachable, because Pij is seeded with the node itself and so is never empty. A list disconnected from the root therefore does not yield a zero access factor; it yields the empty product 1. Reproduced here so that the three codebases agree, and flagged rather than fixed.

Definition in file cache_gamma_lp.h.