优化载体用于蒙特卡洛模拟的积累

Question

我想优化以下代码：

在蒙特卡洛模拟过程中，我累积了一些量f(x)（f(x)的计算价格昂贵），并在每个采样步骤后将其保存在数组bins中。

编辑：f（x）不是x的确定性函数（我的意思是它生成伪随机数并使用它们来修改结果），也取决于previoulsy计算的值f（y）

for(int n=0;n<N;n++)
{
    // compute some values f(x) at points "p"
    for(auto k: p) bins[k] += f(k);
}

p.size()比bins的大小要小得多，但最终将设置大多数元素。

模拟后，我通过在bins上进行加权总和来累积我的最终值（g是另一个数组中的查找）：

for(int l=0;l<M;l++)
    for(int k=0;k<bins.size();k++)
        finalResult[l] += g(k,l)*bins[k];

我当然可以在每个采样步骤后计算我的更新的finalResult，但是由于 M的循环，这确实会慢慢降低程序。

我已经尝试了非常基本的boost::accumulate，但这并不能提高性能（如果我使用此设计，我将最终由于稳定性而必须使用它）。

所有数组均为类型Eigen::MatrixXd，因为我需要它们进行Blas操作。

p.size() < 10^2
N ~ 10^7
M ~ 10^4
bins.size() ~ 10^5

您对哪些技术在此处进行优化有任何建议？

Answer 1

尝试仅对N值中的每个值（即备忘录）来计算f(x)。因此，例如，如果N很大（就像在这种情况下一样），请尝试将循环更改为以下内容：

static std::unordered_map<unsigned int, double> memoizedFunction;
for(int n=0;n<N;n++)
{
    // compute some values f(x) at points "p"
    for(auto k: p) 
    {
        auto it = memoizedFunction.find( k );
        if (it == memoizedFunction.end())
        {
             it = memoizedFunction.emplace( f(k) ).first;
        }
        bins[k] += *it;
    }
}

另外，您可以存储k TH bin的次数已在bins[k]中为hit，然后最后一次通过并计算每个k的bins[k] * f(k)。

Answer 2

只是一个想法，但是如果您可以验证f（x）是线性的 转换然后您可以创建矩阵 a ，以便

[f(x)] = A[x] where [x] is the coordinates of x with respect to some basis B.

可以使f（x）更容易，更快地计算，尤其是在x 存在于较小的矢量空间中。

但是，如果在坐标和答案之间转换很昂贵 总体上可能会杀死任何好处（只要牢记这一点）。

这里有一些链接可以帮助解释矩阵表示 线性转换。

https://math.colorado.edu/~nita/matrixrepresentations.pdf https://math.dartmouth.edu/archive/m24w07/public_html/lecture12.pdf https://en.wikipedia.org/wiki/transformation_matrix