c++ - C++ 中的组合练习看到速度与 VBA 相比有所下降

Question

只是为了娱乐，我想我会用蒙特卡洛实现来模拟一个组合问题。我在 VBA 中做了一个实现，然后作为练习，我想我会尝试用 C++ 编写它(我是一个完全的新手)来检查速度差异等。除了我不知道高级编码技术/技巧之外，我曾天真地认为只要将模型忠实地转移到 C++ 并尽可能地使用镜像函数/循环/变量类型等等，除了微小的调整之外，C++ 的强大功能会立即提高我的速度，因为我正在运行大量的模拟人生嵌入式排序等。好吧，情况恰恰相反，所以 C++ 实现一定存在严重错误，根据参数，它最多只有一半的速度。他们都收敛到相同的答案，所以在数学上很高兴他们工作。

问题:

假设您有 N 天随机分配 k 个考试，例如每天 2 个考试时段 (AM/PM)。说 2 天是完整考试日的概率是多少？我想我有一个封闭的形式，我现在相信，所以无论如何都想用 MC 进行测试。

算法启发式:

很简单，假设我们有 18 天、6 场考试、每天 2 个时段，我们想知道我们有 2 个完整天的概率。

(i) 模拟6个制服U_i(ii) 使用根据已分配的名额调整的制服在剩余的名额中随机分配考试名额，从而为考试分配名额。例如，如果 Exam 4 在 34 槽空间中分配了槽 4，但已经占用了 3 和 5，那么在 36 槽空间中，Exam_4 将分配到槽 6(这将是 rebase 后的第一个空闲槽)。已经通过一些嵌入式排序实现了这一点(在 VB Bubblesort/quicksort 中差异可以忽略不计，到目前为止在 C++ 中仅使用 bubblesort)。(iii) 只需将时间槽转换为天数，然后计算达到目标的模拟人生数。

呸——那只是背景。这样做的精神并不是真正优化算法，只是为了帮助我理解我做错了什么，导致在 C++ 中“镜像”时速度变慢!!

代码!

// monte carlo

#include "stdafx.h"
#include"AllocateSlots.h"
#include<vector>
#include<string>
#include<iostream>
#include<cmath>
#include<ctime>

using namespace std;

int main()
{
    int i, j, k, m;

    int days, exams, slotsperday, filledslotsperday, targetfulldays, filleddays;

    long sims, count, simctr;

    cout << "Days?: ";cin >> days;
    cout << "Exams?: ";cin >> exams;
    cout << "Slots Per Day?: ";cin >> slotsperday;
    cout << "Filled Slots?: ";cin >> filledslotsperday;
    cout << "Target Full Days?: ";cin >> targetfulldays;
    cout << "No. of sims?: ";cin >> sims;

    system("PAUSE");

    //timer
    clock_t start;
    start = clock();

    double randomvariate;

    //define intervals for remaining slots
    vector <double> interval(exams);

    int totalslots = (days * slotsperday);

    for (k = 1; k <= exams; k++)
    {
        interval[k-1] = 1 / (static_cast <double> (totalslots - k + 1));
    }

    vector <int> slots(exams);          //allocated slots 
    vector <int> previousslots(exams);  //previously allocated slots
    vector <int> slotdays(exams);       //days on which slots fall

    srand((int) time(0)); //generates seed on current system time
    count = 0;
    for (simctr = 1; simctr <= sims; simctr++)
    {
        vector<int> daycounts(days);        //initialised at 0

        for (i = 1; i <= exams;i++)
        {
            //rand() generates integers in [0.0,32767]
            randomvariate = (static_cast <double> (rand()+1))/ (static_cast <double> (RAND_MAX+1));
            j = 1;
            while (j <= totalslots - i + 1)
            {
                if (randomvariate < j*interval[i - 1]) break;
                j++;
            }

            slots[i - 1] = j;
        }

        for (i = 2; i <= exams;i++)
        {
            previousslots.resize(i - 1);
            for (m = 1; m <= i - 1; m++)
            {
                previousslots[m - 1] = slots[m - 1];
            }

            BubbleSort(previousslots);

            for (k = 1; k <= i - 1;k++)
            {
                if (slots[i - 1] >= previousslots[k - 1]) 
                { 
                    slots[i - 1]++ ;
                }
            }
        }

        //convert slots into days
        for (i = 1; i <= exams;i++)
        {
            slotdays[i - 1] = SlottoDays(slots[i - 1], slotsperday);
        }

        //calculate the filled days
        filleddays = 0;
        for (j = 1; j <= days; j++)
        {
            for (k = 1; k <= exams; k++)
            {
                if (slotdays[k - 1] == j)
                {
                    daycounts[j - 1]++;
                }
            }

            if (daycounts[j - 1] == filledslotsperday)
            {
                filleddays++;
            }

        }

        //check if target is hit
        if (filleddays == targetfulldays)
        {
            count++;
        }

    }

    cout << count << endl;
    cout << "Time: " << (clock() - start) / (double)(CLOCKS_PER_SEC) << " s" << endl;
    //cout << (static_cast<double>(count)) / (static_cast<double>(sims));
    system("PAUSE");

    return 0;
}

以及 2 个辅助函数:

#include "stdafx.h"
#include"AllocateSlots.h"
#include<iostream>
#include<cmath>
#include<vector>

using namespace std;

//returns day for a given slot 
int SlottoDays(int &examslot, int &slotsperday)
{
    return((examslot % slotsperday == 0) ? examslot/ slotsperday: examslot/ slotsperday + 1);
}

//BubbleSort Algorithm
vector <int> BubbleSort(vector <int> &values)
{
    int i;
    int j;
    int tmpSort;
    int N = values.size();

    for (i = 0; i < N;i++)
    {
        for (j = i + 1; j < N; j++)
        {
            if (values[i] > values[j])
            {
                tmpSort = values[j];
                values[j] = values[i];
                values[i] = tmpSort;
            }
        }
    }
    return values;
}

就是这样 - 就像我说的算法是 C++ 和 VBA 通用的，很高兴发布 VBA，但首先只是想知道上面是否有明显的东西。几乎是第一次这样做，使用 vector 等，独立的，自学的，所以肯定搞砸了一些事情，尽管已经设法让它运行了一些奇迹!非常感谢一些智慧的话 - 尝试通过这样的练习自学 C++，但我真正想要的是速度(当然还有数学准确性!)用于更大的项目。

仅供引用，在我的 18 天、6 次考试、每天 2 个空位、2 天的填充时间中，它应该收敛到大约 3.77%，这是在 VBA 中的 38 秒和 145 秒的 1mm 模拟机上实现的x64 windows7 上的 duocore 2.7G i7 4GB RAM 笔记本电脑。

Answer 1

从评论中的讨论来看，您可能正在以 Debug 模式运行您的程序。这会关闭一些优化，甚至会生成一些额外的代码。

要在 Release 模式下运行，请在标准工具栏中查找 Solution Configurations 下拉菜单，然后使用下拉菜单将 Debug 更改为 Release。

然后重建您的解决方案并重新运行您的测试。

要在 Visual Studio 中进一步探索程序性能，您需要使用性能探查器工具。 Microsoft 文档站点上有一个关于使用 Performance Profiler 的教程(包括视频):Profile application performance in Visual Studio .还有 Quickstart: First look at profiling tools还有一大堆:都在Profiling in Visual Studio下部分。