C++无序设置内存不足

Question

该程序遍历1到400的4个数字的每个组合,并查看可以从产品中制作多少个唯一数字.我相信unordered_set用来保存已经检查的数字太大了,因此它退出了; 任务经理告诉我它是1.5 GB.

有什么方法可以让这个代码运行？我认为可能会拆分该组或以某种方式找到更有效的公式.

注意:根据评论,我想再说一遍,我没有存储所有250亿个数字.我只存储~100,000,000个号码.问题有RANGE400,但我正在寻找一个全面的解决方案,可以处理500,甚至1000没有内存问题.

#include <iostream>
#include <unordered_set>
using namespace std;

const int RANGE = 400;

int main(){

    unordered_set<long long> nums;

    for(long long a=1; a<=RANGE; a++)
    {
        for(long long b=a; b<=RANGE; b++)
        {
            for(long long c=b; c<=RANGE; c++)
            {
                for(long long d=c; d<=RANGE; d++)
                {
                    unordered_set<long long>::const_iterator got = nums.find(a*b*c*d);
                    if (got == nums.end())
                    {
                        nums.insert(a*b*c*d);
                    }
                }
            }
        }
        cout << a << endl;
    }

    cout << nums.size() << endl;

    return 0;
}

Answer 1

您需要使用64位编译器编译代码,以允许分配超过大约2GB的内存.你在运行它的机器上还需要至少4GB的RAM,或者最多需要几乎永远完成.

"bitset",每个条目使用一位,将占用大约3GB的内存.

使用现有的代码,它将在具有64位g ++编译器的Linux机器上使用大约4GB的内存,完成大约需要220秒,给出答案:

86102802
1152921504606846975

根据/ usr/bin/time -v:

Command being timed: "./a.out"
User time (seconds): 219.15
System time (seconds): 2.01
Percent of CPU this job got: 99%
Elapsed (wall clock) time (h:mm:ss or m:ss): 3:42.53
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 4069336
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 0
Minor (reclaiming a frame) page faults: 679924
Voluntary context switches: 1
Involuntary context switches: 23250
Swaps: 0
File system inputs: 0
File system outputs: 0
Socket messages sent: 0
Socket messages received: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0