자유 게시판 / Forum

vector.size( ) 수행시간...

by prof, 10월 4일, 15:23

vector <int> v ;

여기에서 v.size( ) 를 계산하는 시간은 한번 측정을 해봐야 할 것 같은데요.
이게 compiler마다 따라서...

v.size( ) := v.end( ) - v.begin( )

이렇게 한다면 constant time인데요. 이게 실제 원소 갯수만큰 걸리지 않지 싶네요.
누가 한번 실험을 해서 좀 공개해주세요.

assist , 10월 4일, 16:26
 최근에 바뀌었군요. 알려주셔서 감사합니다. 
prof , 10월 4일, 15:51
 실험을 해보니까 size( )에는 O(1) 시간, vector 크기에는 상관이 없네요.

---------- 수행 결과 --------------
 push_back( )  : 0.014

 size_back( )  : 0.011001

Process returned 0 (0x0)   executio
n time : 0.078 s
Press any key to continue.

----------- 실험 코드 -----------
// 수행시간 측정하는 함수
// > g++ thisfile.cpp std=C14++

#include <iostream>
#include <chrono>
#include <cmath>
#include <functional>  // 이걸 사용해야 function을 변수로 넘길 수 있어요.
#include <vector>
#include <array>

using namespace std ;


#define N 300000  // 천만개의 공간, 반드시 밖에서 global로  잡하야 한다.
array <long, N>  myarray ;
int   carray[N] ;

void vec_push_back(){
    vector <long >  myvector ;
	for ( long i = 0; i < N; ++i )	{
		myvector.push_back( i ) ;
	}
}

void vec_size_back(){
    vector <long >  myvector ;
    int vsize ;
	for ( long i = 0; i < N; ++i )	{
        vsize = myvector.size( ) ;
		myvector.push_back( i ) ;
	}
}


// 시간을 측정할 함수는 반드시 void fun( ) 로 만들어야 합니다.
//  잡다부리한 parameter 넣으면 안됩니데이....

double Time_Check( string MSG, function <void ( )> target ){
    chrono::system_clock::time_point mybegin, myend ;
    chrono::duration<double> sec ;
    double tsec ;

	mybegin = chrono::system_clock::now();
        target();  // 측정할 함수
	myend   = chrono::system_clock::now() ;
	sec = myend - mybegin ;

    tsec = sec.count() ;
    cout << "\n" << MSG << ": " << tsec << endl;
    return( tsec ) ;
} // end of Time_Check( ) by Zoh 2020. 추석 전전날 아침에


int main(){

    Time_Check(" push_back( )  ",   vec_push_back) ;
    Time_Check(" size_back( )  ",   vec_size_back) ;

	return 0;
}
------------- end of code ---------- 
prof , 10월 4일, 15:33
 >> 누가 언급을 했네요.

That depends on the container and c++ standard used. For example, std::set::size( ) in C++03 could work in up to linear complexity. 

As for C++14, size( ) of all frequently used containers (at least, vector, list, set, map, unordered_set, unordered_map, queue and deque) runs in constant time.

C++14 이상에서는 상수시간에 크기를 계산한다네요.