cpp蒙特卡洛计算23个人中至少有两个生日是同一天的概率?(优化代码效率版本)
作者:yunjinqi   类别:    日期:2024-10-17 12:27:07    阅读:110 次   消耗积分:0 分    

初始版本耗费时间:157206 ms  优化版本1耗费时间:6070.46 ms  优化版本2耗费时间:1502.49 ms  从c++编程水平上来看,chatgpt的能力还是要超过我的,优化版本2是chatgpt改进出来的。


代码优化1:


这个是晚上做梦的时候想到的,没必要去用月和日,直接用数值就好了。但是没考虑到的情况是闰年的时候2月有29天。运行耗费时间大大降低

#include <iostream>
#include <chrono>
#include <iostream>
#include <random>
#include <set>

// The Birthday Problem, main()
// Summary: This application simulates the birthday problem a large number of times to reveal the probability of a birthday match in a groupd of a given number of people.
int main(){
    const int total = 1000000;
    int n, matches;
    std::cout << "Enter the number of people in the group: " << std::flush;
    std::cin >> n;
    // 获取起始时间
    auto start = std::chrono::high_resolution_clock::now();
    // Initialize random number generator
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> month_dist(1, 365);
    if(n > 366)
        matches = total;
    else{
        // Write your code here
        matches = 0;
        for (int j = 0; j < total; ++j){
            std::set<int> month_day_set;
            for (int i=0; i<n; ++i){
                int num = month_dist(gen);
                month_day_set.insert(num);
            }
            int num = n - month_day_set.size()?1:0;
            matches += num;
            // std::cout << "j = " << j << " matches = " << matches << std::endl;
        }
    }
    // 获取结束时间
    auto end = std::chrono::high_resolution_clock::now();

    // 计算持续时间,单位为毫秒
    std::chrono::duration<double, std::milli> duration_ms = end - start;

    // 输出运行时间
    std::cout << "The code took " << duration_ms.count() << " ms to run." << std::endl;
    std::cout << "The probability of a birthday match is " << (double)matches/total << "\n\n" << std::flush;

    return 0;
}


代码优化2:

#include <iostream>
#include <random>
#include <vector>

// Function to simulate the birthday problem
bool has_duplicate_birthday(int n, std::mt19937 &gen, std::uniform_int_distribution<> &dist) {
    // Boolean array to mark birthdays (index from 1 to 365)
    std::vector<bool> birthdays(365, false);

    // Generate random birthdays and check for duplicates
    for (int i = 0; i < n; ++i) {
        int birthday = dist(gen);
        if (birthdays[birthday]) { // If this birthday has already occurred
            return true; // Duplicate found
        }
        birthdays[birthday] = true; // Mark this birthday as taken
    }
    return false; // No duplicate found
}

int main() {
    const int total_simulations = 1000000;
    int n;
    int matches = 0;

    // Ask for the number of people in the group
    std::cout << "Enter the number of people in the group: " << std::flush;
    std::cin >> n;
    // 获取起始时间
    auto start = std::chrono::high_resolution_clock::now();

    // If more than 366 people, we are guaranteed a match
    if (n > 366) {
        matches = total_simulations;
    } else {
        // Initialize random number generator and distribution (1-364 inclusive)
        std::random_device rd;
        std::mt19937 gen(rd());
        std::uniform_int_distribution<> dist(0, 364); // Days from 0 to 364

        // Run the simulation `total_simulations` times
        for (int i = 0; i < total_simulations; ++i) {
            if (has_duplicate_birthday(n, gen, dist)) {
                ++matches;
            }
        }
    }
    // 获取结束时间
    auto end = std::chrono::high_resolution_clock::now();

    // 计算持续时间,单位为毫秒
    std::chrono::duration<double, std::milli> duration_ms = end - start;

    // 输出运行时间
    std::cout << "The code took " << duration_ms.count() << " ms to run." << std::endl;
    // Output the empirical probability
    std::cout << "The probability of a birthday match is " << static_cast<double>(matches) / total_simulations << "\n\n" << std::flush;

    return 0;
}


版权所有,转载本站文章请注明出处:云子量化, http://www.woniunote.com/article/398
上一篇:cpp蒙特卡洛计算23个人中至少有两个生日是同一天的概率?
下一篇:Big Data and Data Mining Lesson Glossary