cache_gamma.h File Reference

Access factors of a multi-list cache whose lists form a general access GRAPH. More...

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

Include dependency graph for cache_gamma.h:

Go to the source code of this file.

Classes
struct	line::cache::CacheGammaGraphResult< T >
	Return value of cache_gamma, mirroring the JAR's Ret.cacheGamma. More...

Namespaces
namespace	line
namespace	line::cache

Functions
template<class T>
CacheGammaGraphResult< T >	line::cache::cache_gamma (const std::vector< Matrix< T > > &lambda, const std::vector< std::vector< Matrix< T > > > &R)
	Access factors of a multi-list cache whose lists form a general access GRAPH.

Detailed Description

Access factors of a multi-list cache whose lists form a general access GRAPH.

Templated port of jar/src/main/java/jline/api/cache/Cache_gamma.java. MATLAB has no counterpart: it carries only cache_gamma_lp, the specialization to a tree ("linear path"), which recovers the path by walking the unique parent relation and rejects a node with two parents.

Here the structure is only required to be reachable. The path is the BREADTH-FIRST shortest path in the access graph of item i, so a node with several parents is admissible and the first shortest path found in node order is the one taken. Along that path,

gamma(i,j) = (sum_v lambda(v,i,0)) prod_{edges (a,b)} sum_v lambda(v,i,a) R{v,i}(a,b)

THREE DIVERGENCES FROM cache_gamma_lp, all faithful to the JAR and all of them changing the number, so a caller must not treat the two as substitutes:

• THE DESTINATION IS NODE j, NOT NODE j+1. cache_gamma_lp walks to node l+1 for column l, node 0 being the miss list; this walks to node j. Column 0 therefore has the trivial one-node path and carries NO edge factor at all, where the tree version carries the miss-to-first-list edge.
• the leading factor is the aggregate miss-node request rate sum_v lambda(v,i,0), whereas the tree version starts the product at one;
• each edge factor reads lambda(v,i,a) at the SOURCE node a alone, whereas the tree version sums lambda(v,i,t) over every t <= a. The first of these is hard to read as anything but an off-by-one against the shared meaning of gamma. It is reproduced rather than corrected because this routine exists only in the JAR – MATLAB has no cache_gamma to arbitrate, and no solver in any codebase calls it (only a JUnit import does), so "fixing" it would leave the C++ disagreeing with the sole reference that defines it. Use cache_gamma_lp for the access factors a cache solver consumes.

An unreachable node gives gamma(i,j) = 0, which unlike the tree version is a REACHABLE branch here: the BFS genuinely returns no path.

THE GRAPH IS READ FROM USER 0 ONLY. The JAR takes R.get(0).get(i) for the adjacency and then sums the per-user rates along that one path, so a model whose users route an item differently is analysed on the first user's graph. Reproduced rather than corrected, since changing it would silently move the answer for every such model.

Arithmetic: EXACT-CAPABLE. Sums and products only; the BFS is pure integer bookkeeping and tests adjacency against zero, which is exact in any T.

Definition in file cache_gamma.h.