从矢量或更好地使用内存（排序基数）最快的擦除元素

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。另外，不要忽略将整个数组复制到另一个容器的可能性，对其进行分类，然后将其复制回来。根据数组的大小，这可能会有所帮助。