영속 어레이

컴퓨터 과학에서, 더 정확히 말하면, 영구 배열은 (비영구적) 배열과 유사한 특성을 가진 영구 데이터 구조입니다.즉, 영속 어레이에서 값이 갱신되면 2개의 영속 어레이가 존재합니다.업데이트가 고려되는 1개의 영속 어레이와 업데이트 전 어레이와 동일한 1개의 어레이.

영속 어레이와 어레이의 차이

고정된 수로와 요소 e0,…, en− 1{\displaystyle e_{0},\dots ,e_{n-1}}의 배열은 r)[e0,…, en− 1]{\displaystyle \mathrm{ar}=[e_{0}일 경우 ,e_{n-1},\dots]}데이터 구조, n입니다. 그것은, 배열 함께와 인덱스 0을 나는 <, n{\displaystyle 0\leq i<, n}값 ≤ 것으로 예상된다. e ${$ }}는 $e_{i}$ 빠르게 검색할 수 있습니다.이 작업을 룩업이라고 합니다.또한 어레이 ar, $0\leq i<n$ 0 $0\leq i<n$ i < $0\leq i<n$ \ $displaystyle$ 0 \ $leq$ i $[e_{0},\dots ,e_{i-1},v,e_{i+1},\dots ,e_{n-1}]$ < $n$ } 및 $0\leq i<n$ 새로운 값 v $[e_{0},\dots ,e_{i-1},v,e_{i+1},\dots ,e_{n-1}]$ $[e_{0},\dots ,e_{i-1},v,e_{i+1},\dots ,e_{n-1}]$ $[e_{0},\dots ,e_{i-1},v,e_{i+1},\dots ,e_{n-1}]$ 0 $,$ … , $[e_{0},\dots ,e_{i-1},v,e_{i+1},\dots ,e_{n-1}]$ - $[e_{0},\dots ,e_{i-1},v,e_{i+1},\dots ,e_{n-1}]$ , v $[e_{0},\dots ,e_{i-1},v,e_{i+1},\dots ,e_{n-1}]$ , $[e_{0},\dots ,e_{i-1},v,e_{i+1},\dots ,e_{n-1}]$ + 1, e n - $](\$ displaystyle $[e_0 ,\dots$ , $e_v-1$ , $e_1\dots$ , e_dots )가 주어집니다.이 작업을 업데이트라고 합니다.영속 어레이와 비영속 어레이의 주요 차이점은 비영속 어레이에서는 ar2 생성 중에 어레이 ar가 파괴된다는 것입니다.

예를 들어, 다음의 의사 코드에 대해 생각해 보겠습니다.

array = updated_array = array.update(0, 8) other_array = array.update(1, 3) last_array = updated_array.update(2, 5)

실행 종료 시 어레이 값은 [0, 0, 0], update_array 값은 [8, 0, 0], other_array 값은 [0, 3, 0], last_array 값은 [0, 8, 5]입니다.

2종류의 영속 어레이가 있습니다.영속 어레이는 부분적으로 또는 완전히 영속적일 수 있습니다.완전 영속 어레이는 임의의 횟수 갱신할 수 있지만 부분 영속 어레이는 한 번에 갱신할 수 있다.위의 예에서 어레이가 부분적으로만 영속적인 경우 other_array 작성은 금지되지만 last_array 작성은 여전히 유효합니다.실제로 updated_array는 어레이와는 다른 어레이이며 last_array를 생성하기 전에는 업데이트된 적이 없습니다.

실장

많은 영구 어레이 구현이 존재합니다.이 섹션에서 양의 자연수 n은 항상 영속 배열의 크기입니다.

이하에서는, 3개의 실장에 대해 설명합니다.첫 번째 것이 가장 구현하기 쉽고 마지막 것이 더 효율적입니다.

순수하게 기능하는 데이터 구조 사용

크기 n의 완전 영속적 배열의 가장 간단한 구현은 임의의 영속적 맵을 사용하는 것입니다.이 맵의 엔트리는 0 ~n-1의 숫자입니다.이러한 데이터 구조는 예를 들어 균형 잡힌 트리가 될 수 있습니다.그러나 이러한 데이터 구조에서 요소를 찾는 데는 로그 시간이 걸립니다.어레이의 주요 관심사 중 하나는 작업이 일정한 시간에 실행된다는 것입니다.모든 작업에 일정한 ^[1]시간이 걸리는 데이터 구조를 생성하는 것은 불가능하지만, 다음 작업을 통해 적어도 구조의 마지막 버전에서 룩업을 보다 효율적으로 수행할 수 있습니다.

배열 및 수정 트리 사용

완전 영속 어레이는 어레이와 이른바 베이커 기술을 사용하여 ^[2]구현될 수 있습니다.이 실장은 Jean-Christophe Filliattre에 의해 OCaml 모듈 parray^[3].ml에서 사용됩니다.

이 구현을 정의하려면 몇 가지 다른 정의가 필요합니다.초기 어레이는 다른 어레이의 업데이트에 의해 생성되지 않은 어레이입니다.배열 ar의 자녀는 ar.update(i,v) 형식의 배열이며, ar는 ar.update(i,v)의 부모입니다.배열 ar의 하위는 ar 또는 ar의 하위 중 하나이다.배열 ar의 초기 배열은 ar가 초기인 경우 ar이거나 ar의 부모 배열의 초기 배열입니다. $\mathrm {ar} =init.update(i_{0},v_{0}).\dots .update(i_{m},v_{m})$ , ar의 초기 배열은 r $\mathrm {ar} =init.update(i_{0},v_{0}).\dots .update(i_{m},v_{m})$ $\mathrm {ar} =init.update(i_{0},v_{0}).\dots .update(i_{m},v_{m})$ $\mathrm {ar} =init.update(i_{0},v_{0}).\dots .update(i_{m},v_{m})$ i $\mathrm {ar} =init.update(i_{0},v_{0}).\dots .update(i_{m},v_{m})$ . $\mathrm {ar} =init.update(i_{0},v_{0}).\dots .update(i_{m},v_{m})$ p d $\mathrm {ar} =init.update(i_{0},v_{0}).\dots .update(i_{m},v_{m})$ t $\mathrm {ar} =init.update(i_{0},v_{0}).\dots .update(i_{m},v_{m})$ ( $\mathrm {ar} =init.update(i_{0},v_{0}).\dots .update(i_{m},v_{m})$ , $\mathrm {ar} =init.update(i_{0},v_{0}).\dots .update(i_{m},v_{m})$ 0 $\mathrm {ar} =init.update(i_{0},v_{0}).\dots .update(i_{m},v_{m})$ ) $\mathrm {ar} =init.update(i_{0},v_{0}).\dots .update(i_{m},v_{m})$ . $\mathrm {ar} =init.update(i_{0},v_{0}).\dots .update(i_{m},v_{m})$ $\mathrm {ar} =init.update(i_{0},v_{0}).\dots .update(i_{m},v_{m})$ $\mathrm {ar} =init.update(i_{0},v_{0}).\dots .update(i_{m},v_{m})$ $\mathrm {ar} =init.update(i_{0},v_{0}).\dots .update(i_{m},v_{m})$ t $\mathrm {ar} =init.update(i_{0},v_{0}).\dots .update(i_{m},v_{m})$ ( $\mathrm {ar} =init.update(i_{0},v_{0}).\dots .update(i_{m},v_{m})$ $\mathrm {ar} =init.update(i_{0},v_{0}).\dots .update(i_{m},v_{m})$ , $\mathrm {ar} =init.update(i_{0},v_{0}).\dots .update(i_{m},v_{m})$ ) $\mathrm {ar} =init.update(i_{0},v_{0}).\dots .update(i_{m},v_{m})$ $display$ style \ $mathrm {ar$ } $= init$ . update ( $i _$ 0 , v $_$ 0 ) $\mathrm {ar} =init.update(i_{0},v_{0}).\dots .update(i_{m},v_{m})$ 。 $\syslog .update(i_{m}, v_{m$ ar initial $i_{0},\dots ,i_{m}$ i $i_{0},\dots ,i_{m}$ $v_{0},\dots ,v_{m}$ $i_{0},\dots ,i_{m}$ m { $display$ style $i_{0},$ v $v_{0},\dots ,v_{m}$ { $display$ style $v_0},$ 은 $v_{0},\dots ,v_{m}$ $v_{0},\dots ,v_{m}$ 의 $v_{0},\dots ,v_{m}$ 값 시퀀스입니다 $.$ 따라서 어레이 패밀리는 초기 어레이와 그 모든 하위 어레이를 포함하는 어레이 세트입니다.마지막으로 어레이 패밀리의 트리는 노드가 어레이인 트리로 ar에서 각 자식 ar.update(i, v)까지의 엣지 e를 가진다.

Baker의 기술을 사용한 영속 어레이는 어레이라고 불리는 실제 어레이와 어레이 트리의 쌍으로 구성됩니다.이 트리는 초기 배열이 아닌 임의의 루트를 허용합니다.루트는 트리의 임의 노드로 이동할 수 있습니다.루트를 루트에서 임의의 노드 ar로 변경하면 ar 깊이에 비례하는 시간이 소요됩니다.즉, root과 ar 사이의 거리에 있습니다.마찬가지로 값을 조회하려면 배열과 해당 패밀리의 루트 사이의 거리에 비례하는 시간이 걸립니다.따라서 동일한 배열 ar를 여러 번 조회할 수 있는 경우 검색을 수행하기 전에 ar로 루트를 이동하는 것이 더 효율적입니다.마지막으로 어레이를 업데이트하는 데 걸리는 시간은 일정합니다.

기술적으로 ar1이 ar2보다 루트에 가까운 2개의 인접 어레이 ar1 및 ar2가 주어졌을 때 ar1에서 ar2까지의 엣지는 (i, ar2[i])로 라벨링된다.여기서 ar1과 ar2 사이의 값이 다른 유일한 위치는 i이다.

어레이 ar의 요소 i에 액세스 하는 방법은 다음과 같다.ar가 루트일 경우 ar[i]는 루트[i]와 같습니다.그렇지 않으면 ar를 루트로 향하게 합니다.e의 라벨이 (i,v)일 경우 ar[i]는 v와 같습니다.그렇지 않으면 ar2를 엣지 e의 다른 노드로 합니다.ar[i]는 ar2[i]와 같습니다.동일한 정의를 사용하여 반복적으로 수행되는 ar2[i]의 계산입니다.

ar.update(i,v)의 작성은 새로운 노드 ar2를 트리에 추가하고 ar에서 ar2에 엣지 e를 (i,v)로 라벨 붙이는 것으로 구성됩니다.

마지막으로 다음과 같이 루트를 노드 ar로 이동한다.ar가 이미 루트인 경우 수행할 작업이 없습니다.그렇지 않으면 ar를 떠나는 엣지가 현재 루트, (i,v) 라벨 및 ar2가 e의 다른 쪽 끝을 향하도록 합니다.루트를 ar2로 이동하려면 먼저 루트를 ar2로 이동하고 e의 라벨을 (i, ar2[i])로 변경하고 어레이[i]를 v로 변경합니다.

로그 로그 시간

1989년 Dietz는^[4] 검색과 갱신이 O $O(\log \log(\min(n,m))$ log $O(\log \log(\min(n,m))$ ( $O(\log \log(\min(n,m))$ , m $)\displaystyle$ O $(\log \log (\min (n$ , $m$ ) )\displaystyle O(\min ( n , m )\displaystyle O $($ + $n$ )\displaystyle O( m + $O(m+n)$ )\ $displaystylement$ O ( n )에서 $O(\log \log(\min(n,m))$ 실행할 수 있도록 완전 영속적인 어레이를 실장하였습니다.이 실장은 이른바 셀 프로브 모델에 따라 룩업에 최적입니다.

다만, 이 실장은, 상기의 2개의 실장보다 훨씬 복잡하기 때문에, 이 문서에서는 설명하지 않습니다.

레퍼런스

^ ^a ^b Straka e, Milan (2013). Functional Data Structures and Algorithms. Prague. pp. 87–90.
^ Fillâtre, Jean-Christophe; Conchon, Sylvain (2007). A Persistent Union-find Data Structure (PDF). New York, NY, USA: ACM. pp. 37–46. ISBN 978-1-59593-676-9.
^ Filliâtre, Jean-Christophe. "Persistent-array implementation".
^ Dietz, Paul F. (1989). "Fully persistent arrays". Proceedings of the Algorithms and Data Structures. pp. 67–74. doi:10.1007/3-540-51542-9_8.

.

[Straka-1] Straka e, Milan (2013). Functional Data Structures and Algorithms. Prague. pp. 87–90.

[ML-2] Fillâtre, Jean-Christophe; Conchon, Sylvain (2007). A Persistent Union-find Data Structure (PDF). New York, NY, USA: ACM. pp. 37–46. ISBN 978-1-59593-676-9.

[3] Filliâtre, Jean-Christophe. "Persistent-array implementation".

[Dietz-4] Dietz, Paul F. (1989). "Fully persistent arrays". Proceedings of the Algorithms and Data Structures. pp. 67–74. doi:10.1007/3-540-51542-9_8.

[1]

[2]

[3]

[4]

Search

영속 어레이

네임스페이스

더

목차