현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

STL vector erase 메써드의 성능에 대한 질문.

nachnine의 이미지
글쓴이: nachnine / 작성시간: 수, 2004/04/14 - 12:33오후

MFC로 Application을 개발하고 있는데
CStringArray를 쓰다가 vector<string>으로 바꿔서 구현했습니다.
push_back이 CString::Add에 비해서 월등히 빠르더군요.
만족했습니다.

하지만 문제!

vector 의 insert/erase가 너무 느립니다

백만개가 넘는 element가 있는 string vector에 대해서
index(? iterator )를 앞쪽에 두고 erase 메써드를 호출하면
100ms 가 넘게 걸리더군요.

반면 CStringArray의 RemoveAt/InsertAt은 vector의
그것에 비하면 월등히 시간히 짧게 걸리더군요.

테스트 환경은 다음과 같습니다.
AMD Athlon XP 2200+
RAM 1GB
MSVC 6
Windows 2000 Pro.

질문1.

원래 vector의 insert / erase 메써드는 element의 갯수가
엄청나게 많을때 ( 백만개 ~ 수천만개 )는 속도가 느리나요?
( CStringArray보다 성능이 낫다고 생각해서 구현했는데 erase는
느리더군요 )

질문2.
그럼 방안은?
CStringArray는 무겁다고 생각해서 쓰기 싫고,
vector로 위의 문제를 해결하는 방법은 없을까요?


 vector<string> m_vString;

 string s = "blahblah";

 ASSERT ( m_vString.size() > 1000000 );

 int nIndex = 0 ;  // 제일 앞쪽에 문자열 삽입

 DWORD sTime = GetTickCount();
 m_vString.erase (&m_vString[nIndex]);
 ASSERT ( GetTickCount() - sTime > 100 );

 m_vString.insert(& m_vString[nIndex], s);
Forums: 
프로그래밍 QnA
buelgsk8er의 이미지

글쓴이: buelgsk8er / 작성시간: 수, 2004/04/14 - 12:48오후

앞뒤에서만 insertion이 일어나고 []를 지원해야 된다면 deque를, 중간에서도 insertion이 일어날 수 있고 []가 필요없다면 list를 추천합니다. 자세한 것은 자료구조 책과 STL책을 참조하시길..

nachnine의 이미지

글쓴이: nachnine / 작성시간: 수, 2004/04/14 - 12:50오후

중간에 insert , remove가 필요하고
[] 도 필요합니다

당연히 list, queue를 고려했었는데 위와 같은 이유로
vector를 사용한것입니다

구현을 찾아봤습니다.



void CStringArray::RemoveAt(int nIndex, int nCount)
{
	ASSERT_VALID(this);
	ASSERT(nIndex >= 0);
	ASSERT(nCount >= 0);
	ASSERT(nIndex + nCount <= m_nSize);

	// just remove a range
	int nMoveCount = m_nSize - (nIndex + nCount);

	DestructElements(&m_pData[nIndex], nCount);

	if (nMoveCount)
		memmove(&m_pData[nIndex], &m_pData[nIndex + nCount],
			nMoveCount * sizeof(CString));
	m_nSize -= nCount;
}

iterator erase(iterator _P)
		{copy(_P + 1, end(), _P);
		_Destroy(_Last - 1, _Last);
		--_Last;
		return (_P); }

보시면 아시다시피 CStringArray는 memmove 를 사용하고
vector는 iteration 할것으로 예상되는 copy를 호출합니다.

답은 " 별도의 class를 제작한다 " 인걸까요?
- 물론 구현하면 되지만, 다른 더 좋은 방법이 있는지 알아보는겁니다.

buelgsk8er의 이미지

글쓴이: buelgsk8er / 작성시간: 수, 2004/04/14 - 12:52오후

중간에 insertion/erase가 필요한데 어째서 vector입니까? vector는 그런 연산에 쥐약입니다. 당연히 list라야죠..

kcando의 이미지

글쓴이: kcando / 작성시간: 수, 2004/04/14 - 12:53오후

코드가 좀 위험해 보입니다.

첫번째 항목을 지우길 원하신다면,
if (! m_vString.empty())
m_vString.erase(m_vString.begin());
처럼 사용하시고요.
제일 앞에 자료를 추가하시려면,
m_vString.insert(m_vString.begin(), s);
를 호출해야 합니다.

