Persistent Data Structure

영속 자료 구조는 예전부터 있어왔던 이야기인데, 막상 퍼시트턴트 데이터 스트럭쳐 어쩌구 이렇게 쓰니 몹시 생소해 보인다. 그리고 생소하다는 건 그만큼 모른다는 것이겠지...

되짚어 볼 겸 간단하게 훑어봤다.

Persistent Data Structure란?

상태를 제거하지 않고 그대로 사용하는 자료구조를 일컫는다. 상태에 변화가 필요할 때에서야 해당 부분에 대해서 새로운 상태를 반환하게 된다.

아래의 예를 들면,

const clone = obj => JSON.parse(JSON.stringify(obj))

const obj = {
  message: 'Hello World',
  inner: { count: 1 }
}
const clonedObj = Object.assign(clone(obj), {
  message: 'Hello'
})

console.log(obj === clonedObj) // false
console.log(obj.inner === clonedObj.inner) // false

단순 clone 사용시에는 모든 객체들을 deep copy하기 때문에, inner은 값이 바뀌지 않았음에도 copy가 수행되어 obj.inner != clonedObj.inner이 된다. 이는 불필요한 연산이다.

영속 자료 구조를 잘 활용한다면 이와 같은 불필요한 연산을 억제할 수 있다.

클로저

영속 자료구조는 클로저 언어와 밀접한 연관이 있는데, 먼저 클로저 언어의 특성에 대해서 알아볼 필요가 있다. 클로저는 강한 함수형 프로그래밍 언어 중 하나로서, 이러한 언어들은 보통 값의 불변성(immutable)을 동반한다. 더 많은 내용이 알고 싶으면 여기를 참조...

그렇기 때문에 값을 변경한다면 지속적으로 새 변수를 선언해야 하는데, 이는 컴퓨터 입장에서 몹시 지저분한 일 중 하나일 것이다. 특히나 그 변수가 크고 무거울수록!

하지만 영속 자료 구조를 이용한다면 꼭 그렇지만도 않을 것이다. 기존 자료 구조를 그대로 쓰고 변한 값만 바꿔서 집어넣으면 되기 때문이고, 심지어 내부적인 최적화까지 더해지면 기존의 명령형 프로그래밍 언어와 다를 바가 없을 것이다.

예를 든다면,

let abc = {'a': 0, 'b': 1, 'c': 2};
let abc2 = Object.assign({'a': 1}, abc);
console.log(abc2['a']);

위 작업은 실제로 아래의 작업과 같이 치환될 것이고,

var abc = {'a': 0, 'b': 1, 'c': 2};
var abc2 = abc;        // shallow copy
abc2['a'] = 0;
console.log(abc2['a']);

필요없는 변수 제거나 pre-eval 등의 내부 최적화를 거치면 아래의 단순한 코드로 변하게 될 것이다.

let a = 0
console.log(a);

이외에도...

• rocess를 fork() 할 때 heap memory 구조를 그대로 복사해 오지만, 그렇다고 메모리 값을 정말로 그대로 복사하는 것이 아니고 필요시에만 (COW; Copy On Write). 이 또한 영속 자료 구조 구현의 한 사례로 볼 수 있겠지...
• 이외에도 python이나 기타 등등의 고수준 언어에서 composite type을 복사할 때도 shallow copy를 수행하여 reference count와 함께 포인터만 취하는 경우가 많다. 이 또한 영속 자료 구조 구현의 일종이겠지?

퍼시스턴트 세그먼트 트리 (Persistent Segment Tree)

이렇게 필요한 값들만 갱신하는 알고리즘을 응용한 알고리즘이 있는데, Persistent Segment Tree 알고리즘이다.

기본적으로 Segment Tree 알고리즘에 기반을 두고 있기 때문에, 해당 알고리즘 및 관련 유형들을 먼저 공부해야 한다. #

데이터에 업데이트가 발생 시 Segment Tree를 새로 만들지 않고 필요한 부분만 지속적으로 변경하도록 하여, 제한된 시간 내에 문제를 해결할 수 있다. 즉 Segment Tree based 알고리즘에 지속적으로 수정/조회 쿼리가 들어오는 경우에 고려될 수 있는 알고리즘이다.

자세한 건 퍼시스턴트 세그먼트 트리 알고리즘 설명과 BOJ 11012번 문제 참조.

출처

• 영속 자료 구조(Persistent Data Structures)
• 클로저라는 훌륭한 도구와 영속 자료 구조
• 퍼시스턴트 세그먼트 트리