Akka Concurrency라는 책에서 persistenet data structures에 대해 간략적으로 다루었지만, 알아두는 것이 좋을거 같아 이렇게 따로 정리해둔다.
함수형 프로그래밍 패러다임의 핵심적인 측면들 중 하나는 순수 함수들을 통해 불변의 값들을 변환하는 것이다. 순수 함수가 (예를 들어 목록에 새로운 노드를 추가함으로써) 데이터 구조의 새로운 변경된 버전을 계산할 때마다, 원래의 것은 수정되지 않은 채로 남아 있어야 하고 이전 참조를 통해 이용 가능해야 한다.
불변 구조를 수용하는 것은 촉진된 다중 스레드 연산들과 같은 다수의 이점들을 갖는다. 변환들은 구조들의 이전 버전을 수정하지 않기 때문에, 다른 스레드들은 구조들이 부주의하게 업데이트될 위험 없이 이들을 사용할 수 있다. 따라서 잠금들 또는 세마포어들과 같은 동시성 동기화 메커니즘들을 사용할 필요가 없다.
반면에 수정이 자료 구조의 이전 버전을 파괴하지 않는다면, 그것은 계산이 메모리가 부족하고 비효율적이라는 생각이 들 수 있다. 사실 전체 구조를 복사하지 않고도 공존하는 새로운 버전을 만드는 것은 종종 가능하다. 우리는 그 개념을 살펴볼 것이다. 우리는 두 가지 잘 알려진 자료 구조의 영구적인 구현(persistent implementations), Persistent data structure 중 일부인 linked list에 대해 정리할 것이다.
Persistent Data Structure의 정의
지금까지 논의한 모든 데이터 구조는 비영구적(non-persistent)이다. Persistent Data Structure는 수정될 때 이전 버전의 자신을 항상 보존하는 데이터 구조이다.
업데이트가 제자리에 있지 않기 때문에 '불변'으로 간주될 수 있다. 모든 버전에 액세스할 수 있지만 최신 버전만 수정할 수 있다면 데이터 구조는 부분적으로 영구적이다. 모든 버전에 액세스하고 수정할 수 있다면 완전 영구적이다. 합류 영구적이란 우리가 두 개 이상의 버전을 병합하여 새로운 버전을 얻을 때이다. 이것은 버전 그래프에 DAG(Directed Acyclic Graph)를 유도한다.
영구성은 단순히 복사만 하면 달성할 수 있지만 대부분의 연산은 DS에 작은 변화만 가져올 것이기 때문에 CPU 및 RAM 사용에서 비효율적이다. 따라서 더 나은 방법은 새 버전과 이전 버전 간의 유사성을 활용하여 구조를 공유하는 것이다.
LinkedList
n과 m을 노드의 수로 하여 연결된 두 개의 목록을 연결하는 문제를 생각해 보자. n>m이라고 하자. 우리는 버전을 유지해야 한다. 즉, 원래 목록을 작성할 수 있어야 한다. 한 가지 방법은 모든 노드의 복사본을 만들고 연결을 수행하는 것이다. 목록의 순회를 위한 O(n + m)와 (n + m – 1)개의 연결을 추가하는 O(1) 각각이다. 다른 방법이자 시공간에서 더 효율적인 방법은 두 목록 중 하나의 목록만 순회하고 새로운 연결은 더 적게 한다. 우리는 m<n을 가정하므로 복사할 노드가 m개인 목록을 선택할 수 있다. 이것은 순회를 위한 O(m)와 각 (m)개의 연결에 대한 O(1)를 의미한다. 그렇지 않았다면 우리는 목록의 원래 형태가 지속되지 않았을 것이다.
위와 같이 앞쪽에 삽입이 된다면 기존의 리스트 데이터는 유지하면서도 새로 업데이트 된 데이터를 최소한의 공간 복잡도로 추가할 수 있다.
노드들 각각은 불변이다. 이것은 단일 노드를 여러 개의 리스트로 참조할 수 있는 능력을 준다. 우리는 원래 리스트에 새로운 head를 추가함으로써 완전히 별개의 리스트 두 개를 만들 수 있는데도 그들은 여전히 tail을 공유할 것이다. 리스트 사이에서 노드를 재사용하는 이 방법을 구조 공유(structural sharing)라고 한다. 하나의 노드는 이전 노드에 대한 정보만 가지고 있을 뿐, 다른 노드가 자신을 가리키는지 모르거나 신경 쓰지 않는다. 응용 프로그램에서 사용되는 일부 참조의 경우에는 리스트의 첫 번째 요소가 될 수도 있고, 다른 참조의 경우에는 리스트의 중간에 있을 수도 있다.
위의 그림에서 A와 B라는 요소가 L1에 추가되어도 다른 언어에서처럼 복사되는 것이 아닌, 기존의 노드와 연결이 된다. 따라서 Persistent Data Structure에서는 효과적으로 값을 저장할 수 있다.
