c++ - 用于蒙特卡洛模拟的 vector 优化累积

Question

我想优化以下代码:

在蒙特卡洛模拟过程中，我累积了一些量 f(x)(f(x) 的计算成本很高)并将它们保存在数组 bins 中 在每个采样步骤之后。

编辑:f(x) 不是 x 的确定性函数(我的意思是它生成伪随机数并使用它们来修改结果)并且还取决于先前计算的值 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 个 bin 被命中的次数存储在 bins[k] 中，然后在结束并为每个 k 计算 bins[k] * f(k)。