vector, deque 및 목록에 대한 push_back

Question

C++ 루틴을 최적화하려고합니다. 이 루틴의 주요 병목은 객체 벡터의 push_back()입니다. 대신 deque를 사용하여 시도하고 목록을 시도했습니다. 그러나 이상하게도 (그리고 이론과는 반대로) deque와 list 구현은 벡터보다 훨씬 느리게 실행됩니다.

실제로 벡터 함수보다 deque와 list 구현에서 훨씬 더 느리게 clear()가 실행됩니다. 이 경우에도 벡터 구현은 목록 구현이 가장 느린 반면 가장 빠른 것 같습니다.

모든 포인터?

참고 : vector reserve()는 구현을 가속화 할 수 있었지만 크기가 알려지지 않았기 때문에 수행 할 수 없었습니다.

감사합니다.

Answer 1

개체 자체 또는 개체에 대한 포인터를 뒤로 밀고 있습니까? 포인터는 일반적으로 개체의 크기에 관계없이 복사하는 데 4-8 바이트 만 있으면 훨씬 빠릅니다.

Answer 2

루틴의 작동에 대한 자세한 정보가 필요합니다.

push_back()의 속도가 걱정되는 곳에서는 clear()이 걱정됩니다. 컨테이너를 만들고 뭔가를 한 다음 덤핑하고 있습니까? 당신이 clear()에 대한 참조

결과는 vector<>는 메모리의 자장하게 블록을 해제하기 때문에, deque<> 여러 해제해야하고, list<>은 각 요소에 대해 하나의 해제해야합니다.

Answer 3

Deque는 벡터보다 복잡한 구조를 가지며 두 가지 사이의 속도 차이는 특정 구현과 푸시 백된 요소의 실제 수에 크게 의존하지만 많은 양의 데이터의 경우 더 빠릅니다. clear()는보다 복잡한 기본 구조를 제거하기 때문에 느려질 수 있습니다. 목록의 경우도 마찬가지입니다.

Answer 4

벡터가 큐 또는 목록보다 빠르거나 빠를 것으로 예상됩니다. 그것은 더 간단한 데이터 구조입니다. 충분히 에 벡터가 큰

1. 검사가 새로운 항목을 보유 : vector::push_back과 관련하여

   , 그것은 두 가지 작업을 수행해야한다.

2. 새 항목을 삽입하십시오.

일반적으로 벡터의 크기를 조정하고 operator[]을 사용하여 항목을 설정하면 1 단계가 생략됩니다.

업데이트 : 원본 포스터에 예제가 필요합니다. 회 128 메가 삽입하여 출력

push_back   : 2.04s 
reserve & push_back : 1.73s 
resize & place  : 0.48s 

아래 코드 컴파일 이전 P4 머신 데비안/레니 g ++ -O3 실행.

#include <iostream> 
#include <time.h> 
#include <vector> 

int main(int,char**) 
{ 
    const size_t n=(128<<20); 

    const clock_t t0=clock(); 
    { 
    std::vector<unsigned char> a; 
    for (size_t i=0;i<n;i++) a.push_back(i); 
    } 
    const clock_t t1=clock(); 
    { 
    std::vector<unsigned char> a; 
    a.reserve(n); 
    for (size_t i=0;i<n;i++) a.push_back(i); 
    } 
    const clock_t t2=clock(); 
    { 
    std::vector<unsigned char> a; 
    a.resize(n); 
    for (size_t i=0;i<n;i++) a[i]=i; 
    } 
    const clock_t t3=clock(); 

    std::cout << "push_back   : " << (t1-t0)/static_cast<float>(CLOCKS_PER_SEC) << "s" << std::endl; 
    std::cout << "reserve & push_back : " << (t2-t1)/static_cast<float>(CLOCKS_PER_SEC) << "s" << std::endl; 
    std::cout << "resize & place  : " << (t3-t2)/static_cast<float>(CLOCKS_PER_SEC) << "s" << std::endl; 

    return 0; 
} 

Answer 5