하지만, vector에 100만개의 자료가 들어 있고 제일 앞쪽(인덱스 0)을 삭제할 경우 999999개의 자료가 1바이트 앞쪽으로 복사 됩니다. 다시 제일 앞쪽에 자료를 삽입하게 되면 999999개의 자료가 1바이트 뒤쪽으로 복사가 되겠군요(정확하지 않을지도 모릅니다 ;;;).
즉, vector는 자료의 끝을 제외한 다른 부분에서 삽입/삭제가 일어날 경우 엄청난 복사를 수반하게 됩니다.

자료의 앞뒤 부분에 추가/삭제가 빈번히 발생한다면 deque를 사용하는게 좋습니다. 자세한 내용은 관련 자료를 참고하시기 바랍니다.

여담으로 STL은 정확한 이해없이 사용하게 되면 많은 구현/성능 상의 문제가 발생하게 됩니다. Effective STL의 일독을 권합니다.

buelgsk8er의 이미지

글쓴이: buelgsk8er / 작성시간: 수, 2004/04/14 - 12:54오후

중간 insertion/erase과 random access([]) 를 동시에 빠르게(=상수시간에) 지원하는 자료구조는 제가 알기론 hash테이블을 제외하곤 없습니다. 프로그래머는 어느쪽이 더 중요한 연산인가를 생각해서 선택해야죠. vector든 list든. 아니면 deque든.

nachnine의 이미지

글쓴이: nachnine / 작성시간: 수, 2004/04/14 - 12:56오후

위에 인용한 코드는
실제 코드가 아닙니다.

상황이 어떤지를 이야기하기 위해서 적은 코드입니다.
구현상의 문제는 없구요 ( Assertion failed 되는 코드는 아닙니다.)

그리고 operator [] 가 필요하기때문에 리스트를 사용할수 없습니다.

girneter의 이미지

글쓴이: girneter / 작성시간: 수, 2004/04/14 - 12:57오후

전 제가 쓰는 데이터의 양이 다 작은것들이라서
웬만한건 다 map 으로 구현해 버리는데
아예 map 을 쓰는건 어떤가요?
효율이 많이 떨어지나요?

개념없는 초딩들은 좋은 말로 할때 DC나 웃대가서 놀아라. 응?

bugiii의 이미지

글쓴이: bugiii / 작성시간: 수, 2004/04/14 - 12:59오후

map 이나 hash 쓰시는게 상황에 맞는 것 같습니다.

nachnine의 이미지

글쓴이: nachnine / 작성시간: 수, 2004/04/14 - 1:02오후

Array Index를 Hash의 key로 사용하는 map을 쓰면 되겠군요

수정:

Hash나 map으로는 InsertAt RemoveAt의 구현이 불가능합니다.;;;

key가 index라고 하면 위와 같은 연산을 할때 모든 key를 다 바꿔줘야합니다

luscent의 이미지

글쓴이: luscent / 작성시간: 수, 2004/04/14 - 1:08오후

그건.

vector가 상수시간에 접근할 수 있는 random access가 가능하지만

insertion 등의 처리에서는 list가 훨씬 빠르므로 list를 사용하라고 되어 있습니다.

그리고 find, find_if 등의 functional등을 이용하면 그리 불편하지 않게

vector를 대체할 수 있을 것 같으네요..

buelgsk8er의 이미지

글쓴이: buelgsk8er / 작성시간: 수, 2004/04/14 - 1:09오후

모든 요구조건을 다 만족하는 자료구조는 세상에 없습니다. 요구조건의 우선순위를 분석해서 적절한 자료구조들을 선택하거나, 포인터를 이용해서 각각의 요구조건에 맞는 복수개의 자료구조들을 일일히 관리하거나 하는 수 밖에 없습니다.

nachnine의 이미지

글쓴이: nachnine / 작성시간: 수, 2004/04/14 - 1:28오후

char** 을 member로 하는 class를 구현해야겠네요

buelgsk8er의 이미지

글쓴이: buelgsk8er / 작성시간: 수, 2004/04/14 - 1:41오후

자료구조책을 읽어보시면 도움이 되리라 생각합니다.

qufdl113의 이미지

글쓴이: qufdl113 / 작성시간: 수, 2004/04/14 - 1:56오후

해결책은 벡터를 쓰지 않는것. 윗분들이 해결책은 제시해주셨네요 ㅡㅡ;

