c++ - 比较 vector 中的元素时花费的时间呈指数增长

Question

我有一段代码看起来像这样:

void MonteCarloRainbowOptionFunction::ValueInstrument()
{
    std::vector<MJArray> correlatedNormVariates = GetArraysOfCorrelatedGauassiansByBoxMuller(numberOfPaths, covMatrix); 
    std::vector<StatisticAllPaths> thesePathGatherers;
    for (unsigned long i = 0; i < S_vect.size(); i++)
    {
        StandardExcerciseOption thisOption(ThePayOffVect[i], TTM);
        StatisticAllPaths onePathGatherer;
        thesePathGatherers.push_back(onePathGatherer);
        OneStepMonteCarloValuation(thisOption, S_vect[i], impvol_vect[i], r, d_vect[i], numberOfPaths, correlatedNormVariates[i], thesePathGatherers[i]);
    }
    f = 0;
    for (unsigned long i = 0; i < numberOfPaths; i++)
    {       
        int count = 0;
        if (i % 2500 == 0)
        {
            count += 1;
            std::cout << i << " paths done" << "\n";
        }
        std::vector<double> outcomes;
        for (unsigned long j = 0; j < S_vect.size(); j++)
        {
            outcomes.push_back(thesePathGatherers[j].GetResultsSoFar()[0][i]);
        }
        switch (optionType)
        {
        case RainbowOptionType::best_of:
            f += *max_element(outcomes.begin(), outcomes.end());
            break;
        case RainbowOptionType::worst_of:
            f += *min_element(outcomes.begin(), outcomes.end());
            break;          
        default:
            throw std::runtime_error("Unsupported or unknown option type found in " + GetuniqueIdentifier()[0]);
            break;
        }   
    }
    f *= ((double)nominal/numberOfPaths);
    return;
}

在第一部分中(在第一个“时间检查”之前)，我模拟了大量的值，这些值通过函数OneStepMonteCarloValuation存储在 vector 中(确实在 vector 的 vector 的第一个 vector 中)。像这样(花费的时间最少):

void OneStepMonteCarloValuation(const StandardExcerciseOption& TheOption, double Spot, double Vol, double r, double d, unsigned long NumberOfPaths, MJArray normVariates, StatisticsMC& gatherer)
{
    if (normVariates.size() != NumberOfPaths)
        throw("mismatched number of paths and normal variates");
    //Pre-calculate as much as possible
    double Expiry = TheOption.GetExpiry();
    double variance = Vol * Vol * Expiry;
    double rootVariance = sqrt(variance);
    double itoCorrection = -0.5 * variance;
    double movedSpot = Spot * exp((r-d) * Expiry + itoCorrection);
    double thisSpot;
    double discounting = exp(-r * Expiry);
    for (unsigned long i = 0; i < NumberOfPaths; i++)
    {
        thisSpot = movedSpot * exp(rootVariance * normVariates[i]);
        double thisPayoff = TheOption.OptionPayOff(thisSpot);
        gatherer.DumpOneResult(discounting * thisPayoff);
    }
    return;
}

它在这里调用的收集器是此类:

StatisticAllPaths::StatisticAllPaths(const unsigned long minimumNumberOfPaths) : PathsDone(0)
{
    ResultList.reserve(minimumNumberOfPaths);
}

void StatisticAllPaths::DumpOneResult(double result)
{
    ResultList.push_back(result);
    PathsDone++;
}

std::vector<std::vector<double>> StatisticAllPaths::GetResultsSoFar() const
{
    vector<double> innerVector(ResultList);
    vector<vector<double> > Results(1, innerVector);
    Results[0] = ResultList;
    return Results;
}

在第二部分中，我遍历所有 vector 并将i元素保存在临时“输出” vector 中，比较输出中的值并保存结果，然后执行相同的操作。遍历thesePathGatherers中的所有值。第一部分运行很快，但是这花费了更长的时间，甚至对于足够高的numberOfPaths也无法全部完成。我添加了这一部分:

    if (i % 2500 == 0)
    {
        count += 1;
        std::cout << i << " paths done" << "\n";
    }

要进行调试并发现，例如，如果路径总数很大，则执行前10 ^ 4条路径会花费更长的时间，即每个单独的路径花费的时间越长，您执行的路径就越多。 GetResultsSoFar()的实现/用法有问题吗？那是我唯一能想象的。任何帮助表示赞赏

让我知道是否还有更多需要分享的内容。

Answer 1

这里有一些答案集中在GetResultsSoFar中发生的过度复制上，但是没有一个解决您如何调用此函数的毫无意义的问题:

std::vector<double> outcomes;
for (unsigned long j = 0; j < S_vect.size(); j++)
{
    outcomes.push_back(thesePathGatherers[j].GetResultsSoFar()[0][i]);
}

在这里，您正在为每个“路径收集器”收集一个结果值，但是要这样做是在提取一个值之前多次复制每个结果列表。我认为改善此问题的第一步是避免复制ResultList，因为这是不需要的。

相反，如何返回对结果的const引用。我还将重命名此函数，以避免将其与您现有的定义混淆。但是随便你怎么称呼它:

const std::vector<double>& StatisticAllPaths::GetResultList() const
{
    return ResultList;
}

当然，循环然后将第i个值作为thesePathGatherers[j].GetResultList()[i]进行访问。这里的关键区别是根本没有复制发生。

在outcomes上还有一个小的优化。由于您确切知道要推送多少个项目，因此应该预先保留该内存。

即

std::vector<double> outcomes;
outcomes.reserve(S_vect.size());
for (unsigned long j = 0; j < S_vect.size(); j++)
{
    outcomes.push_back(thesePathGatherers[j].GetResultList()[i]);
}

如果希望它更整洁，请考虑定义仅返回单个结果的double GetResult(size_t) const，然后调用thesePathGatherers[j].GetResult(i)。