[알고리즘] 얕은 복사(shallow copy) vs 깊은 복사(deep copy)
2018. 5. 14. 13:36ㆍ공부 자료/알고리즘
얕은 복사(shallow copy) vs 깊은 복사(deep copy)
객체의 복사는 얕은 복사와 깊은 복사로 나눠집니다. 평소에도 잘 알고 있고, 언제 써야하는지도 알고 있는 사람들도, 실제로 코드로 구현이 어떻게 되어있는지는 잘 모를 수 있습니다. ( 사실 몰라도 된다. 라이브러리에 나와있는데 굳이.. ) 프로그램을 만들면서 deep copy가 얼마나 shallow copy에 비해 느린지 궁금하게 되었고, 진행하면서 코드도 어떻게 만들어야 할지 생각해보는 시간을 가져보았습니다.
1. 객체 복사
주소값을 복사 해 간 경우로, 그저 변수명만 다르게 되어있고 같은 곳을 참조하는 방식을 객체 복사
예시 )
a = new Tree([2, 5, 20, 1, 7]);
b = a;
2. 얕은 복사( Shallow Copy )
따로 객체를 생성하여 복사하지만, 그 안에 들어가는 객체는 객체 복사로 진행되는 것을 의미합니다. 자바나 C++에서는 객체복사와 얕은 복사를 혼용해서 쓰곤 하는데, 이렇게 객체 복사와 얕은 복사를 따로 나누는 것이 맞다고 봅니다.
3. 깊은 복사( Deep Copy )
객체 내의 모든 객체를 따로 복사하여 진행함. 보통 라이브러리에 구현이 되어있다. 재귀적으로 copy() 함수를 만드는 방식으로 실제로 구현함. 자바에서 특히 이해하기 쉽게 구현 가능한데 clonable interface를 상속받는 방식으로 진행된다. python에서는 그런거 없이 copy.deepcopy() 메소드로 모두 한번에 해결 가능합니다. 다만 deepcopy 구현에 있어서는 Java로 진행하는 편이 더 이해하기 쉬울 수 있는데, 이는 다음과 같이 진행됩니다.
public class Obje implements Cloneable {
ArrayList mem1;
int mem2, mem3;
String mem4;
// 다음의 pre-define된 method를 작성하면 된다. super가 clone을 지원하지 않을 경우를 대비해서 exception도 잘 체크한다.
public Obje clone() throws CloneNotSupportedException {
Obje o = (Obje)super.clone();
o.mem1 = (ArrayList) this.mem1.clone();
o.mem2 = this.mem2;
o.mem3 = this.mem3;
o.mem4 = (String) this.mem4.clone();
return o;
}
}
N개의 맴버 변수를 가질 때, clone의 시간 복잡도는 단순히 O(N)으로 표현 불가능 할 것인데, 각각의 맴버 변수가 또 clone을 재귀적으로 실행 할 수 있기 때문입니다. Copy 주제에 시간복잡도가 있다는게 웃기긴 한데.. 계산하는 방법이 따로 있는지 아시는 분은 답변으로 달아주시면 고맙겠습니다.
4. 소스로 확인
import copy
a = [2, 3, 4, [2, 5, 10]]
b = a
c = copy.copy(a)
d = copy.deepcopy(a)
print("a : " + str(a) + " b : " + str(b) + " c : " + str(c) + " d : " + str(d))
a.append([2,3])
a[3].append(4)
a[0] = 7
print("a : " + str(a) + " b : " + str(b) + " c : " + str(c) + " d : " + str(d))
b[0] = 5
print("a : " + str(a) + " b : " + str(b) + " c : " + str(c) + " d : " + str(d))
c[0] = 20
c[3].append(5)
print("a : " + str(a) + " b : " + str(b) + " c : " + str(c) + " d : " + str(d))
d[0] = 21
d[3].append(20)
print("a : " + str(a) + " b : " + str(b) + " c : " + str(c) + " d : " + str(d))- 결과
a : [2, 3, 4, [2, 5, 10]]
b : [2, 3, 4, [2, 5, 10]]
c : [2, 3, 4, [2, 5, 10]]
d : [2, 3, 4, [2, 5, 10]]
a : [7, 3, 4, [2, 5, 10, 4], [2, 3]] # a, b는 변경이 동일하게 진행된다.
b : [7, 3, 4, [2, 5, 10, 4], [2, 3]]
c : [2, 3, 4, [2, 5, 10, 4]]
d : [2, 3, 4, [2, 5, 10]]
a : [5, 3, 4, [2, 5, 10, 4], [2, 3]] # a, b는 변경이 동일하게 진행된다.
b : [5, 3, 4, [2, 5, 10, 4], [2, 3]]
c : [2, 3, 4, [2, 5, 10, 4]]
d : [2, 3, 4, [2, 5, 10]] # d는 변경 사항 없음.
a : [5, 3, 4, [2, 5, 10, 4, 5], [2, 3]]
b : [5, 3, 4, [2, 5, 10, 4, 5], [2, 3]]
c : [20, 3, 4, [2, 5, 10, 4, 5]] # c 내부의 객체 변경만이 원래의 객체에 영향이 간다. 나머진 영향이 없다.
d : [2, 3, 4, [2, 5, 10]]
a : [5, 3, 4, [2, 5, 10, 4, 5], [2, 3]]
b : [5, 3, 4, [2, 5, 10, 4, 5], [2, 3]]
c : [20, 3, 4, [2, 5, 10, 4, 5]]
d : [21, 3, 4, [2, 5, 10, 20]] # d는 아예 동떨어진 객체이다.
5. deep copy는 shallow copy에 비해서 얼마나 느릴까?
필자의 컴퓨터는 i3 7세대 CPU를 사용함을 유의하고 진행해봅시다. ( 좋은 컴퓨터는 아니다 ㅠ.. )
import copy
import time
doTime = 100000
startTime = time.time()
x = range(0, 10)
for _ in range(0, doTime):
y = copy.copy(x)
endTime = time.time()
print("Shallow Copy : " + str(endTime - startTime) + " sec")
startTime = time.time()
x = range(0, 10)
for _ in range(0, doTime):
y = copy.deepcopy(x)
endTime = time.time()
print("Deep Copy : " + str(endTime - startTime) + " sec")
- 결과
doTime = 10000
Shallow Copy : 0.00423407554626 sec
Deep Copy : 0.074471950531 sec
doTime = 50000
Shallow Copy : 0.0215489864349 sec
Deep Copy : 0.371958971024 sec
doTime = 100000
Shallow Copy : 0.0784220695496 sec
Deep Copy : 0.745931148529 sec
shallow copy는 5배, 10배 늘어난다고 딱 딱 늘어나는 것 같진 않습니다. 그에 비해 deep copy는 딱 딱 맞게 늘어나는 것 같습니다. 빠르기는 대충 20배 ~ 10배 정도 차이가 나는데, doTime이 커지는 것과 실행 시간은 크게 관계가 없는 것 같습니다. ( 아예 없는 건 아니고, 유의미한 변화가 있는것도 아니라 애매하게 관련 있다고만 표현 가능할 듯 싶습니다. )
doTime = 10000 && x = range(0, 100)
Shallow Copy : 0.00627708435059 sec
Deep Copy : 0.076199054718 sec
doTime = 50000 && x = range(0, 100)
Shallow Copy : 0.0286030769348 sec
Deep Copy : 0.367890119553 sec
doTime = 100000 && x = range(0, 100)
Shallow Copy : 0.0572488307953 sec
Deep Copy : 0.767907857895 sec
< 개념 >
< 구현 >
'공부 자료 > 알고리즘' 카테고리의 다른 글
| [ 알고리즘 ] DFS 와 BFS (0) | 2018.08.16 |
|---|---|
| [알고리즘] 최대공약수와 최소공배수 (0) | 2018.07.16 |
| [알고리즘] 순환 Linked List 순환 지점 찾기 (2) | 2018.05.09 |