가와 push_back() 느리다 및 예비 더 도움이되는하지와 관련하여, MSVC에서 사용되는 STL의 구현은 다음과 같이 작동합니다 : 당신이 먼저 공간을 보유하는 벡터를 만들 때 내가 10 개 요소를 생각하십시오. 그 다음부터는 벡터가 꽉 차있을 때마다 벡터의 요소 수의 1.5 배 공간을 예약합니다. 그래서 10, 15, 22, 33, 49, 73, 105, 157과 같은 것 ... 재 할당은 비쌉니다.

정확한 크기를 모르더라도 reserve()가 유용 할 수 있습니다. reserve()는 필요하다면 vector가 자랄 수 있도록하지 않는다. 당신이 reserve()를하고 벡터가 그 크기를 넘어 서면, 예비 때문에 여전히 개선 된 것이 있습니다. 벡터가 훨씬 작아지는 것으로 판명되면 일반적으로 성능이 더 작은 크기에서 더 잘 작동하기 때문에 괜찮을 수도 있습니다.

어떤 전략이 가장 효과적인지 알아 보려면 RELEASE 모드에서 프로필해야합니다.

Answer 6

추가 할 객체의 수를 모르는 경우에는 최적의 솔루션을 찾는 것이 매우 어렵습니다. 당신이 할 수있는 일은 당신이 알고있는 비용을 최소화하는 것입니다.이 경우에 당신의 벡터는 끊임없이 크기가 조정됩니다.

두 가지 방법으로이 작업을 수행 할 수 있습니다.

1) 건물을 분할하고 마무리합니다. 여기서 목록을 벡터로 구성하여 충분히 큰 것으로 보장하고 완료되면 다른 벡터로 복사합니다.

예.

std::vector<Foo> hugeVec; 
hugeVec.reserve(1000); // enough for 1000 foo's 

// add stuff 

std::vector<Foo> finalVec; 
finalVec = hugeVec; 

2) 또는, 당신의 벡터 개체의 또 다른 세트에 대한 충분한 전체 전화 예약 인 경우;

if (vec.capacity() == vec.size()) 
    vec.reserve(vec.size() + 16); // alloc space for 16 more objects 

당신은 모든 요소가 크기 조정에 복사가 발생하지 않은 다른 컨테이너를 선택할 수 있습니다,하지만 당신의 병목 현상은 새로운 요소에 대한 개별 메모리 할당 될 수 있습니다.

Answer 7

벡터가 빨라지려면 충분한 공간을 확보해야합니다(). 각각의 성장은 끔찍한 비용이기 때문에 큰 차이가 있습니다. 당신이 모르는 경우에, 좋은 추측을하십시오.

Answer 8

개체의 복사본이 느린 경우 "push_back()"속도가 느려질 수 있습니다. 기본 생성자가 빠르며 복사본을 피하기 위해 스왑을 사용하는 방법이 있다면 훨씬 빠른 프로그램을 만들 수 있습니다.

void test_vector1() 
{ 
    vector<vector<int> > vvi; 
    for(size_t i=0; i<100; i++) 
    { 
     vector<int> vi(100000, 5); 
     vvi.push_back(vi); // copy of a large object 
    } 
} 

void test_vector2() 
{ 
    vector<int> vi0; 
    vector<vector<int> > vvi; 
    for(size_t i=0; i<100; i++) 
    { 
     vector<int> vi(100000, 5); 
     vvi.push_back(vi0); // copy of a small object 
     vvi.back().swap(vi); // swap is fast 
    } 
} 

결과 :

당신은 당신이 그것으로 할 건지에 따라 컨테이너를 선택해야

VS2005-debug 
* test_vector1 -> 297 
* test_vector2 -> 172 

VS2005-release 
* test_vector1 -> 203 
* test_vector2 -> 94 

gcc 
* test_vector1 -> 343 
* test_vector2 -> 188 

gcc -O2 
* test_vector1 -> 250 
* test_vector2 -> 156 

Answer 9

.

관련 작업은 확장 (push), 삽입 (필요하지 않을 수도 있음), 추출, 삭제입니다.

cplusplus.com에는 컨테이너 유형별 작업에 대한 아주 좋은 개요가 있습니다.

조작이 push 인 경우 벡터가 다른 모든 것을 제합니다. deque에 대한 좋은 점은 고정 된 청크를 할당하므로 조각 메모리를보다 효율적으로 사용할 수 있다는 것입니다.