728x90
반응형
Persistent Data Structures 란 데이터 구조를 변경할 때, 기존 버전을 유지하며 새로운 버전을 생성하는 데이터 구조를 말합니다.
이러한 구조는 데이터를 복사하거나 덮어쓰지 않고, 불변성 을 유지하면서 효율적으로 새로운 상태를 관리할 수 있습니다.
-
불변성 (
Immutability)- 기존 데이터 구조는 변경되지 않고, 새로운 데이터 구조가 생성됩니다.
- 데이터 구조의 이전 버전은 항상 유지됩니다.
-
공유 및 효율성
- 변경되지 않는 부분은 기존 데이터 구조를 재사용합니다.
- 데이터 복사를 최소화하여 메모리 및 성능 효율성을 높입니다.
-
버전(
Version) 관리- 여러 상태를 동시에 관리할 수 있으므로, Undo/Redo 기능 구현이 간단해집니다.
-
함수형 프로그래밍
- 불변성을 선호하는 함수형 프로그래밍에서 자주 사용됩니다.
- 모든 버전을 읽고 수정할 수 있습니다.
- 이전 버전을 읽을 수 있지만, 수정은 가장 최신 버전에서만 가능합니다.
- 기존 버전은 삭제되며, 최신 버전만 유지됩니다.
Persistent Linked List는 노드 변경 시, 기존 리스트를 유지하며 새로운 노드를 생성합니다.
cpp
#include <iostream>
#include <memory>
// 노드 정의
struct Node {
int value;
std::shared_ptr<Node> next;
Node(int value, std::shared_ptr<Node> next = nullptr)
: value(value), next(next) {}
};
// 리스트의 헤드 출력
void printList(const std::shared_ptr<Node>& head) {
std::shared_ptr<Node> current = head;
while (current) {
std::cout << current->value << " -> ";
current = current->next;
}
std::cout << "nullptr\n";
}
// 새로운 노드를 추가하는 함수
std::shared_ptr<Node> addNode(const std::shared_ptr<Node>& head, int value) {
return std::make_shared<Node>(value, head);
}
int main() {
// 초기 리스트 생성
std::shared_ptr<Node> list1 = std::make_shared<Node>(1);
list1 = addNode(list1, 2);
list1 = addNode(list1, 3);
// 새로운 리스트 생성 (list1의 복사본)
std::shared_ptr<Node> list2 = addNode(list1, 4);
// 두 리스트 출력
std::cout << "List 1: ";
printList(list1);
std::cout << "List 2: ";
printList(list2);
return 0;
}
List 1: 3 -> 2 -> 1 -> nullptr
List 2: 4 -> 3 -> 2 -> 1 -> nullptr
설명:
list1을 변경하지 않고,list2는 새로운 노드를 추가한 버전입니다.list1과list2는 서로 다른 리스트이지만, 변경되지 않은 노드를 공유합니다.
Persistent Binary Tree는 노드의 변경이나 추가 시, 필요한 경로의 노드만 복사하여 새로운 버전을 만듭니다.
cpp
#include <iostream>
#include <memory>
// 트리 노드 정의
struct TreeNode {
int value;
std::shared_ptr<TreeNode> left;
std::shared_ptr<TreeNode> right;
TreeNode(int value, std::shared_ptr<TreeNode> left = nullptr, std::shared_ptr<TreeNode> right = nullptr)
: value(value), left(left), right(right) {}
};
// 새로운 노드를 추가하는 함수
std::shared_ptr<TreeNode> addNode(const std::shared_ptr<TreeNode>& root, int value) {
if (!root) {
return std::make_shared<TreeNode>(value);
}
if (value < root->value) {
return std::make_shared<TreeNode>(root->value, addNode(root->left, value), root->right);
} else {
return std::make_shared<TreeNode>(root->value, root->left, addNode(root->right, value));
}
}
// 트리 출력 (중위 순회)
void printTree(const std::shared_ptr<TreeNode>& root) {
if (!root) return;
printTree(root->left);
std::cout << root->value << " ";
printTree(root->right);
}
int main() {
// 초기 트리 생성
std::shared_ptr<TreeNode> tree1 = addNode(nullptr, 10);
tree1 = addNode(tree1, 5);
tree1 = addNode(tree1, 15);
// 새로운 트리 생성 (tree1의 복사본)
std::shared_ptr<TreeNode> tree2 = addNode(tree1, 12);
// 두 트리 출력
std::cout << "Tree 1: ";
printTree(tree1);
std::cout << "\nTree 2: ";
printTree(tree2);
return 0;
}
Tree 1: 5 10 15
Tree 2: 5 10 12 15
설명:
tree1은 변경되지 않고 유지됩니다.tree2는12를 추가한새로운 트리 버전입니다.- 변경되지 않은 노드는 공유됩니다.
- 데이터 안정성
- 데이터의 이전 버전을 항상 보존합니다.
Undo/Redo기능 구현 용이- 이전 상태로의 복원이 간단합니다.
- 불변성으로 인한 동시성 안전
- 멀티쓰레드 환경에서도 안전하게 사용할 수 있습니다.
- 메모리 사용량 증가
- 변경된 노드의 복사가 추가 메모리를 요구합니다.
- 성능 오버헤드
- 공유되지 않는 데이터가 많아지면 복사 비용이 증가할 수 있습니다.
- 복잡성 증가
- 구조 설계 및 구현이 더 복잡할 수 있습니다.
-
Undo/Redo시스템- 텍스트 에디터, 그래픽 편집기에서 사용.
-
버전(
Version) 관리- Git과 같은 분산 버전 관리 시스템.
-
분산 시스템
- 데이터베이스 및 네트워크 시스템에서 데이터 상태 관리.
-
함수형 프로그래밍
Immutable한 데이터 구조를 사용하는 언어 (예:Haskell,Clojure)에서 활용.
Persistent Data Structures는 데이터 불변성과 효율성을 동시에 제공하며, 다양한 시스템에서 데이터의 안정적이고 효율적인 관리에 활용됩니다.
728x90
반응형
'Algorithm' 카테고리의 다른 글
| 모노이드(Monoid)와 함수형 디자인 (0) | 2024.11.19 |
|---|---|
| 캐시 히트와 캐시 미스: 캐시 성능 이해하기 (0) | 2024.11.19 |
| 캐시-친화 알고리즘 Cache-Friendly Algorithms (0) | 2024.11.19 |
| 유클리드 호제법 (1) | 2008.11.28 |
| 문자열(string) 필수 기능 (0) | 2007.09.14 |