1년전에 vector를 사용했던적이 있었습니다.
그당시 vector에 편리함에 너무도 감탄했었죠.

하지만,
vector는 많은 데이터를 처리하게 되면 느려진다는걸 어디선가 읽게 되었죠.
이유는 vector는 내부에서 확보된 메모리공간이 없을때 현재 있는 자료의 2배를 늘려준다고 들었습니다.

즉.

1개째 데이터 입력하면. 내부에 2개가 생성되고.
2번째 데이터 넣으면 꽉차면서 4개 생성.
3번째엔 그냥 삽입.
4번째 데이터넣으면 메모리공간 8개 잡고 삽입하는 식으루여.
:
:
왠지 오버헤드가 생길듯 하더군요.

그래서 vector는 많은 데이터가의 삽입.삭제가 빈번하게 발생하며 빠른 응답시간을 요구할때 적합하지 않다고 하더군요.
그래서 데이터양이 많으면 느려지는건 당연하겠죠.

☆

nachnine의 이미지

글쓴이: nachnine / 작성시간: 수, 2004/04/14 - 1:57오후

흠

자료구조 같은건 옆에 두고 살아야되는데

계속 MSDN보고 MFC 객체 갖다쓰다 보니,

필요가 없었는데, 다시 봐야겠군요.

도움주신분들 감사합니다.

휴학한지 오래되서 모를 문제는 아닌거 같은데;;

.. 아아..

nachnine의 이미지

글쓴이: nachnine / 작성시간: 수, 2004/04/14 - 2:07오후 

 void insert(iterator _P, size_type _M, const _Ty& _X)
		{if (_End - _Last < _M)
			{size_type _N = size() + (_M < size() ? size() : _M);
			iterator _S = allocator.allocate(_N, (void *)0);
			iterator _Q = _Ucopy(_First, _P, _S);
			_Ufill(_Q, _M, _X);
			_Ucopy(_P, _Last, _Q + _M);
			_Destroy(_First, _Last);
			allocator.deallocate(_First, _End - _First);
			_End = _S + _N;
			_Last = _S + size() + _M;
			_First = _S; }
		else if (_Last - _P < _M)
			{_Ucopy(_P, _Last, _P + _M);
			_Ufill(_Last, _M - (_Last - _P), _X);
			fill(_P, _Last, _X);
			_Last += _M; }
		else if (0 < _M)
			{_Ucopy(_Last - _M, _Last, _Last);
			copy_backward(_P, _Last - _M, _Last);
			fill(_P, _P + _M, _X);
			_Last += _M; }}

VC98에 들어있는 vector 구현을 보고 있는데 어지러워 죽겠군요

size_type _N = size() + (_M < size() ? size() : _M);
nachnine의 이미지

글쓴이: nachnine / 작성시간: 수, 2004/04/14 - 3:35오후

그냥 무식하게 결국은 char** 를 사용하여

vector<string>과 CStringArray를 대체할 클래스를 구현완료 했습니다.

제일 용량을 적게 차지하고, 또 결코 느리지 않군요.

도움 주신 분들 모두모두 감사합니다 ^^

bugiii의 이미지

글쓴이: bugiii / 작성시간: 수, 2004/04/14 - 4:18오후

에디터 만드시나요?

nachnine의 이미지

글쓴이: nachnine / 작성시간: 수, 2004/04/14 - 4:20오후

예리하시군요.

벤치마킹 대상
ultraedit 기능
editplus 성능
crimsoneditor 가벼움
acroedit 디자인

bugiii의 이미지

글쓴이: bugiii / 작성시간: 수, 2004/04/14 - 4:25오후

vector< string* > 같은 것이 만드신 것과 같은 것 아닌가요?

아마 VC 에 포함된 string 이 내부적으로 포인터 하나만 딸랑 쓰는 타입이 아니라면 vector< string* > 하고 속도차이가 좀 날 듯 하네요.

그리고, 직접적인 행으로 가는 것에 정말 빠른 속도가 꼭 필요한지도 한번 생각해 볼 일입니다.

과연 행으로 바로 가는 동작이 많은지 아니면 행이 필요할 때 처음부터 행구분자의 개수를 세서 구하는 것이 좋은지 등은...

최대 행수는 미리 계산하고 삽입 삭제시 +/- 하면 될테구요. 맨앞/마지막은 이걸로 왔다 갔다 할 수 있을거구요.

