자료구조

C++ STL 컨테이너

  • vector는 임의 참조 O(1), 끝에 삽입 O(1), 끝을 제외한 임의 삽입은 O(n)이다. 배열이 가득 차는 순간 크기를 두 배로 늘리며 O(n)이지만 자주 발생하는 일이 아니므로 상환 입력 시간amortized insertion time으로 계산하면 여전히 O(1)이다.
    reserve() 호출이 눈에 뜨일 정도의 성능상의 효과가 없었다는 점을 발견하고 놀랐다. (TCPPL, 2013)
  • deque는 앞/끝 모두 O(1)이지만 메모리 상에서 연속적인 공간으로 할당되지 않는다.
  • list는 doubly linked list로 어느 위치에나 삽입/삭제가 O(1)이지만 검색/접근은 O(n)이다. 임의 접근이 어려우므로 제네릭 알고리즘으로는 성능이 떨어져, 자체 정렬 멤버 함수인 sort()를 제공한다. 요세푸스 문제가 유명하다.
  • set/multiset은 red-black tree(balanced tree 다)를 이용해 정렬된 상태로 저장된다. 삽입/검색/삭제 모두 O(log n) 이다. 배열을 미리 할당해 놓지 않아도 되기 때문에 잠재적으로 적은 공간을 사용한다는 장점이 있다. 또한 키의 집합을 특정 순서로 차례대로 접근할 수 있어 유용한 경우가 있다. multiset은 같은 값이 허용되며(다중집합), 삽입 순서가 유지된다. Java는 multiset을 지원하지 않는다.
  • map/multimap은 set과 비슷하지만 정렬이 가능한 key와 그 key가 가리키는 객체의 pair로 저장된다. Java에서 유사한 구현은 TreeMap이다. C++에서는 역사적인 이유로 hash table이 아닌 tree 기반의 map이 디폴트가 되었다고 한다.
  • unordered_set/unordered_map은 hash table로 저장하며 O(1)이지만 key가 충돌할 경우 worst는 O(n)이다. Java는 HashSet/HashMap, Python은 dict로 구현되어 있다. STL에 hash_map이 있었지만 C++ Standard Library에 포함되지 못하고 C++ 11에서 unordered_map으로 추가됐다.

기본 제공 배열보다는 vector, string, array 같은 컨테이너를 선택한다. 이유는,

  1. 기본 제공 배열은 배열에서 포인터로 암시적인 변환이 일어난다.
  2. 기본 제공 배열의 경우 크기를 기억해야 하기 때문에 수많은 오류의 원인이 된다.
  3. C 스타일 문자열의 포인터 의미 구조는 미숙한 표기법을 낳고 프로그래머의 추가적인 작업을 필요로 하기 때문에 역시 수많은 오류(메모리릭 같은)의 원인이 된다.

std::vector

Note that vector inherits from _Vector_val, which contains the following members:

pointer _Myfirst;   // pointer to beginning of array
pointer _Mylast;    // pointer to current end of sequence
pointer _Myend; // pointer to end of array
_Alty _Alval;   // allocator object for values

(TCPPL, 2013)

Java의 ArrayList가 C++의 vector와 유사하다.

  • LinkedList implements it with a doubly-linked list.
  • ArrayList implements it with a dynamically re-sizing array.

장점

  1. 촘촘하게 저장되어 메모리 오버헤드가 존재하지 않는다.
  2. 순회가 매우 빠르다. 포인터를 통해 간접하지 않아도 되며, 현대적 컴퓨터는 연속적인 접근에 최적화되어 있다.
  3. 간단하고 효율적인 임의 접근을 지원한다. 따라서 sort(), binary_search()(정렬된 시퀀스에 유효) 같이 vector에 대해 수많은 알고리즘이 효율적이다.

끝에 삽입, 임의 참조 모두 O(1)이다. list는 vector의 순회 탐색 비용에 비해 10배 이상이 될 수 있다. (TCPPL, 2013)

std::array

