V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
woshichuanqilz
V2EX  ›  C++

如何实现多线程计算组合数

  •  
  •   woshichuanqilz · 2022-04-09 19:56:36 +08:00 · 2015 次点击
    这是一个创建于 943 天前的主题,其中的信息可能已经有所发展或是发生改变。

    现在我想计算 80 里面取 20 个数的所有组合可能, 这个数据量比较大, 计算比较耗时, 享用多线程计算应该会快, 但是不知到多线程怎么写这个程序

    https://stackoverflow.com/questions/9430568/generating-combinations-in-c

    计算方法参考的这个链接

    #include <iostream>
    #include <algorithm>
    #include <vector>
    
    int main() {
        int n, r;
        std::cin >> n;
        std::cin >> r;
    
        std::vector<bool> v(n);
        std::fill(v.end() - r, v.end(), true);
    
        do {
            for (int i = 0; i < n; ++i) {
                if (v[i]) {
                    std::cout << (i + 1) << " ";
                }
            }
            std::cout << "\n";
        } while (std::next_permutation(v.begin(), v.end()));
        return 0;
    }
    
    9 条回复    2022-04-11 11:04:17 +08:00
    ChaosesIb
        1
    ChaosesIb  
       2022-04-09 20:02:08 +08:00
    什么场景?如果不需要立即求值的话可以写个迭代器
    caidaoli
        2
    caidaoli  
       2022-04-09 22:34:55 +08:00
    你耗时主要在 std::cout 上,用一个变量存储,组合完成再输出
    helloworld000
        3
    helloworld000  
       2022-04-09 22:49:09 +08:00
    你主要的耗时是一个个打印

    但是你也没办法把所有结果一次存内存里,C(80, 20) 太大了

    每 100,000 就结果写进 disk ,然后清空 vector 或者 string 可以试试
    helloworld000
        4
    helloworld000  
       2022-04-09 22:49:34 +08:00
    同 ls ,迭代器是最好的选择
    cwaken
        5
    cwaken  
       2022-04-10 11:14:49 +08:00 via iPhone
    有一个双线程方法,利用头尾指针那套思维
    woshichuanqilz
        6
    woshichuanqilz  
    OP
       2022-04-10 18:43:42 +08:00 via Android
    @ChaosesIb 我有一个表格里面有 80 行数据,我想把里面所有取二十行情况都列出来。满足条件的就保存下来。
    这个迭代器的写法能不能给点提示?
    kilasuelika
        7
    kilasuelika  
       2022-04-11 09:50:45 +08:00 via Android
    C(80,20)的量级是 2 的 6
    1 次方左右,你
    kilasuelika
        8
    kilasuelika  
       2022-04-11 09:51:28 +08:00 via Android
    C(80,20)的量级是 2 的 61 次方左右,你确信能遍历所有可能性吗?
    aloxaf
        9
    aloxaf  
       2022-04-11 11:04:17 +08:00
    @woshichuanqilz #6 你这是典型的 X-Y 问题,建议描述一下你的原始需求
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5092 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 05:43 · PVG 13:43 · LAX 21:43 · JFK 00:43
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.