C++慢循环计算
C++ slow loop computation
我有以下循环用于我正在执行的蒙特卡洛计算:
下面的变量是pre-computed/populated,定义为:
w_ = std::vector<std::vector<double>>(150000, std::vector<double>(800));
C_ = Eigen::MatrixXd(800,800);
Eigen::VectorXd a(800);
Eigen::VectorXd b(800);
while 循环需要我大约 570 秒才能 compute.Just 循环我知道我有 nPaths*m = 150,000 * 800 = 120,000,000 组计算发生(我没有考虑由 boost 库处理的 cdf 计算)。
我是一个低于平均水平的程序员,想知道我是否犯了任何明显的错误,这可能会减慢计算速度。或者是否有任何其他方法来处理可以加快速度的计算。
int N(0);
int nPaths(150000);
int m(800);
double Varsum(0.);
double err;
double delta;
double v1, v2, v3, v4;
Eigen::VectorXd d = Eigen::VectorXd::Zero(m);
Eigen::VectorXd e = Eigen::VectorXd::Zero(m);
Eigen::VectorXd f = Eigen::VectorXd::Zero(m);
Eigen::VectorXd y;
y0 = Eigen::VectorXd::Zero(m);
boost::math::normal G(0, 1.);
d(0) = boost::math::cdf(G, a(0) / C_(0, 0));
e(0) = boost::math::cdf(G, b(0) / C_(0, 0));
f(0) = e(0) - d(0);
while (N < (nPaths-1))
{
y = y0;
for (int i = 1; i < m; i++)
{
v1 = d(i - 1) + w_[N][(i - 1)]*(e(i - 1) - d(i - 1));
y(i - 1) = boost::math::quantile(G, v1);
v2 = (a(i) - C_.row(i).dot(y)) / C_(i, i);
v3 = (b(i) - C_.row(i).dot(y)) / C_(i, i);
d(i) = boost::math::cdf(G, v2);
e(i) = boost::math::cdf(G, v3);
f(i) = (e(i) - d(i))*f(i - 1);
}
N++;
delta = (f(m-1) - Intsum) / N;
Intsum += delta;
Varsum = (N - 2)*Varsum / N + delta*delta;
err = alpha_*std::sqrt(Varsum);
}
如果我对你的代码理解正确,运行 时间实际上是 O(nPaths*m*m)=10^11
,因为点积 C_.row(i).dot(y)
需要 O(m)
运算。
如果不计算两次,您可以将程序速度提高两倍:
double prod=C_.row(i).dot(y)
v2 = (a(i) - prod) / C_(i, i);
v3 = (b(i) - prod) / C_(i, i);
但也许编译器已经为您完成了。
另一件事是 y
由零组成(至少在开头),因此您不必进行完整的点积,而只需在 i
的当前值之前进行。那应该给另一个因素 2 加速。
因此,考虑到操作的绝对数量,您的时机还算不错。代码有一些改进的空间,但如果您有兴趣加快一些数量级的速度,您可能应该考虑更改您的公式。
我有以下循环用于我正在执行的蒙特卡洛计算:
下面的变量是pre-computed/populated,定义为:
w_ = std::vector<std::vector<double>>(150000, std::vector<double>(800));
C_ = Eigen::MatrixXd(800,800);
Eigen::VectorXd a(800);
Eigen::VectorXd b(800);
while 循环需要我大约 570 秒才能 compute.Just 循环我知道我有 nPaths*m = 150,000 * 800 = 120,000,000 组计算发生(我没有考虑由 boost 库处理的 cdf 计算)。
我是一个低于平均水平的程序员,想知道我是否犯了任何明显的错误,这可能会减慢计算速度。或者是否有任何其他方法来处理可以加快速度的计算。
int N(0);
int nPaths(150000);
int m(800);
double Varsum(0.);
double err;
double delta;
double v1, v2, v3, v4;
Eigen::VectorXd d = Eigen::VectorXd::Zero(m);
Eigen::VectorXd e = Eigen::VectorXd::Zero(m);
Eigen::VectorXd f = Eigen::VectorXd::Zero(m);
Eigen::VectorXd y;
y0 = Eigen::VectorXd::Zero(m);
boost::math::normal G(0, 1.);
d(0) = boost::math::cdf(G, a(0) / C_(0, 0));
e(0) = boost::math::cdf(G, b(0) / C_(0, 0));
f(0) = e(0) - d(0);
while (N < (nPaths-1))
{
y = y0;
for (int i = 1; i < m; i++)
{
v1 = d(i - 1) + w_[N][(i - 1)]*(e(i - 1) - d(i - 1));
y(i - 1) = boost::math::quantile(G, v1);
v2 = (a(i) - C_.row(i).dot(y)) / C_(i, i);
v3 = (b(i) - C_.row(i).dot(y)) / C_(i, i);
d(i) = boost::math::cdf(G, v2);
e(i) = boost::math::cdf(G, v3);
f(i) = (e(i) - d(i))*f(i - 1);
}
N++;
delta = (f(m-1) - Intsum) / N;
Intsum += delta;
Varsum = (N - 2)*Varsum / N + delta*delta;
err = alpha_*std::sqrt(Varsum);
}
如果我对你的代码理解正确,运行 时间实际上是 O(nPaths*m*m)=10^11
,因为点积 C_.row(i).dot(y)
需要 O(m)
运算。
如果不计算两次,您可以将程序速度提高两倍:
double prod=C_.row(i).dot(y)
v2 = (a(i) - prod) / C_(i, i);
v3 = (b(i) - prod) / C_(i, i);
但也许编译器已经为您完成了。
另一件事是 y
由零组成(至少在开头),因此您不必进行完整的点积,而只需在 i
的当前值之前进行。那应该给另一个因素 2 加速。
因此,考虑到操作的绝对数量,您的时机还算不错。代码有一些改进的空间,但如果您有兴趣加快一些数量级的速度,您可能应该考虑更改您的公式。