std::array<int, 3> a1 = {1, 2, 3};
std::array<std::string, 4> aa = {"a", b"};
// 마지막 두 원소는 빈 문자열

array의 원소 개수는 컴파일 타임에 알 수 있기 때문에 size()constexptr이다.

장점

  • 배열의 크기를 정확히 알 수 있다.
  • 포인터가 자동으로 잘못 타입 캐스팅 되는 것을 피할 수 있다.
    • 타입이 다르면 포인터로 변환되지 않는다.
  • 기본 제공 배열은 포인터로 잘못된 오프셋을 지정할 수 있다.
  • STL 반복자, 알고리즘을 이용할 수 있다.

std::valarray

단일 차원 수치 배열로 수치 벡터 산술 연산 및 다양한 첨자 연산자, 분할 및 간접 액세스를 제공한다.

Differences between HashTable and HashMap

Hashtable is synchronized. If synchronization becomes an issue, you may also look at ConcurrentHashMap.

Vector 또한 synchronized이다. HashTable 대신 HashMap을 사용하는 것과 마찬가지로 주로 ArrayList를 사용한다. 차이점은 Vector contains many legacy methods that are not part of the collections framework. 레거시다.

트리(그래프)

Trie

In computer science, a trie, also called digital tree and sometimes radix tree or prefix tree (as they can be searched by prefixes), is a kind of search tree—an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings.

Binary Search Tree vs. Binary Heap

BST have average of O(log⁡ n) for insertion, deletion, and search. BST는 노드가 자식(child)의 왼쪽 보다 크고, 오른쪽 보다 작은 값으로 구성된다.

Binary Heap have average O(1) for findMin(MinHeap인 경우 root이므로 )/findMax(MaxHeap 경우) and O(log n) for insertion and deletion 또는 MinHeap일때 findMax는 마찬가지로 O(log n)이다. BST와 달리 child의 좌우 크기는 관계 없다.

Binary Heap는 Complete Binary Tree이며, 인덱스가 depth에 따라 일정하게 1,2,4,8개 순으로 필요하므로, 일반적으로 array로 표현된다.

How is Binary Heap represented?

  • parent: arr[(i-1)/2]
  • left child: arr[(2*i)+1]
  • right child: arr[(2*i)+2]

Operations on MinHeap:

  • 추가(O(log n)): 맨 마지막에 값을 추가하고 parent와 비교하여 작을수록 parent로 계속 swap하며 올린다.
  • 삭제(O(log n)): 해당 자리에 MIN값을 추가하고 root까지 swap하며 올린다(decrease). root를 제거하고(즉, MIN 제거) 맨 마지막 값을 root에 둔다. 다시 child까지 swap하며 내린다(heapify). 만약 left child가 사라졌다면 root가 되었던 맨 마지막 값은 left child가 되어 다시 complete binary tree 형태가 된다. 즉, left에는 항상 빈 값이 없는 상태가 된다.

Applications of Heaps:

  • Heap Sort
  • Priority Queue
  • Graph Algorithms: The priority queues are especially used in Graph Algorithms like Dijkstra’s Shortest Path and Prim’s Minimum Spanning Tree.
  • K’th Largest Element in an array, Sort an almost sorted array, Merge K Sorted Arrays.

레드블랙트리

노드에 색을 부여하여 트리의 균형을 유지하며, 탐색, 삽입, 삭제 연산의 수행시간이 각각 O(logN)을 넘지 않는 매우 효율적인 자료구조다. 일반적인 레드블랙트리는 삽입이나 삭제를 수행할 때 트리의 균형을 유지하기 위해 상당히 많은 경우를 고려해야 한다는 단점이 있으며, 이에 따라 프로그램이 복잡해지고 그 길이도 증가한다. 그러나, 좌편향 레드블랙 Left-Learning Red-Black, LLRB트리는 삽입이나 삭제 시 고려해야 하는 경우의 수가 매우 작아서 프로그램의 길이도 일반 레드블랙트리 프로그램의 1/5 정도에 불과하다는 장점을 갖는다. 또한 LLRB 트리는 실제로 AVL 트리, 2-3 트리, 2-3-4 트리, 일반 레드블랙트리보다 우수한 성능을 갖는다. (파이썬과 함께하는 자료구조의 이해, 2018)


2017 Book Reports · 2018 Book Reports · 2019 Book Reports · Activation, Cost Functions · Apache Thrift · C++ · Docker · Go · HTML, CSS, JavaScript · Hadoop, Spark · Information Retrieval · Java · Keras · LifeHacks · MySQL · NLP 실험 · NLP · Naive Bayes · OAuth 2.0 · OOP · PHP · PyTorch · Python Data Structure Cheatsheet · Python · RSA · Sent2Vec · Software Deployment · Support Vector Machine · Word2Vec · XGBoost · Scikit Learn · 개발 생산성 · 거리 · 기하와 벡터 · 데이터 마이닝 · 데이터 사이언스 · 딥러닝 응용 · 딥러닝 · 머신러닝 분류기 · 머신러닝 · 비지니스 · 사회심리학 · 수학 · 알고리즘 · 영어 · 이산수학 · 인공지능 · 자료구조 · 진화생물학 · 통계학 응용 · 통계학 ·
is a collection of Papers I have written.
© 2000 - Sang-Kil Park Except where otherwise noted, content on this site is licensed under a CC BY-NC 4.0.
This site design was brought from Distill.