각 행번호 출력도 비슷하게 생각하면 되지 않을까요?

그리고 SGI 의 rope 라는 컨테이너도 한번 고려해 봐야 할 것 같습니다.

p.s. 만드시는 거... 공개하시는 건가요???

nachnine의 이미지

글쓴이: nachnine / 작성시간: 수, 2004/04/14 - 4:27오후

아주 골치가 아프군요.

vector 쓰지 않습니다

그냥 char** 를 멤버로 두고
memmove, memcpy , strlen 만 쓰는 클래스를
만들었습니다.

100메가 파일 읽어들이는데 5초가 걸리네요

( 물론 syntax hightlighting 실시간으로 다 합니다 )

에디터 개발에 관한 좋은 자료 있으면 도와주시면 감사하겠습니다 ^^

p.s. 소스공개는 일부만 가능하다면 하고, ( 워낙 허접해서;; )
라이센스는 프리로 갈 겁니다.
업무가 아니라 공부하는걸 목적으로 개발하는거라서,,
언제 릴리즈 될지는 모릅니다. -_-

관심있으면 홈페이지 방문해보세요 :)

bugiii의 이미지

글쓴이: bugiii / 작성시간: 수, 2004/04/14 - 4:39오후

VC6 string 의 sizeof 가 얼마가 되나요?

앞에 말씀드린 vector< string* > 도 한번 시도해보세요. 만드신 클래스가 string 의 포인터 (new 로 만든)를 저장하는 것과 비슷한 역할 아닌가 해서 드린 말씀입니다...

nachnine의 이미지

글쓴이: nachnine / 작성시간: 수, 2004/04/14 - 4:52오후

bugii 님 정말 감사드립니다. ^^

vector<string*>

잘 되네요

괜히 어렵게 구현했어요;;;

bugiii의 이미지

글쓴이: bugiii / 작성시간: 수, 2004/04/14 - 5:22오후

:wink:

p.s. bug + iii, 벌레3호입니다...

ssggkim의 이미지

글쓴이: ssggkim / 작성시간: 수, 2004/04/14 - 5:56오후

nachnine wrote:

관심있으면 홈페이지 방문해보세요 :)

지금 접속이 안되는데요... :?

nachnine의 이미지

글쓴이: nachnine / 작성시간: 수, 2004/04/14 - 6:02오후

그거 페이크 에요;;; 첫화면에 장난을 좀 쳐놨어요.

화면을 잘 살펴보세요 ^^

bugiii의 이미지

글쓴이: bugiii / 작성시간: 수, 2004/04/14 - 6:07오후

속았습니다.... 근데, 이미지네요....

ssggkim의 이미지

글쓴이: ssggkim / 작성시간: 수, 2004/04/14 - 6:27오후

nachnine wrote:
그거 페이크 에요;;; 첫화면에 장난을 좀 쳐놨어요.

화면을 잘 살펴보세요 ^^

허걱~
status bar에 주소/BACKUP_HOME 이라고 나오는게 이상하긴 했지만...
완전히 속았습니다. :wink:

세벌의 이미지

글쓴이: 세벌 / 작성시간: 목, 2004/04/15 - 7:18오전

ssggkim wrote:
nachnine wrote:
그거 페이크 에요;;; 첫화면에 장난을 좀 쳐놨어요.

화면을 잘 살펴보세요 ^^

허걱~
status bar에 주소/BACKUP_HOME 이라고 나오는게 이상하긴 했지만...
완전히 속았습니다. :wink:

페이지의 아래에

Quote:
익스플로러가 아닌 브라우저로 이페이지를 본다면 낭패;;

이렇게 써 놓으셨군요. 제가 지금 익스플로러 아닌 브라우저로 보고 있다는 :wink:

세벌 https://sebuls.blogspot.kr/

tinywolf의 이미지

글쓴이: tinywolf / 작성시간: 목, 2004/04/15 - 3:45오후

컼.. 우리학교...

사사삭 (사라진다)

ㅡ_ㅡ;

Seven..의 이미지

글쓴이: Seven.. / 작성시간: 목, 2004/04/15 - 7:44오후

대단하시네요

베타릴리즈 되면 꼭 알려주세요+_+

테스터가 되어드리지욧 :lol:

VENI VIDI VICI

댓글 달기

텍스트 포맷에 대한 자세한 정보

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.