cache_is.h File Reference

Importance-sampling estimate of the cache normalizing constant. More...

#include <cmath>
#include <cstddef>
#include <limits>
#include <random>
#include <vector>
#include "line/api/cache/cache_erec.h"
#include "line/api/pfqn/pfqn_asympt_common.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for cache_is.h:

Go to the source code of this file.

Classes
struct	line::cache::CacheIsResult< T >

Namespaces
namespace	line
namespace	line::cache

Functions
template<class T>
CacheIsResult< T >	line::cache::cache_is (const Matrix< T > &gamma_in, const std::vector< int > &m, std::size_t samples, std::uint64_t seed, const std::vector< int > &sigma_in, const std::vector< int > &k)
	Importance-sampling estimate of the cache normalizing constant.
template<class T>
CacheIsResult< T >	line::cache::cache_is (const Matrix< T > &gamma_in, const std::vector< int > &m, std::size_t samples, std::uint64_t seed)
	cache_is without storage cost caps.
template<class T>
CacheIsResult< T >	line::cache::cache_is (const Matrix< T > &gamma, const std::vector< int > &m)
	cache_is with the MATLAB default of 1e5 samples.

Detailed Description

Importance-sampling estimate of the cache normalizing constant.

Templated port of matlab/src/api/cache/cache_is.m. A configuration is drawn by choosing mt = sum(m) of the n items uniformly without replacement and splitting them across the lists in the given order, a proposal of constant density 1/(C(n,mt) multinomial(mt;m)); the estimator is the sample mean of the product of the access factors divided by that density, so it is unbiased. It scales to item counts at which the exact enumeration of cache_erec is out of reach, at the price of a Monte Carlo error.

MATLAB draws the sample with randperm(n,mt) and then shuffles it again before splitting. This port draws it with a partial Fisher-Yates pass, which produces a uniformly random ordered sequence of mt distinct items directly; the second shuffle of the reference is a permutation of an already exchangeable sequence and changes nothing in distribution. The stream is therefore NOT reproducible against MATLAB run for run: only the estimate is comparable, within its own Monte Carlo error.

Arithmetic. static_assert(has_transcendental) – the estimator is formed in the log domain (log-factorials, a log-sum-exp average) because the raw weights overflow, and it is a Monte Carlo average in any case, so exact arithmetic is meaningless here.

Definition in file cache_is.h.