벡터에서 요소를 지우거나 메모리를 더 잘 사용 (기수 정렬)

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의 제 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에서 제거 부품이 만들어되지 않습니다. 그것은 당신이 함께 살아야한다는 사실입니다. 속도와 메모리 사용 간의 거래는 고전적인 문제입니다. 벡터를 사용하면 모든 제거 (끝에서 제외)는 비용이 많이 들고 낭비입니다. 이는 요소를 제거 할 때마다 프로그램이 배열을 내부적으로 재 할당하거나 void를 채우기 위해 모든 요소를 ​​이동해야하기 때문입니다. 벡터를 계속 사용하면 극복 할 수없는 궁극적 인 제한 사항입니다.

벡터 : 빠르고 많은 메모리 사용.

기타 (아마도) 최적의 극단 (메모리 단위)은 std::list입니다. 아무 곳이나 제거하는 데 전혀 문제가 없습니다. 반면에 요소를 액세스하는 것은 기본적으로 doubly-linked list이기 때문에 전체 목록을 요소로 반복하는 것만 가능합니다. 요소 번호에 액세스 할 수 없습니다.

문제 목록 : 메모리 사용이 가장 좋지만 목록 요소 액세스가 느리기 때문에 속도가 느립니다.

마지막으로, 중간 근거는 std::deque입니다. 그것들은 벡터들과 목록들 사이의 중간 지점을 제공합니다. 그들은 기억이 연속적이 아니지만, 그 숫자로 항목을 찾을 수 있습니다. 중간에서 요소를 제거한다고해서 반드시 벡터에서 동일한 파괴가 발생하는 것은 아닙니다. Read this에 대해 자세히 알아보십시오.

문제에 대한 답변 : 중급, 문제에 따라 메모리 및 액세스 속도가 빠름.

메모리가 가장 중요한 관심사라면 분명히 목록과 함께하십시오. 그게 가장 빠릅니다. 가장 일반적인 해결책을 원한다면 deque로 가라. 또한 전체 배열을 다른 컨테이너에 복사하고 정렬 한 다음 다시 복사 할 가능성을 무시하지 마십시오. 배열의 크기에 따라 도움이 될 수 있습니다.