使用unordered_map與向量作爲對象的可能的內存問題

我正在編寫一個程序，它決定了每個數字的主因子高達120000.我試圖學習如何使用unordered_map的，以便我有一個地圖用int作爲關鍵映射到其主要因素的向量。使用unordered_map與向量作爲對象的可能的內存問題

我提出的算法包括列出120000以下的所有素數，然後遞歸處理2個素數（2x3 = 6,3x19 = 57等）的產物，然後使用3個素數（2x2x5 = 20,3x5x7 = 105等）等等，直到我有一個完整的列表。我寫程序採取任何最大值（不只是120000），它可以完美地處理值高達MAX_C = 45000，但是當我用MAX_C> 50000嘗試它時，它會中斷（並且經常崩潰我的計算機。

我試圖重寫程序，以避免使用unordered_maps，用我的factorsAndTotal結構的載體，但我有類似的問題。我試圖分配任意大量內存的映射，但無濟於事。

我猜這是一個記憶問題，但我不確定，所以我不能真正發佈代碼片段，對不起！

#include <iostream> 
#include <vector> 
#include <unordered_map> 

using namespace std; 

//structs 
struct factorsAndTotal 
{ 
    vector<int> factors; 
    int total; 
}; 

//prototypes 
vector<int> allPrimesLessThan(int); 
void buildPrimeFactorsMap(); 
vector<factorsAndTotal> siftNextSet(vector<factorsAndTotal>); 

//globals 
int MAX_C = 45000; 
vector<int> primes; 
unordered_map <int, vector<int> > mapPrimeFactors; 

//main 
int main() 
{ 
    primes = allPrimesLessThan(MAX_C); 
    mapPrimeFactors.reserve(MAX_C); 

    buildPrimeFactorsMap(); 

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

    return 0; 

} 

void buildPrimeFactorsMap() 
{ 
    vector<int> chainOfFactors; 
    vector<factorsAndTotal> sifting; 

    factorsAndTotal temp; 

    //add primes themselves to the map 
    int size = primes.size(); 
    for (int i=0; i<size; i++) 
    { 
     //put them in map itself and get struct ready for recursion later 
     chainOfFactors.push_back(primes[i]); 

     mapPrimeFactors[primes[i]] = chainOfFactors; 
     temp.factors = chainOfFactors; 
     temp.total = primes[i]; 

     sifting.push_back(temp); 

     chainOfFactors.clear(); 
    } 
    //recursion 
    while (!sifting.empty()) 
    { 
     sifting = siftNextSet(sifting); 
    } 

    cout<<"factors found"<<endl; 
} 

vector<factorsAndTotal> siftNextSet(vector<factorsAndTotal> input) 
{ 
    int total = 0; 
    int i = 0, j = 0; 
    int size = input.size(); 
    bool finished = false; 
    vector<int> chainOfFactors; 
    vector<factorsAndTotal> output; 
    factorsAndTotal temp; 

    for (i=0; i<size; i++) 
    { 
     //find last factor 
     while (primes[j] < input[i].factors.back()) j++; 

     while (!finished) 
     { 
      total = input[i].total*primes[j]; 

      if (total > MAX_C) 
      { 
       finished = true; 
      } 
      else 
      { 
       chainOfFactors = input[i].factors; 
       chainOfFactors.push_back(primes[j]); 

       mapPrimeFactors[total] = chainOfFactors; 

       temp.total = total; 
       temp.factors = chainOfFactors; 
       output.push_back(temp); 

       chainOfFactors.clear(); 

       j++; 
      } 
     } 
     finished = false; 
     j=0; 
    } 

    return output; 
} 

//returns primes less than a given number 
vector<int> allPrimesLessThan(int x) 
{ 
    vector<int> findingPrimes; 

    int i = 0, j = 0; 

    bool isPrime; 

    for (i=2; i<=x; i++) 
    { 
     isPrime = true; 

     for (j=0; j<findingPrimes.size(); j++) 
     { 
      if (i%findingPrimes[j] == 0) isPrime = false; 
     } 

     if (isPrime) findingPrimes.push_back(i); 
    } 

    cout<<"primes found"<<endl; 

    return findingPrimes; 
}

來源

2014-02-16 jimbarrett27

抱歉，無法找到你的問題。但是，我會建議一種不同的方法：首先找到所有適當的素數。（我實際上會建議使用[Erastothenes Sieve]（http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes），而不是你目前使用的暴力方法。）然後，只需遍歷所有你想分解的數字，並嘗試通過遍歷所有素數來分解它，嘗試它們是否是當前數字的一個因子。如果它們是，請注意，如果它們不是，請嘗試下一個素數，如果素數大於當前數字，break - >您已經擁有所有素數... – Xarn

數字的因子。（或者只是在外出時將倍數分解，如果在運行餘數中達到1，則分解。）對所有想知道因子的數字重複此操作。 – Xarn

該問題與您選擇的MAX_C的值無關。看看這個循環中，與變量j的用法一起：

while (primes[j] < input[i].factors.back()) 
    j++; 

while (!finished) 
{ 
    total = input[i].total*primes[j];

當我運行你的代碼，J超越了素數載體的限制，因爲你在同時增加Ĵ（！完了）循環。

while（！finished）循環並不會限制j將會走多高，因此您需要確保循環終止或執行其他操作，而不是訪問具有j的超出邊界值的素數向量。

的一種方式，以確保您不出門界：

while (!finished && j < primes.size()) 
{ 
    total = input[i].total*primes[j];

來源

2014-02-17 00:20:52 PaulMcKenzie

使用unordered_map與向量作爲對象的可能的內存問題

回答

相關問題