회사에서 작업하던 중간에….
동료: 이거 너무 느린데?
까막: 응? 좀 보자.
(잠시후)
까막: 우욱. size()는 O(n)이잖아. 뭔 배짱으로 쓰는거냐.
동료: O(1)이잖아. 확인 했는데?
까막: linked list로 구현이 되어 있을테니 O(n)이지.
동료: 응?
궁금증이 도진 두 공학도. size()위에 커서를 놓고 F12를 칩니다. MSVC 기본 STL의 size()로 가더군요.
// list 429 MSVC 2003 기준.
size_type size() const
{ // return length of sequence
return (_Mysize);
}
헛. 정말로 O(1)입니다. 둥실둥실 당황한 까막군.
까막: 어.. 어라.. STLPort를 보자. 분명히 O(n)이었는데?
동료: 그래?
역시 눈으로 확인하는게 최고지요. STLPort를 보러 갑니다.
// STLPort5 stl/_list.h 316라인.
size_type size() const {
size_type __result = distance(begin(), end());
return __result;
}
네.. std::distance를 쓰고 있군요. Bidirectional Iterator이니 O(n)입니다. 하아. 이런 차이점이 생기는 군요. 왜 생겼을까 고민해보았습니다.
std::list의 가장 큰 장점이라면, Insert할때 Cost가 적다는 점입니다. std::vector같은 클래스는 중간에 끼워 넣으려면 끼워넣는 위치 뒤쪽에 있는 요소들은 전부 뒤로 한칸씩 밀어줘야하기 때문에, 빡세지만 std::list는 그냥 포인터만 바꿔주면 되기 때문에 간단하지요. 그리고, splice라는 같은 타입의 리스트끼리 데이터를 O(1)으로 이동시켜주는 멋진 기능도 갖고 있지요. 게다가 splice는 allocator를 호출하지도 않습니다! 포인터만 옮겨주면 끝이거든요. 🙂
문제는, size()를 O(1)으로 구현한 MSVC STL은 태생적으로 O(n)의 splice를 갖게 된다는 점입니다. splice는 range를 받도록 되어있으며, 이 range의 크기를 알아야 list의 크기를 바꿀 수 있기 때문이지요. 물론, range가 전체 범위라면, 해당 리스트의 크기를 받아와서 처리하면 되긴하지만, 이건 특수한 케이스이고 원칙적으로는 O(n)이 됩니다.
반면에, STLPort의 std::list는 O(1)의 splice를 갖게 되지요. size()를 호출될때마다 계산하기 때문에 splice알고리즘이 빠르게 작동하게 됩니다.
어느 구현이 낫다고 이야기할 수는 없습니다. size()를 많이 호출하는 코드라면 MSVC STL이 낫겠지만, splice를 주로 쓰는 코드라면 STLPort가 낫겠지요. 대부분의 사람들이 Linked List의 크기는 O(n)으로 가져온다고 알고 있는 상황을 상정해본다면, STLPort쪽이 오류를 줄일 수 있는 쪽이라는 생각도 듭니다.
저는 std::list는 가급적 사용하지 않습니다. 중간에 끼워넣어야 하는 자료구조는 대부분 정렬된 형태의 자료가 많은데, 이 경우에는 std::set이나 std::map을 주로 이용하고, 끼워넣는 일이 없으면 std::deque나 std::vector를 사용하기 때문이지요. std::list는 splice가 필요한 경우에나 사용합니다. 어쩔수 없이 써야하는 경우는 size를 별도로 caching을 하지요. (물론 머리를 잘 굴려야 합니다만.. -_-)
흔히 상식으로 알고있고, 쉽게 생각하고 쓰는 것도, 구현체별로 조금씩 다른 상황이 의외로 많습니다. 이런걸 조금씩 주의하면서 쓰는게 결국은 센스죠 센스. 한가지 더 재밌는건, STLPort는 node allocator를 쓰기때문에 메모리를 재사용하는 반면에, MSVC STL은 항상 malloc과 free를 사용합니다. 테스트해보면 STLPort가 더 빠르게 나오지요. 후훗. (특히나 Multithreaded환경에선… 까막군이 작업하는 코드는 구동시 쓰레드가 대충 40-50개정도 생성됩니다. -_-)
+ 회사에서는 STLPort를 쓰기 때문에, 결국, list를 deque로 바꿔버렸습니다. splice를 쓰는 것도 아니고, 중간에 끼워넣을 일도 고민해보니 없더라구요. 🙂
+ 쓰다 쓰다 열받아서 WordPress에 포함된 TinyMCE를 포기해버렸습니다. 그냥 기본 에디터가 더 편하군요. _-_
