벡터

이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다.
아래의 포스트는 개인적인 용도로 내용을 요약한 것 입니다.

    https://github.com/AeroCodeX/

벡터

배열처럼 인덱스를 통한 임의접근이 가능하고,

연결 리스트처럼 논리적 수용량에 제한이 없는 고수준 배열(List).

여러개의 배열(청크)이 모여 하나의 벡터를 이룬다.

꽉 찬 상태에서 데이터 삽입을 시도하면,

새로운 메모리(청크)를 할당받아 뒤에 덧붙인다.

배열에서는 기존보다 더 큰, 

아예 새로운 배열을 만들어야 했다.

벡터의 특성

• 여러개의 독립적인 배열(청크)을 접합한 것 이다.
• 논리적 수용량의 제한이 없다.
• 어느 위치에서든 데이터를 가져오는 것은 빠르다.  (상수시간)
• 램덤 액세스로 데이터를 가져올 때, 인덱스 계산으로 인한 약간의 오버헤드가 있다.  (그래도 상수시간)
• 처음이나 중간에 위치한 데이터를 삽입/삭제하는 것은 느리다.  (선형시간)
• 마지막에 위치한 데이터를 삽입/삭제하는 것은 빠르다.  (상수시간)
• 새로운 청크를 할당받을 때 큰 오버헤드가 있다.

벡터의 수용량 증가(capacity)

모든 청크가 꽉 찬 상태에서 뒤에 데이터 삽입을 시도하면,

새로운 청크를 끝 부분에 이어붙이고 진행한다.

새롭게 할당받는 청크의 수는 현재 청크수의 0.5배 또는 1배이며, 

이 경우, 동적할당으로 발생하는 오버헤드를 감수해야 한다. 

빈번한 청크확장은 성능하락의 원인이 된다.

새로운 동적할당이 빈번하게 이루어지지 않도록,

처음부터 벡터의 할당량을 적절히 크게 잡아놓으면 오버헤드를 줄일 수 있다. 

벡터의 인덱스 계산 오버헤드

벡터는 여러개의 부분배열이 연결된 상태이므로,

해당 인덱스에 대응되는 청크를 찾기위한 산술식이 오버헤드를 일으킨다.

전체범위를 훑어야한다면, 순방향이나 양방향 이터레이터를 사용하는 것이 성능상 좋다.

옆으로 한칸씩 옮겨가기 때문에, 부분배열을 얻기위한 산술식을 수행하지 않기 때문이다.

추가적으로 for-each 구문을 사용하면,

암묵적으로 순방향 이터레이터를 사용한다.

자바에서는 왜 벡터를 사용하지 않는가?

Java에서 벡터는 ArrayList의 Synchronized 형태이므로,

병렬 안전성이 필요한 경우가 아니라면 ArrayList를 사용하는 것이 성능상 좋다.