영구 데이터 구조 Persistent Data Structures

영구 데이터 구조 Persistent Data Structures

Persistent Data Structures 란 데이터 구조를 변경할 때, 기존 버전을 유지하며 새로운 버전을 생성하는 데이터 구조를 말합니다.

이러한 구조는 데이터를 복사하거나 덮어쓰지 않고, 불변성 을 유지하면서 효율적으로 새로운 상태를 관리할 수 있습니다.

---

1. Persistent Data Structures의 특징

1. 불변성 (Immutability)

   • 기존 데이터 구조는 변경되지 않고, 새로운 데이터 구조가 생성됩니다.
   • 데이터 구조의 이전 버전은 항상 유지됩니다.

2. 공유 및 효율성

   • 변경되지 않는 부분은 기존 데이터 구조를 재사용합니다.
   • 데이터 복사를 최소화하여 메모리 및 성능 효율성을 높입니다.

3. 버전(Version) 관리

   • 여러 상태를 동시에 관리할 수 있으므로, Undo/Redo 기능 구현이 간단해집니다.

4. 함수형 프로그래밍

   • 불변성을 선호하는 함수형 프로그래밍에서 자주 사용됩니다.

---

2. Persistent Data Structures의 예

(1) 완전한 불변 구조 (Fully Persistent)

• 모든 버전을 읽고 수정할 수 있습니다.

(2) 부분 불변 구조 (Partially Persistent)

• 이전 버전을 읽을 수 있지만, 수정은 가장 최신 버전에서만 가능합니다.

(3) 완전 삭제 불변 구조 (Ephemeral)

• 기존 버전은 삭제되며, 최신 버전만 유지됩니다.

---

3. 예제: Persistent Linked List

Persistent Linked List는 노드 변경 시, 기존 리스트를 유지하며 새로운 노드를 생성합니다.

예제 코드 (C++):

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는 서로 다른 리스트이지만, 변경되지 않은 노드를 공유합니다.

---

4. 예제: Persistent Binary Tree

Persistent Binary Tree는 노드의 변경이나 추가 시, 필요한 경로의 노드만 복사하여 새로운 버전을 만듭니다.

예제 코드 (C++):

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를 추가한 새로운 트리 버전입니다.
• 변경되지 않은 노드는 공유됩니다.

---

5. Persistent Data Structures의 장단점

장점

1. 데이터 안정성
   • 데이터의 이전 버전을 항상 보존합니다.
2. Undo/Redo 기능 구현 용이
   • 이전 상태로의 복원이 간단합니다.
3. 불변성으로 인한 동시성 안전
   • 멀티쓰레드 환경에서도 안전하게 사용할 수 있습니다.

단점

1. 메모리 사용량 증가
   • 변경된 노드의 복사가 추가 메모리를 요구합니다.
2. 성능 오버헤드
   • 공유되지 않는 데이터가 많아지면 복사 비용이 증가할 수 있습니다.
3. 복잡성 증가
   • 구조 설계 및 구현이 더 복잡할 수 있습니다.

---

6. 활용 사례

1. Undo/Redo 시스템

   • 텍스트 에디터, 그래픽 편집기에서 사용.

2. 버전(Version) 관리

   • Git과 같은 분산 버전 관리 시스템.

3. 분산 시스템

   • 데이터베이스 및 네트워크 시스템에서 데이터 상태 관리.

4. 함수형 프로그래밍

   • Immutable한 데이터 구조를 사용하는 언어 (예: Haskell, Clojure)에서 활용.

---

Persistent Data Structures는 데이터 불변성과 효율성을 동시에 제공하며, 다양한 시스템에서 데이터의 안정적이고 효율적인 관리에 활용됩니다.

view raw Persistent Data Structures.ko.md hosted with ❤ by GitHub