표준 벡터 성능/대안

Question

데이터를 일시적으로 처리하고 저장해야합니다. 현재 최대 요소에 도달하면 std::vector::push_back을 사용하여 데이터를 추가하고 std::vector::erase을 사용하여 요소를 삭제합니다. 내 문제는 내가 많은 양의 데이터를 처리해야하고 최대량에 도달하면 지우기가 성능에 영향을 미친다는 것이다. 그래서 나는 최적화로 매 yms마다 데이터를 추가하고 x 요소를 지우기로 결정했습니다. 시작하려면 벡터에 일정량을 예약해야합니다. 나는 다른 곳으로 데이터를 전달하기 위해 const double *std::vector<T>::data() 함수가 필요하고 어떤 변환/복사 또는 아무것도 할 수 없기 때문에 벡터를 사용합니다. 그것은 단지 빠르다.

std::vector<double> data; 
size_t max; // there are millions of elements, e.g. 2000000 
data.reserve(max); 

// happens every x microseconds 
void receive(double val) { 
    data.push_back(val); 
} 

// timed every x ms 
void update() { 
    if (data.size() > max) 
     data.erase(data.begin(),data.end()+(data.size()-max)); 
} 

내 질문은 : 어떻게하면 더 효율적으로 만들 수 있습니까? 다른 컨테이너를 사용하여? 컨테이너를 const double *으로 변환 할 수 있습니까?

필자는이 설정으로 항상 최대 값을 초과했음을 알았습니다. 성능 저하의 원인이 될 수 있습니까? 다음 코드로 문제가 해결 되었습니까?

if (data.size() > max*0.8) 
     data.erase(data.begin(),data.begin()+(data.size()-max*0.8)); 

미리 감사드립니다.

Answer 1

의견에서 말했듯이, 귀하의 요구 사항은 실제로 박스에 넣었습니다. 내가 알고있는 유일한 컨테이너는 인접한 데이터를 std::vector이라고합니다.

std::vector과 관련된 두 개의 시간 소 거기가 있습니다. 첫 번째는 이미 예약 된 용량에있는 벡터에서 push_back으로 시도 할 때입니다. 새 버퍼를 할당해야하며 이전 버퍼 내용이 새 버퍼에 복사됩니다. 용량에 도달하기 전에 요소를 지우면 쉽게 피할 수 있습니다. 두 번째는 벡터의 끝 부분을 제외한 다른 곳에서 지울 수 있습니다. 이를 위해서는 요소를 버퍼의 이전 위치에서 새 위치로 복사해야합니다. 이 부분은 피할 수 없습니다. 당신이 할 수있는 한 많은 요소들을 한 번에 지우면서 가능한 한 드물게 이것을하는 것입니다. 버퍼가 가득 찰 때마다 데이터의 일부를 삭제

void receive(double val) { 
    static const size_t drop_size = max/2; 
    if (data.size() == data.capacity()) { 
     data.erase(data.begin(), data.begin() + drop_size); 
    } 
    data.push_back(val); 
} 

:

여기서 둘 조건을 제공하는 모드이다. 임의로 최대/2를 선택했지만 실제 요구 사항에 맞게 임계 값을 조정할 수 있습니다.

좋은 컴파일러는 erase 동안 요소 복사를 최적화하지만 memcpy을 사용하면 더 잘 수행 할 수 있습니다. 이 경우 다음과 erase을 대체 할 수

memcpy(&(data[0]), &(data[drop_size]), sizeof(double) * (data.size() - drop_size)); 
data.resize(data.size() - drop_size); 

당신이해야 확실히 벤치 마크이 당신이 그것으로 가기로 결정하기 전에. 크기를 조정할 때 벡터의 용량을 줄이는 구현 인 vector에 대해서는 알지 못하지만 표준 요구 사항은 아닙니다. 편집 : 표준에는 현재 용량 아래에서 크기를 조정할 때 반복자가 무효화되지 않아 용량이 이 아니며이 감소하지 않을 것이라는 요구 사항이 포함됩니다.