有效地去除C++中的聯合大型向量？

-2

我需要聯合一百萬個向量來做這件事我正在使用下面的程序。每個矢量包含十億個元素。聯盟的結果不應包含任何重複。有效地去除C++中的聯合大型向量？

set<unsigned> myfunc() 
{ 
    vector<vector<unsigned> > vec(1000000); 
    set<unsigned> result; 
    for(int i=0; i<1000000; i++) 
     result.insert(vec[i].begin(), vec[i].end()); //vec[i] contains a billion elements 

    return result; 
}

有什麼辦法可以將兩個大向量有效地結合起來？由於上面的代碼似乎運行了2個多小時。我正在與128 GB RAM

來源

2016-12-30 Jannat Arora

'向量VEC （1000000）;' - 這是一個單「無符號」值的向量，而不是多個向量。 – PaulMcKenzie

@PaulMcKenzie謝謝你的錯字。 –

_「...聯合一百萬個向量...每個向量都包含十億個元素......」_ - 做數學 - 這需要多少內存？一個XY問題的氣味。 –

的顯而易見的方法的機器上的代碼是使用std::set_union()與std::sort() ED std::vector<unsigned> S：

std::vector<unsigned> myfunc() 
{ 
    vector<vector<unsigned> > vec(1000000); 
    std::vector<unsigned> result, tmp; 
    for(int i=0; i<1000000; i++) { 
     std::sort(vec[i].begin(), vec[i].end()) 
     std::set_union(vec[i].begin(), vec[i].end(), 
         result.begin(), result.end(), 
         std::back_inserter(tmp)); 
     swap(tmp, result); 
     tmp.clear(); 
    } 
    return result; 
}

來源

2016-12-30 12:30:32

謝謝，但剛剛出於好奇，爲什麼std :: set_union比設置插入更快？ –

它不使用不可預知的訪問模式隨機分佈在內存中的數據結構。相反，它在連續內存中進行高度結構化的內存訪問。我還沒有測量兩種實現的效果，但我確定使用'std :: set_union（）'要快得多（儘管不是理論漸近複雜度是相同的）。 –

有效地去除C++中的聯合大型向量？

回答

相關問題