ベクトルからの最も速い消去要素またはメモリのより良い使用（基数ソート）

Question

私は問題を抱えていますが、私は基数ソートアルゴリズムから実装を作成しますが、私はメモリを減らすことができます。しかし、...私はこれを使用した後にベクトルの要素を消去します。問題：3分の実行対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++の私の第二章です...学んでいます。だから誰かがもっと複​​雑な解決策を持っているなら...それを使う方法を学ぶことができますが、難しさは重要ではありません。 消去せずに

結果：消去して

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をご覧ください。

問題の原因：中程度ですが、問題に応じて、おそらくメモリとアクセスの両方が高速です。

メモリが最も重要な関心事なら、間違いなくリストに入れてください。これは最速です。最も一般的な解決策が必要な場合は、dequeを使用してください。また、配列全体を別のコンテナにコピーしてソートしてからコピーする可能性を無視しないでください。配列のサイズによっては、参考になるかもしれません。