DataStructure
-
[ Open Data Structures ] - Hash Table ( Chaining )DataStructure 2021. 8. 19. 01:09
* hash 함수는 다음에 배워 구현합니다. 이 챕터로써는 해시 함수를 포함한 코드를 실행시킬 수 없습니다. (Random numbers plucked from the atmosphere (irishtimes.com)) -> Atmospheric noise Add Operation Hash table은 List를 요소로 갖는 배열 t로 구현을 합니다. 격납되어 있는 모든 요소의 수를 n으로 추적합니다. Remove Operation Multiplicative Hashing * C/C++기준입니다. 다른 프로그래밍 언어에서는 Undefined Behaviour일 수 있습니다. 또한, 여기서 등장하는 HashCode(x)와 Hash(x)상당히 혼란스럽습니다. Hash(x)는 x에게 부여된 어떤 수를 갖고 배..
-
-
[ Open Data Structures ] - Skiplists - 2DataStructure 2021. 7. 29. 13:49
SkiplistList 이렇게 되면 Get/Set 함수도 함께 자명해집니다. ? 어렵습니다. Add 함수가 두 개라서 헷갈릴 수 있습니다. 그런데 둘은 Parameter가 다르다는 점을 알아야 합니다. 노드를 받는 Add를 하나씩 분석해보며 이해하도록 합시다. 각 노드의 변의 길이를 결정하는 부분이 조금 헷갈렸으나 천천히 짚어보니 이해가 됐습니다. Node* u = sentinel; 은 기존 Skiplist처럼 좌상단의 노드부터 시작합니다. k는 추가하려는 노드의 높이를 나타냅니다. r = h는 Skiplist의 높이를 취합니다. 첫 번째 While문은 Skiplist의 높이를 조건으로 사용합니다. 두 번째 while 문에서 처음 j가 등장합니다. 기본적으로 j는 수직으로 이동할 때는 값이 변화하지 않습..
-
[ Open Data Structures ] - Skiplists - 1DataStructure 2021. 7. 28. 17:28
Skiplists 이번엔 다양한 활용이 가능한 Skiplist라는 아름다운 자료구조를 공부해보록 합니다. 이 자료구조를 사용하여 우리는 Add, Get, Set, Remove을 O ( log(n) )의 Running time을 갖는 List interface를 구성할 수 있으며 모든 오퍼레이션이 Expected running time이 O ( log(n) )을 취하는 Sorted Set을 구성할 수도 있습니다. Skiplist의 효율성은 랜덤화에서 기인합니다. 새로운 자료가 Skiplist에 추가될 때 Skiplist는 무작위 동전 던지기와 같은 기법으로 새로운 자료의 높이[Height]를 결정하곤 합니다( 곧 이 높이에 관해서 논할 겁니다 ). Skiplist의 성능[Performance]은 Expec..
-
[ 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 ] - Space-Efficient Linked List - 1DataStructure 2021. 5. 14. 13:13
Linked List의 깊은 곳에 위치한 Node에 접근하는 시간적인 비용을 차치하고도 Linked List엔 단점이 하나 존재하는데 그것은 공간의 효율성이다. DLList의 각 Node는 해당 Node의 전후를 가리키는 Prev와 Next 두 개의 Reference 혹은 Pointer를 요구한다. DLList의 Node를 보면 prev, next와 실제 정보를 저장하는 x의 총 세 개의 Field로 이루어져 있는데 이들 중에서 실질적으로 정보를 저장하는 Field는 x밖에는 없다. 따라서, Space-Efficient Linked List(以下SEList)는 DLList에 개별의 자료/원소를 저장하기 보다는 몇 개의 자료를 포함하는 Array/Block을 사용하여 공간의 낭비를 줄인다. 조금 더 상세하..
-
[ 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..