3.1. MyArrayList 메서드 분류하기
상수시간
get 메서드
@Override
public T get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
return array[index];
}get 메서드에 있는 모든 것은 상수 시간이다.
set 메서드
@Override
public T set(int index, T element) {
// get(index);
// T old = array[index];
// 내가 했던 것...
T old = get(index);
array[index] = element;
return old;
}명시적으로 인덱스의 유효성 검증을 하지 않고 get 메서드를 호출했다.
get 메서드는 상수 시간이고 이외에도 set 메서드에 있는 모든 코드는 상수 시간이다. 따라서 set도 상수 시간이다.
equals 메서드
private boolean equals(Object target, Object element) {
if (target == null) {
return element == null;
} else {
return target.equals(element);
}
}이 메서드는 target.equals 메서드를 호출 하는데, 이 메서드가 실행시간은 target 또는 element 크기에 의존하기는 하지만 배열의 크기에는 의존하지 않기에 상수시간이라고 생각한다.
선형
indexOf 메서드
@Override
public int indexOf(Object target) {
for (int i = 0; i < size; i++) {
if (equals(target, array[i])) {
return i;
}
}
return -1;
}
반복문 안에 있는 것은 equals 메서드로 상수시간이다. 그렇다면 반복문이 몇번 실행하는지 생각해봐야한다. 운이 좋다면 대상 객체를 초반에서 찾고 바로 리턴되겠지만 운이 없다면 모든 요소를 테스트해야한다. 평균적으로는 요소 개수의 절반을 테스트한다고 기대한다. 따라서 indexOf 메서드는 선형 시간이다. (대상 요소가 배열의 시작에 있는 거의 일어나지 않을 경우는 제외)
remove 메서드
@Override
public T remove(int index) {
get(index);
T old = get(index);
for (int i = index + 1; i < size; i++) {
array[i - 1] = array[i];
}
array[size - 1] = null;
size--;
return old;
}get메서드를 호출하고 난 다음부터는 반복문이 실행되는데 만약 배열의 가장 마지막 요소를 삭제한다면 반복문이 실행되지 않고 뒤의 코드를 실행할 것이다. 뒤의 코드는 모두 상수시간이므로 상수시간이 된다. 그러나 가장 첫번째 요소를 삭제한다면 나머지 모든 요소에 접근하여 선형이 된다. 따라서 remove 메서드는 선형으로 간주한다.(요소가 배열의 끝에 있거나 끝에서 상수거리에 있음을 아는 특수한 경우는 제외)
3.2. add 메서드 분류하기
@Override
public boolean add(T element) {
if (size == array.length) {
E[] bigger = (E[]) new Object[array.length * 2];
System.arraycopy(array, 0, bigger, 0, array.length);
array = bigger;
}
array[size] = element;
size++;
return true;
}단일 파라미터인 add 메서드는 만약 배열의 빈공간이 남는 경우 상수시간이 되고, 빈공간이 없어 배열을 늘리게 되면, System.arraycopy 메서드를 호출하는데 이것은 실행시간이 배열의 크기에 비례하기 때문에 add 메서드는 선형이다.
분할 상환 분석
이런 경우에는 상수시간일까? 선형일까? 일련의 n개 요소를 추가할 때의 평균 연산 횟수를 고려하여 이 메서드를 분류해야한다. 간단하게 두 요소만큼의 공간이 있는 배열로 시작한다.
- 첫번째 add 실행 - 사용하지 않는 공간에 한 요소 저장
- 두번째 add 실행 - 사용하지 않는 공간에 한 요소 저장
- 세번째 add 실행 - 배열의 크기 변경 후(배열 크기 : 4) 요소 2개 복사, 한 요소 저장
- 네번째 add 실행 - 사용하지 않는 공간에 한 요소 저장
- 다섯번째 add 실행 - 배열의 크기 변경 후(배열 크기 : 8) 요소 4개 복사, 한 요소 저장
- 다음 3번의 add 실행 - 사용하지 않는 공간에 요소 3개 저장
- 다음 add 실행 - 배열의 크기 변경 후 (배열 크기 : 16) 요소 8개 복사, 한 요소 저장
- 다음 7번의 add 실행 - 사용하지 않는 공간에 요소 7개 저장
↓
- 4번의 add 메서드 호출 후 요소 4개 저장, 2번 복사
- 8번의 add 메서드 호출 후 요소 8개 저장, 6번 복사
- 16번의 add 메서드 호출 후 요소 16개 저장, 14번 복사
n번 추가하면 요소 n개 저장하고 n - 2개를 복사해야한다.
즉 총 연산 횟수는 n + n - 2 = 2n - 2이가 된다.
이것은 메서드를 n 번 호출했을 때의 총합으로 이것을 나눈 평균은 2 - 2/n이 된다. n이 커지면 2/n은 작아지므로 n의 가장 큰 지수에만 관심있다는 원칙을 적용했을 때 add 메서드는 상수시간으로 간주된다.
때때로 선형이 되는 알고리즘이 상수시간이라는 것은 이해하기 힘들 수 있지만, 배열의 크기는 항상 2배씩 늘기 때문에 각 요소를 복사하는 횟수가 점점 줄 수 밖에 없다. 고정된 양만큼 곱하는 대신 고정된 양을 배열의 길이에 더한다면 분석 결과는 달라질 것이다.
이처럼 일련의 호출에서 평균시간을 계산하는 알고리즘 분류 방법을 분할 상환 분석이라고 한다. 일련의 호출을 하는 동안 배열을 복사하는 추가 비용이 분산되거나 분할 상환된 것이 핵심이다.
@Override
public void add(int index, T element) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
// add the element to get the resizing
add(element);
// shift the elements
for (int i=size-1; i>index; i--) {
array[i] = array[i-1];
}
// put the new one in the right place
array[index] = element;
}다음 두 파라미터를 받는 add 메서드는 단일 파라미터 메서드인 add(E)를 호출한 후, 새로운 인자를 마지막에 넣은 뒤 다른 요소를 오른쪽으로 이동시키고 올바른 자리에 새로운 요소를 넣는 과정을 거친다.
add(E) 메서드를 호출한 후에 배열 일부에 반복문을 실행하고 요소를 시프트한다.이 반복문은 리스트 끝에 요소를 추가하는 특별한 경우를 제외하면 선형이므로 이 메서드는 선형이다.
3.3. 문제 크기
다음 예제는 removeAll 메서드이다. 반복문을 돌려 각 컬렉션 요소를 remove한 후, 그 리턴값을 flag에 &한다. 따라서 Collection의 한 요소라도 리스트에 없다면 리턴값은 false이다.
@Override
public boolean removeAll(Collection<?> collection) {
boolean flag = true;
for (Object obj: collection) {
flag &= remove(obj);
}
return flag;
}한편, 이 메서드는 반복문을 돌때마다 선형인 remove 메서드를 호출하므로 메서드를 이차로 생각하기 쉬우나 반드시 그렇지는 않다.
이 메서드에서 반복문을 collection 인자의 각 요소를 한번씩 순회한다. collection의 요소가 m개고, 제거할 리스트에 요소가 n개 있다면, O(nm)이다. Collection의 크기가 상수라면 removeAll 메서드는 n에 대해 선형이다. 하지만 collection의 크기가 n에 비례한다면 removeAll 메서드는 이차이다. collection이 항상 100개 이하의 요소를 갖는다면, removeAll는 선형이지만, 일반적으로 collection이 제거할 리스트에 있는 요소의 1%를 포함한다면 removeAll 메서드는 이차이다.
문제 크기에 관해서 이야기하자면, 대상이 어떤 크기인지에 주의해야한다. 이 예는 알고리즘 분석에서 반복문의 개수를 세는 유혹적인 지름길의 함정을 보여준다. 이 예시로 알고리즘 분석에서 반복문의 개수를 세는 유혹적인 지름길을 들 수 있다. 반복문이 한개라면 알고리즘은 보통 선형이고, 반복문이 두개가 중첩되었다면 보통 이차이다. 하지만 각 반복문을 몇번 실행하는 지 생각해야한다. 반복 횟수가 모든 반복문에서 n에 비례한다면 단지 반복문만 세면 되겠지만, 반복 횟수가 항상 n에 비례하지 않는다면 좀더 고민해야한다.
3.4. 연결 자료구조
이 책은 LinkedList 인터페이스의 일부 구현을 제공한다. 자료구조가 연결되었다는 것은 노드라는 객체가 다른 노드에 대한 참조를 포함한 형태로 저장된 것을 의미한다. 각 노드는 다음 노드에 대한 참조를 포함한다. 연결 구조의 다른 예로는 트리와 그래프가 있다. 이때 노드는 둘 이상의 다른 노드에 대한 참조를 포함한다.
다음은 Node 클래스를 간단하게 정의한 것이다.
public class ListNode {
public Object data;
public ListNode next;
public ListNode() {
this.data = null;
this.next = null;
}
public ListNode(Object data) {
this.data = data;
this.next = null;
}
public ListNode(Object data, ListNode next) {
this.data = data;
this.next = next;
}
public String toString() {
return "ListNode(" + data.toString() + ")";
}
}필드로 객체를 저장할 data와 다음 노드의 주소값을 저장할 next가 있고, 다양한 종류의 생성자와 toString() 메서드가 있다. next가 없는 마지막 노드의 next 값은 null이 될 것이다.
연결 리스트의 각 노드들은 다음에 오는 노드의 주소를 저장하는 식으로 서로 연결된다.
3.5.실습 3
Algorithms/ThinkDataStructures/src/main/java com.allendowney.thinkdast.MyLinkedList.java
Algorithms/ThinkDataStructures/src/main/java com.allendowney.thinkdast.MyLinkedListTest.java
MyLinkedList에 TODO 주석이 3개가 있다. 이것을 채워 Test를 성공시켜야한다.
인스턴스 변수와 생성자
public class MyLinkedList<E> implements List<E> {
private int size; // keeps track of the number of elements
private Node head; // reference to the first node
public MyLinkedList() {
head = null;
size = 0;
}size 변수는 MyLinkedList에 있는 요소 개수를 의미하고, head는 첫번째 요소가 될 노드의 주소이다. 요소 개수를 저장할 필요는 없지만, size 변수를 명시적으로 저장하면 상수시간으로 size 메서드를 구현할 수 있다. size 변수가 없었다면 리스트를 순회하면서 요소의 개수를 세는 선형 시간이 필요할 것이다. size 변수를 만들면 요소를 증감시킬 때마다 size 변수를 갱신해야하기 때문에 증감에 관한 메서드는 약간 느려지지만, 증가 차수를 변경하지 않기 때문에(n**3, n**2, n, 1) 그만한 가치가 있다.
생성자는 head를 null로, size를 0으로 초기화하여 빈 리스트를 만든다. 이 클래스는 요소의 타입으로 타입 파라미터 E를 사용한다.
add(E) 메서드
@Override
public boolean add(E element) {
if (head == null) {
head = new Node(element);
} else {
Node node = head;
// loop until the last node
for ( ; node.next != null; node = node.next) {}
node.next = new Node(element);
}
size++;
return true;
}해당 메서드는 리스트의 가장 마지막 요소로 원하는 값을 추가한다. 많은 메서드에서 첫번째 요소에 대한 처리를 특별히 해줘야하는데 여기서도 마찬가지이다. 리스트가 비어있는 경우에는 첫번째 요소인 head에 원하는 값을 넣어야한다. 그게 아니라면 node라는 임시변수를 만들고, 그것을 head에서부터 시작하여 차례차례 각 node의 next에 저장된 다음 요소로 이동하면 next가 비어있는 마지막 요소에 도달하는 데 이때의 next를 원하는 객체의 주소로 바꿔준다. 그러고 나선 마지막으로 size를 하나 올린다.
indexOf(Object) 메서드 (내가 한 것)
@Override
public int indexOf(Object target) {
Node node = head;
for (int i = 0; node != null; i++, node = node.next) {
if (equals(node.data, target))
return i;
}
return -1;
}head를 node로 지정한 후 가장 마지막 요소까지 순회하며 node.data와 target이 일치한지 확인한다. 이번에도 ArrayList와 같이 equals 메서드를 오버로딩하여 어느 한 쪽이 null인 경우를 정상적으로 처리할 수 있게 했다. 반복문을 모두 돌고 나서도 data가 같은 노드를 찾지 못했다면 -1을 리턴한다.
add(int, E) 메서드 (내가 한 것)
@Override
public void add(int index, E element) {
Node newNode = new Node(element);
if (index == 0) {
Node temp = head;
head = newNode;
newNode.next = temp;
} else {
Node node = head;
for (int i = 0; i < index - 1; i++) {
node = node.next;
}
Node temp = node.next;
node.next = newNode;
newNode.next = temp;
}
size++;
}element를 data로 갖는 노드를 먼저 생성한 후, 파라미터로 받은 Index가 0일 경우, head의 값을 기존 첫번째 요소가 아니라 새로 생성한 노드로 변경한다. 파라미터가 0이 아닌 경우에는 반복문을 통해 Index - 1 번째의 요소까지 도달한 후에 해당 node의 next값을 새로 생성한 노드로 변경하고, 새로 생성한 노드의 next값은 index - 1번째 노드의 next에 원래 있던 주소를 저장한다.
remove(int) 메서드 (내가 한 것)
@Override
public E remove(int index) {
Node old;
if (index == 0) {
old = head;
head = old.next;
old.next = null;
} else {
Node node = head;
for (int i = 0; i < index - 1; i++) {
node = node.next;
}
old = node.next;
node.next = old.next;
old.next = null;
}
size--;
return old.data;
}만약 지우고자하는 요소의 인덱스가 0이라면 head를 원래 head.next 주소로 바꿔주고 지워지는 노드의 next는 null로 처리해준다. 인덱스가 0이 아닐 경우에는 node를 index - 1 번째 노드까지 옮긴 다음, node의 next를 다음다음번째 요소로 건너띄어준다. 그리고 지워지는 노드의 next는 null로 처리해준다. 모든 경우에 대하여 size를 줄이고, 지워진 노드의 data를 리턴한다.
subList(int, int) 메서드 개선 (내가 한 것)
@Override
public List<E> subList(int fromIndex, int toIndex) {
if (fromIndex < 0 || toIndex >= size || fromIndex > toIndex) {
throw new IndexOutOfBoundsException();
}
MyLinkedList<E> list = new MyLinkedList<E>();
Node node = head;
for (int i = 0; i < fromIndex; i++) {
node = node.next;
}
list.head = node;
for (int i = fromIndex; i < toIndex; i++) {
node = node.next;
list.size++;
}
node.next = null;
list.size = toIndex - fromIndex + 1;
// int i = 0;
// for (Node node=head; node != null; node = node.next) {
// if (i >= fromIndex && i <= toIndex) {
// list.add(node.data);
// }
// i++;
// }
return list;
}그렇게 성능이 좋아졌을지는 솔직히 잘 모르겠지만 그래도 기존 리스트에서 toIndex를 넘어 끝까지 반복문을 돌릴 필요가 없고, if 문 조건식을 매번 실행할 필요가 없어서 조금은 나아졌다고 생각한다. 일단 fromIndex에 있던 노드를 반복문을 통해 찾고 이것을 새로운 리스트의 head로 저장한 후, fromIndex부터 toIndex까지 다시 반복문을 돌려서 toIndex번째 노드에 도달하면, 이 노드의 next를 null로 변경하고 size를 한번에 계산하여 초기화한다.
모든 테스트를 가까스로 통과했다....ㅋㅋㅋ
3.6. 가비지 컬렉션
앞의 실습에서 MyArrayList 클래스는 필요하면 배열이 늘어나지만 결코 줄어들지는 않는다. 따라서 요소를 삭제하더라도 그에 맞춰 배열이 작아지지 않는다. 배열은 가비지 컬렉션을 하지 않고 그 요소도 리스트 자체가 파괴될 때까지는 가비지 컬렉션의 대상이 아니다.
그에 비해 LInkedList는 요소를 제거하면 리스트 크기가 줄어들고 사용하지 않는 노드는 가비 컬렉션이 될 수 있다. clear 메서드의 구현은 다음과 같다.
@Override
public void clear() {
head = null;
size = 0;
}head 변수를 null로 만들면, 첫번째 Node에 대한 참조 개수가 0이되고, 가비지 컬렉션이 된다. 첫번째 컬렉션이 사라지면 이어서 두번째 Node에 대한 참조 개수가 0이 되고, 이것도 가비지 컬렉션이 된다. 이 과정은 모든 노드가 가비지 컬렉션이 될 때까지 계속된다.
clear 메서드는 어떻게 분류될까? 이 메서드 자체만 보면 두 개의 상수 시간 연산을 포함하기 때문에 상수시간으로 보인다. 그러나 호출할 때는 요소의 개수에 비례하여 가비지 컬렉터가 동작하므로 선형을 간주된다.
이러한 괴리를 성능 버그(performance bug)라고 부른다. 증가 차수가 기대되는 만큼 나오지 않고, 엉뚱한 차수가 나올 수 있기 때문이다. 자바와 같은 언어는 가비지 컬렉션처럼 뒷단에서 많은 일을 수행하고 있으므로 이런 종류의 버그를 찾기가 더욱 힘들다.
'자바 자료구조 & 알고리즘 > 자바로 배우는 핵심 자료구조와 알고리즘' 카테고리의 다른 글
| 자바로 배우는 핵심 자료구조와 알고리즘 : 2장 알고리즘 분석 (0) | 2020.08.25 |
|---|---|
| 자바로 배우는 핵심 자료구조와 알고리즘 : 1장 인터페이스 (0) | 2020.08.21 |