從矢量或更好地使用內存（排序基數）最快的擦除元素

Question

我有麻煩，我從基數排序算法創建實現，但我認爲我可以使用更少的內存，我可以！但是......我這樣做是在使用後擦除矢量的元素。問題：執行3分鐘vs 17秒。如何擦除元素更快？或...如何更好地使用內存。

sort.hpp

#include <iostream> 

#include <vector> 
#include <algorithm> 

unsigned digits_counter(long long unsigned x); 

void radix(std::vector<unsigned> &vec) 
{ 
    unsigned size = vec.size(); 
    if(size == 0); 
    else { 
    unsigned int max = *max_element(vec.begin(), vec.end()); 
    unsigned int digits = digits_counter(max); 

    // FOR EVERY 10 POWER... 
    for (unsigned i = 0; i < digits; i++) { 
     std::vector < std::vector <unsigned> > base(10, std::vector <unsigned>()); 

#ifdef ERASE 
     // GET EVERY NUMBER IN THE VECTOR AND 
     for (unsigned j = 0; j < size; j++) { 
    unsigned int digit = vec[0]; 

    // GET THE DIGIT FROM POSITION "i" OF THE NUMBER vec[j] 
    for (unsigned k = 0; k < i; k++) 
     digit /= 10; 
    digit %= 10; 

    // AND PUSH NUMBER IN HIS BASE BUCKET 
    base[ digit ].push_back(vec[0]); 
    vec.erase(vec.begin()); 
     } 

#else 
     // GET EVERY NUMBER IN THE VECTOR AND 
     for (unsigned j = 0; j < size; j++) { 
    unsigned int digit = vec[j]; 

    // GET THE DIGIT FROM POSITION "i" OF THE NUMBER vec[j] 
    for (unsigned k = 0; k < i; k++) 
     digit /= 10; 
    digit %= 10; 

    // AND PUSH NUMBER IN HIS BASE BUCKET 
    base[ digit ].push_back(vec[j]); 
     } 
     vec.erase(vec.begin(), vec.end()); 
#endif 

     for (unsigned j = 0; j < 10; j++) 
    for (unsigned k = 0; k < base[j].size(); k++) 
     vec.push_back(base[j][k]); 
    } 
    } 
} 


void fancy_sort(std::vector <unsigned> &v) { 
    if(v.size() <= 1) 
    return; 
    if(v.size() == 2) { 
    if (v.front() >= v.back()) 
     std::swap(v.front(), v.back()); 
    return; 
    } 
    radix(v); 
} 

sort.cpp

#include <vector> 

#include "sort.hpp" 

using namespace std; 

int main(void) 
{ 
    vector <unsigned> vec; 

    vec.resize(rand()%10000); 

    for (unsigned j = 0; j < 10000; j++) { 
    for (unsigned int i = 0; i < vec.size(); i++) 
     vec[i] = rand() % 100; 
    fancy_sort(vec); 
    } 


    return 0; 
} 

我只是學習......這是我的Deitel的C第2章++。所以...如果有人有更復雜的解決方案......我可以學習如何使用它，難度無關緊要。

結果 不擦除：

g++ -O3 -Wall sort.cpp && time ./a.out 
./a.out 2.93s user 0.00s system 98% cpu 2.964 total 

隨着擦除：

g++ -D ERASE -O3 -Wall sort.cpp && time ./a.out 
./a.out 134.64s user 0.06s system 99% cpu 2:15.20 total 

Answer 1

std::vector沒有做成具有從中拆下的部件。這是你必須忍受的事實。速度和內存使用之間的交易是一個經典問題。對於載體，任何去除（除了結束）都是昂貴的並且是浪費。這是因爲每次刪除元素時，程序都必須在內部重新分配陣列，或者必須移動所有元素以填充空白。如果你繼續使用矢量，那麼這是一個永遠無法克服的終極限制。

矢量爲您的問題：快速但很多的內存使用情況。

另一個（可能）最佳極端（記憶明智）是std::list，這對任何地方的任何東西都沒有任何問題。另一方面，訪問元素只能遍歷整個列表到元素，因爲它基本上是一個doubly-linked list，你不能通過它的編號訪問一個元素。

列出您的問題：最好的內存使用情況，但由於訪問列表元素較慢，所以速度較慢。

最後，中間的理由是std::deque。它們提供了向量和列表之間的中間地帶。他們在記憶中不是連續的，但可以通過他們的數字找到物品。從中間去除元素不一定會導致向量中的相同破壞。 Read this瞭解更多關於它們的信息。

deques爲您的問題：中間的理由，根據問題，可能快速的內存和訪問。

如果內存是您最關心的問題，那麼一定要使用列表。這是最快的。如果您想要最通用的解決方案，請使用deque。另外，不要忽略將整個數組複製到另一個容器的可能性，對其進行分類，然後將其複製回來。根據數組的大小，這可能會有所幫助。