list vs vector

vector와 list의 timecomplexity다. 

이것만 보면 서로 장단 점이 있어  random access 를 할 때는  vector로 구현하고 i/d 를 쓸 때는 list를 쓰면 될 것 같다 하지만 99%가 vector를 쓴다 find 때문이다 TimeComplexity는 같지만

실행해보면 vector의  find가 훨씬 빠르다.

그 이유는 두가지 이유가 있는데 첫번째로 메모리 구조 때문이다.

 

vector는 연속되게 저장된다 하지만 list는 3개씩 떨어진 상태로 저장된다.

find를 하게 되면 vector에서는 1부터 4까지 하나씩 움직이며 찾게 되고 움직인 뒤 그 메모리는 캐시 된다 그런데 list는 떨어진 상태로 존재하기 때문에 1을 찾고 캐시를 하고 캐쉬가 캐시 미스가나고 2를 찾고 캐쉬를 하고 캐쉬미스가 되고 하는 과정을 거치게 된다.

그래서 find는 같은 TimeComplexity지만 vector가 list보다 훨씬 빠르다.

 

두번째로는 병렬 프로그래밍과 과련이 있다.

 

벡터안에 있는 데이터에 8개 혹은 16개의 코어로 병렬 연산을 하고 싶다. 캐쉬라인의 배수 만큼 짤라서 각각의 코어에 할당만 해주면 쉽게 구연할 수 있지 list의 경우 linked list로 구연되어있는 이를 코어의 개수 만큼 간단히 짜를 수 있는 방법이다 그래서 병렬프로그래밍에 있어서 list는 사용하기 불편하다.

 

 

 

운영중인 카톡방입니다.

https://open.kakao.com/o/gsMhUFie

C/C++/C# 언리얼/유니티 /질문