불변 자료구조 구현방법 예시

Raymond Yoo·2023년 12월 11일

함수형-프로그래밍-시작해보기

목록 보기

4/15

여기서 소개하는 방법은 불변 자료구조를 구현할때
이런식으로 생각할 수 있다며 예시를 몇 가지 소개하고 있는 것이지
절대적인 정답은 아니다.
나중에 스스로 구현한 자료구조 또는 클래스에
Copy-On-Write 를 적용하고 싶다면 그때 그때
최적의 알고리즘을 선택하면 된다.

단방향 리스트 append

처음에 리스트 a 는 1,2,3,4 로 이루어져 있었다.
여기서 맨 뒤에 5 를 추가한 결과를 알고 싶다고 하자.
변수의 불변성이라는 원리를 적용하려면 아래와 같이 해야한다.
우선 원본 리스트 a 를 복사해서 1,2,3,4 를 가진 리스트 b 를 만든다.
리스트 a 는 건드리지 않고 리스트 b 에 새로운 요소 5 를 추가한다.
그리고 사용자에게 리스트 b 를 반환한다.
그러면 리스트 a 는 처음 그대로 1,2,3,4 가 들어있다
append 결과인 1,2,3,4,5 리스트도 올바르게 결과값으로
얻을 수 있다.

단방향 리스트 prepend

이번에는 맨 뒤 대신에 맨 앞에 0 을 추가한 결과를 알고 싶다고 하자.
처음에 리스트 a 를 복사해서
1,2,3,4 로 이루어진 리스트 b 를 얻는다.
여기서 리스트 a 는 건드리지 않고 리스트 b 에
새로운 요소 0 을 추가한다.
사용자에게는 리스트 b 를 반환한다.
그러면 리스트 a 는 처음 그대로 1,2,3,4 가 들어있고
prepend 결과인 0,1,2,3,4 리스트를 결과값으로 얻을 수 있다.

Copy-On-Write 에서 중요한 점은
리턴값이 처음부터 끝까지
복제한 결과물이어야 하는 법칙은 없다는 것이다.
그림 속 예시는 단방향 리스트이기 때문에
리스트에 대한 참조는 언제나 헤드, 즉 맨 앞 요소부터 시작한다.
그러므로 앞쪽에만 차이가 있고 뒤쪽의 요소들이 동일하다면
두 개의 리스트가 공통되는 요소 목록을 공유할 수 있다.
Copy-On-Write 방식이라고
언제나 메모리를 두배로 사용해야만 하는건 아니다.

단방향 리스트 update

update 는 갱신하려는 인덱스와 갱신 후 담아두려는 값
두 개의 파라미터를 입력받는 함수이다.
이를 구현하면 다음과 같이 된다.
처음에 리스트 a 를 복사해서 1,2,3,4 를 담고있는 리스트 b 를 얻는다.
여기서 리스트 a 는 건드리지 않고
리스트 b 의 1번 인덱스에 있는 요소를 5 로 변경한다.
그리고 나서 리스트 b 를 반환한다.
리스트를 갱신할때 차이가 나는 부분만,
즉 0번 인덱스부터 1번 인덱스까지는 복사해서
리스트 a 와 리스트 b 가 각자 적절한 요소를 참조하도록 구현하지만
공통되는 부분은 공유하므로써 컴퓨팅 리소스를 줄일 수 있다.
그러면 리스트 a 는 처음 그대로 1,2,3,4 가 들어있고
update 결과인 1,5,3,4 리스트도 올바르게 결과값으로 얻을 수 있다.

위의 방식도 나쁘지는 않지만
시간복잡도 라는 기준으로 분석해보면 다음과 같은 결론을 얻는다.
append 는 O(n)
prepend 는 O(1)
update 는 O(n)
런타임에 사용하는 메모리량이라는 기준으로 분석하더라도
최악의 경우에 거의 두 배가 된다.
pop 함수를 구현한다고 생각하면 맨 뒤에서 하나를 제거하기 때문에
원본 리스트 N 개를 그대로 복사해서
새로운 리스트 N-1 개를 만들어야하므로
조금 더 최적화할 방법이 없을까 고민하게 된다.

트리구조를 활용하기