Data Structures
-
[ Open Data Structures ] - Space-Efficient Linked List - 2DataStructure 2021. 5. 14. 20:00
Nodeを包括する関数の場合, template 宣言のため、 コンパイラーの問題が発生する。これらの問題はMeta programmingに関する問題点と推定される。SEList自体が今まで学んできたデータ構造の中で一番やっかい構造の一つである。 参考 : Introduction to metaprogramming in C++ | InfoWorld Removing an Element 자료의 제거는 추가와 유사하다. 가장 먼저 자료의 index i를 포함하는 노드 u를 찾는다. 그리고 블록의 크기가 b - 1보다 작아지지 않도록 주의하며 자료가 삭제될 수 없는 모든 경우를 고려하는 것이다. Amortised Analysis of Spreading and Gathering 여기서는 Add와 Remove에 의해 호출될 수 있는 Gath..
-
[ Open Data Structures ] - The model of ComputationDataStructure 2021. 5. 6. 01:48
The Model of Computation 자료구조의 Operation의 이론적인 Running time을 정확하게 분석하기 위해서 우리는 Mathematical model of computation이 필요하다. 이를 위해서, w-bit word-RAM 모델을 사용할 것이다. RAM은 'Random Access Machine'의 약자이다. 이 모델에서는, w-bit word를 저장하고 cell로 구성되어 있는 random access memory에 접근할 수 있다. 이는 곧 예를 들어서, Memory cell은 어떤 정수의 집합 {0, .. 2^w - 1}을 나타낼 수 있다는 것이다. 'Memory cell is an electronic circuit that stores one bit of infor..
-
[ Open Data Structures ] - Randomisation and ProbabilityDataStructure 2021. 5. 6. 00:13
Randomisation and Probability 어떤 자료구조를 구현함에 있어서 앞으로 혹은 이전에 랜덤화를 채택하는 일이 있을 것(혹은 있었다)이다. 이 자료구조는 저장되는 자료나 수행되는 작업(Operation)에 대해 독립적인 무작위 선택을 차용한다. 이러한 연유로 같은 작업을 한 번 이상 수행하게 되면 각각 다른 결과를 얻게 된다. 이런 형태의 자료구조를 분석함에 있어서 우리는 이들의 Expected Running Time에 중점을 두게 될 것이다. 딱딱한 표현을 쓰자면 랜덤화 된 자료구조의 Running time은 Random Variable(랜덤 변수)이며 여기서는 그 랜덤 변수의 Expected value에 대한 공부를 하기로 한다. 셀 수 있는 집합 U 안에 있는 이산 랜덤 변수(Di..
-
[ Open Data Structures ] - Rootish Array Stack - 1DataStructure 2021. 3. 6. 16:04
Rootish Array Stack Get and Set 이러한 방법을 토대로 Get과 Set을 직관적으로 작성할 수 있다. 가장 먼저 적절한 block b를 찾아내고 해당 block 내의 index i가 위치할 index j를 계산하면 된다. 마지막으로 호출한 각 함수마다 적절한 조치를 취하면 끝이다. 일반적으로 이 작업들은 Constant time내에 완료된다. Add and Remove Grow()에서 소모하는 시간을 제외하면 Add의 Running time은 Array Stack처럼 원소들의 위치를 교환하는 작업에 압도적으로 의존하게 된다. 따라서 Array Stack과 같은 O(1 + n - i )의 Running time을 갖는다. Remove는 Add와 비슷하게 동작한다. i+1, i+2, ..
-
[ Open Data Structures ] - Dual Array Deque - 1DataStructure 2021. 3. 4. 14:34
Dual Array Deque : Building a Deque From Two Stacks /* 수정 : Balance() 함수의 back stack을 확장하는데 있어서 For-Loop에 Get(nb + j )를 Get(nf + j)로 수정 */ Dual Array Deque를 만들어 본다. Array Stack을 두 개 사용해서 전에 만들었던 Array Deque와 비슷한 성능을 낼 수 있다. 사실, Asymptotic performance자체는 Array deque와 크게 차이가 나지 않지만, 두 개의 간단한 자료구조를 조합하여 정교한 자료구조를 만드는 좋은 예제가 될 수 있다. Dual Array Deque는 두 개의 Array Stack을 사용하는 List를 나타낸다. Array Stack이 배..
-
[ Open Data Structures ] - Array Deque - 1DataStructure 2021. 2. 28. 16:41
Array Deque : Fast Deque Operation using an array Array Queue는 배열의 한 지점에서 정보를 저장하고 반대편에서 삭제하는 자료구조였다. Array Deque는 양지점 어느 쪽에서든 자료의 저장/삭제를 효율적으로 할 수 있도록 해준다. 이 자료구조는 Array Queue에서 봤던 Circular array를 사용하여 List interface를 implement한다. 각 변수가 의미하는 바는 Array Queue와 크게 다르지 않다. 삭제할 index를 추적하는 mElem2Remove, 배열에 저장된 원소의 개수를 추적하는 mNumOfElem, 그리고 배열 mArr. Get(_i) Set(_i, _x) Get(_i)과 Set(_i, _x)의 operation은..
-
[ Open Data Structures ] - Array Queue - 1DataStructure 2021. 2. 27. 22:31
Array Queue : An Array-Based Queue FIFO ( First In First Out ) 자료구조인 Array Queue를 가볍게 만들어본다. Array Stack은 배열에 들어온 순서( Add(x) Operation )대로 다시 나갔다( Remove() Operation ). 가만 생각해보면 Array Stack을 FIFO Queue를 구현하는데 선택하는 것은 비효율적인 선택이라고 할 수 있다. 왜냐하면, 배열의 한쪽 끝에서 Add를 하면 Remove는 반드시 정반대에서 수행해야 하기 때문이다. 두 작업 중 하나는 반드시 배열의 머리에서 수행되어야만 한다면 다른 하나는 반드시 꼬리에서 수행되어야만 하고 이는 원소의 개수 n에 비례한 Running time을 요구하게 된다. Que..
-
[ Open Data Structures ] - Array Stack - 2DataStructure 2021. 2. 24. 16:23
Growing and Shrinking Resize() method는 꽤 직관적이다. 크기가 기존 mSize의 두 배인 새로운 배열(resizedArray)을 만들고 mSize개의 원소를 새로운 배열에 복사한다. 그리고 Array Stack class의 mArr가 resizedArray를 가리키게 만든다. Resize() 시간을 계산하는 것은 어렵지 않다. 2*mSize의 새로운 배열 resizedArray를 만들고 mSize개의 원소를 복사한다. 따라서, O(mSize)의 time을 요구한다. 전의 Running time을 계산할 땐 이 Resize()를 무시했다. 여기서는 Amortised analysis기법을 사용하여 분석해보기로 한다. 이것을 통해서 Add/Remove가 각각 수행될 비용을 계산하..