1. Array (배열)
배열리스트를 살펴보기 전에 가장 먼저 배열에 대해서 짚고 넘어간다. 배열은 같은 타입의 데이터를 연속된 메모리 공간으로 이루어진 정적(크기가 고정된) 자료구조이다. 같은 타입의 변수들을 연속적으로 저장하고 싶을 때 사용할 수 있다. 우리가 만약 int 형 자료 100개를 저장해야한다고 가정해보자. 그러면 코드 내에 변수 100개를 선언하고 할당해야한다. 굉장히 길고 불편한 코드가 될 것이다. 때문에 이러한 문제를 해결하기 위해 우리는 배열이라는 구조를 사용한다.
int a1, a2, a3, a4, ... // 너무 길고 불편함.
int arr[100]; // 깔끔하고 간편함.
배열은 연속된 메모리 공간을 사용한다. 같은 타입의 연속된 공간을 사용하기 때문에 우리는 배열의 원소를 바로 Random Access 하여 꺼낼 수 있다. Random Access는 Index번호를 찍어서 원하는 위치의 데이터에 바로 접근하는 것을 말한다. 예를 들어 크기가 5인 문자형 배열을 선언하면 5Byte가 메모리에 할당된다. 그리고 우리가 array[2]에 접근하면 배열의 시작주소 + 2* sizeof(char) 연산을 수행하여 해당 메모리로 접근할 수 있다. 각 메모리 공간의 간격이 일정(타입이 일정하기에)하기 때문에 Base + Offset(index * size)으로 해당 원소에 바로 접근할 수 있다.
이 때 Base는 배열의 시작 주소를 가리키는 말이고, Offset은 시작번지로 부터 얼마나 떨어져 있는가를 표현할 때 사용하는 말이다. int 타입의 배열 array에 접근할때, 만약 array[4]라고 한다면 배열의 시작주소 + 4 * sizeof(int) 연산을 수행하여 해당 메모리로 접근 할 수 있다. 이 경우, Base는 배열의 시작주소, Offset은 4가 된다. 같은 오프셋이라도 타입에 따라 그 크기가 달라진다.
2. Array(배열)의 장단점
같은 타입의 데이터를 다량으로 저장하기 위한 데이터 구조로 Random Access를 지원하는 배열은 매우 좋은 구조이다. (검색속도가 O(1)로 정말 빠르다) 그러나 이러한 배열도 몇가지 문제를 가지고 있다. 일단 중간에 삽입과 삭제를 하기 위해서는 배열의 사이즈를 조정해야한다. 그러나 배열은 크기가 고정된 정적 구조이다. 때문에 데이터가 가득차면 더 이상 삽입할 수 없다. 이를 해결하기 위해 더욱 사이즈가 큰 새로운 배열을 만들고 그 배열로 모든 데이터를 옮겨 담아야한다. 또한 데이터를 삭제하면 그 부분이 빈공간이 된다. 그러나 리스트의 정의에 의하면 원소와 원소 중간에 빈공간이 존재하면 안되기 때문에 삭제한 원소 뒷부분의 원소들을 모두 1칸씩 앞칸으로 당겨서 옮겨 담아야한다. 이러한 단점이 존재하지만 Random Access가 가능하여 검색속도가 O(1)이라는 것은 매우 큰 장점이기에 많은 개발자들은 여전히 배열로 구현된 리스트를 애용한다.
3. Case Study : Java
자바는 Vector와 ArrayList라는 두가지 배열리스트 구현체를 보유하고 있다. Vector는 Synchronized한 자료구조로서 Multi Thread 환경에서 사용하기에 적합하고, ArrayList는 Unsynchronized한 자료구조로 Single Thread 환경에서 사용하기에 적합하다. 이 두 클래스는 모두 grow(minCapacity : int)라는 메소드를 보유하고 있다. 배열이 가득차면 더 커다란 배열을 생성하고 해당 배열로 모든 원소를 옮겨담는 메소드이다. 또한 두 클래스 모두 삭제시 뒷쪽의 요소를 앞쪽으로 당기는 메커니즘이 구현되어있다.
1) java.util.Vector : 가장 먼저 데이터를 담는 저장공간인 elementData 배열이 존재한다. 이 베열에 모든 데이터가 담기게 된다. 또한 데이터의 수를 세는 elementCount와 배열이 꽉 찼을 때 한번에 증가시킬 용량의 크기은 capacity Increment 변수가 존재한다.
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.StreamCorruptedException;
import java.util.*;
import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
protected Object[] elementData;
protected int elementCount;
protected int capacityIncrement;
private static final long serialVersionUID = -2767605614048989439L;
그 다음 Vector의 생성자이다 initialCapacity와 capacityIncrement를 직접 설정할 수 있다. 만약 설정하지 않으면 초기 사이즈는 10으로 설정되고 increment는 0으로 설정되는데, 나중에 grow시 이 값이 0인지 아닌지 체크해서 만약 0이라면 2배 사이즈로 늘리게끔 구현되어있다.
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: " +
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
public Vector() {
this(10);
}
원소를 추가하는 add 메소드이다. 사이즈를 체크하기 위해 ensureCapacityHelper 메소드를 호출하여 최소 사이즈를 현재 엘리먼트의 갯수 + 1로 설정한다. ensuerCapacityHelper에서는 minCapacity (elementCount+1)이 현재 배열의 사이즈보다 큰지 확인하고, 만약 그렇다면 grow()를 수행하여 더 큰 배열로 옮긴다.
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
사이즈를 늘리는 grow() 메소드이다. 만일 capacity increment가 0보다 큰 값이라면, 사용자가 입력했다는 것이므로 해당 사이즈만큼 사이즈를 키우고, 아니면 oldCapacity를 한번 더 더해 2배 사이즈의 배열을 새로 생성하여 데이터를 옮겨담는다.
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
Arrays.copyOf는 해당 사이즈의 새로운 배열을 생성하고, System.arraycopy 메소드를 호출하여 데이터를 옮겨 담는다. System.arracy는 native 메소드로 C언어로 구현되어 Java 코드로는 내부 확인이 여기까지만 가능하다.
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
이 코드는 C언어로 구현된 native 메소드로 System.arraycopy가 호출되면 아래와 같은 함수가 수행된다. (코드가 너무 길어 중간 코드들은 생략하였다. 여기로 가면 전체 소스코드를 확인할 수 있다) 코드를 보면 아래쪽에서 move32 연산을 수행하여 srcArray를 dstArray로 옮기는 것을 확인할 수 있다.
static void Dalvik_java_lang_System_arraycopy(const u4* args, JValue* pResult)
{
ArrayObject* srcArray = (ArrayObject*) args[0];
int srcPos = args[1];
ArrayObject* dstArray = (ArrayObject*) args[2];
int dstPos = args[3];
int length = args[4];
/* Check for null pointers. */
if (srcArray == NULL) {
dvmThrowNullPointerException("src == null");
RETURN_VOID();
}
if (dstArray == NULL) {
dvmThrowNullPointerException("dst == null");
RETURN_VOID();
}
/*
* ... 중간 생략 ...
*/
move32((u1*)dstArray->contents + dstPos * width,
(const u1*)srcArray->contents + srcPos * width,
copyCount * width);
dvmWriteBarrierArray(dstArray, 0, copyCount);
if (copyCount != length) {
dvmThrowArrayStoreExceptionIncompatibleArrayElement(srcPos + copyCount,
srcObj[copyCount]->clazz, dstClass);
RETURN_VOID();
}
원소를 지우는 메소드이다. 마찬가지로 System.arraycopy 메소드를 이용하여 뒤쪽원소를 모두 한칸 앞으로 당긴다.
public synchronized boolean removeElement(Object obj) {
modCount++;
int i = indexOf(obj);
if (i >= 0) {
removeElementAt(i);
return true;
}
return false;
}
public synchronized void removeElementAt(int index) {
modCount++;
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " +
elementCount);
}
else if (index < 0) {
throw new ArrayIndexOutOfBoundsException(index);
}
int j = elementCount - index - 1;
if (j > 0) {
System.arraycopy(elementData, index + 1, elementData, index, j);
}
elementCount--;
elementData[elementCount] = null; /* to let gc do its work */
}
검색메소드인 get 메소드이다. 배열리스트답게 Random Access로 원소를 검색하여 O(1)의 빠른 속도로 검색이 가능하다.
public E get(int index) {
return elementData(index);
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
2) java.util.ArrayList : 사실 Vector는 ArrayList의 전신이기 때문에 서로 많은 부분이 닮아있다. 여기에서는 Vector와 ArrayList의 차이점만 짚고 넘어간다. 위에서 말한대로 ArrayList는 Unsynchronized하고 grow()를 수행할 때 2배가 아닌 1.5배의 사이즈로 배열을 키운다는 차이점이 있다.
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length; // 이전 용량
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 이전 capacity 에 이전 capacity / 2를 더함
// 즉 이전 용량 * 1.5이 됨.
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 1.5배로 키웠는데도 불구하고
// 최소로 요구하는 용량이 더 크면 작으면 최소 용량으로 맞춤
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 만약 최대로 허용하는 사이즈보다 크면
// 가장 최대사이즈로 사이즈를 설정하고
elementData = Arrays.copyOf(elementData, newCapacity);
// 새로운 배열에 복사함. (새 배열을 생성하는 것임)
}4. Growth Rate에 따른 Insert Time Complexity
배열리스트가 가득 찼을 때, 새로운 배열로 Migration하게 되는데, 이 때 만들어지는 새로운 배열의 크기 대 기존 배열 크기 비율에 따라 insert 연산의 time complexity가 달라진다. 그도 그럴 것이 이 Growth Rate가 작으면 배열이 자주 가득 차기 때문에 자주 Migration해야한다. Migration할 때 반드시 loop이 동반되기 때문에 크기 대 속도 비율을 잘 고려해봐야한다.
- 만약 grow할 때 매번 1칸씩 늘린다고 가정해보자. 그러면, insert할때마다 데이터 개수 n개만큼 loop를 돌아야한다. 때문에, insert연산의 time complexity는 O(n)이 된다.
- 만약 grow할때 매번 배열을 2배씩 늘린다고 가정해보자. 그러면 2의 배수번 insert할때마다 n개만큼 loop를 돌아야한다. 이런 경우 loop의 발생이 매번 발생하지 않기 때문에 n번 시도하여 발생한 시간을 계산하고, 이를 전체 갯수로 나눠서 평균을 구한다 (Amortized하게 분석)
- 만약 1칸짜리 배열로 시작한다고 가정하고, 아래 자세한 예시로 알아보자.
4-1) growth rate = 2.0일때
- index=0에 O를 insert=[O]. (늘리지 않음. 0소모)
- index=1에 O를 insert=[n, O] (늘림, n소모)
- index=2에 O를 insert=[n, n, O, X] (늘림, n소모)
- index=3에 O를 insert=[n, n, n, O] (늘리지 않음, 0소모)
- index=4에 O를 insert=[n, n, n, n, O, X, X, X] (늘림, n소모)
- index=5에 O를 insert=[n, n, n, n, n, O, X, X] (늘리지 않음, 0소모)
- index=6에 O를 insert=[n, n, n, n, n, n, O, X] (늘리지 않음, 0소모)
- index=7에 O를 insert=[n, n, n, n, n, n, n, O] (늘리지 않음, 0소모)
- index=8에 O를 insert=[n, n, n, n, n, n, n, n, O, X, X, X, X, X, X, X] (늘림, n=8소모)
- ...
- time = (0 + n + n + 0) + (n + 0 + 0 + 0) + (n + 0 + 0 + 0 + 0 + 0 + 0 + 0)
- time = 1/2 + 1/4 + 1/8 + ... + 1/n = 1
- 때문에 1번 Insert할때 time complexity는 O(1)이다.
5. Implementation
C로 직접 구현한 배열리스트이다. initialCapacity는 5, 새 배열의 크기 등은 java.util.ArrayList의 포맷을 따라서 1.5배가 되도록 구현하였다. 모든 함수에 도큐먼테이션을 달았으니 자세한 설명은 주석을 확인하면 된다.
#include<stdio.h>
#include<stdlib.h>
#define DEFAULT_SIZE 5
/**
* ArrayList C Implementation
*
* @author Hyunwoong
* @when July 30, 2019
* @homepage github.com/gusdnd852
*/
typedef struct ArrayList {
int *data;
int capacity;
int count;
} ArrayList;
/**
* ArrayList create function
*
* @return new empty ArrayList
*/
ArrayList *create() {
ArrayList *list = (ArrayList *) malloc(sizeof(ArrayList));
if (list == NULL) {
printf("error occurred. can't create obejct");
exit(1);
}
int *data = (int *) malloc(sizeof(int) * DEFAULT_SIZE);
if (data == NULL) {
printf("error occurred. can't create obejct");
exit(1);
}
int i; // initialize array
for (i = 0; i < DEFAULT_SIZE; i++) {
data[i] = 0;
}
list->capacity = DEFAULT_SIZE;
list->count = 0;
list->data = data;
return list;
}
/**
* when list is fulled, we need to resize our list.
* this function will increase list's size to 1.5 times like java
*
* @param list list to resize
*/
void grow(ArrayList *list) {
if (list == NULL) {
printf("NullPointerException Occurred\n");
exit(1);
}
int oldCapacity = list->capacity;
int currentCount = list->count;
int i;
int newCapacity = oldCapacity + (oldCapacity >> 1) + 1;
// grow 1.5 times like java.util.ArrayList<E>
int *newData = (int *) malloc(sizeof(int) * newCapacity);
if (newData == NULL) {
printf("error occurred. can't grow\n");
exit(1);
}
for (i = 0; i < currentCount; i++) {
newData[i] = list->data[i];
}
list->capacity = newCapacity;
free(list->data); // free before assign new data
list->data = newData;
}
/**
* return list's current element count
*
* @param list list to check current size
* @return list's size
*/
int size(ArrayList *list) {
if (list == NULL) {
printf("NullPointerException Occurred\n");
exit(1);
}
return list->count;
}
/**
* return list's current capacity
*
* @param list list to check current capacity
* @return list's capacity
*/
int capacity(ArrayList *list) {
if (list == NULL) {
printf("NullPointerException Occurred\n");
exit(1);
}
return list->capacity;
}
/**
* check whether a list is fulled or not.
*
* @return whether a list is fulled or not
*/
int isFull(ArrayList *list) {
if (list == NULL) {
printf("NullPointerException Occurred\n");
exit(1);
}
if (list->capacity <= list->count) {
return 1;
}
return 0;
}
/**
* check whether a list is empty or not
*
* @param list to check
* @return whether a list is empty(1) or not(0)
*/
int isEmpty(ArrayList *list) {
if (list == NULL) {
printf("NullPointerException Occurred\n");
exit(1);
}
return size(list) == 0 ? 1 : 0;
}
/**
* insert an element to the index that user request
*
* @param list list to insert
* @param elem element to insert
* @param index that user requset
*/
void insert(ArrayList *list, int elem, int index) {
if (list == NULL) {
printf("NullPointerException Occurred\n");
exit(1);
}
if (index > list->count) {
printf("ArrayIndexOutOfBoundException Occurred. count = %d, index = %d\n", list->count, index);
exit(1);
}
if (index < 0) {
printf("NegativeArrayIndexException Occurred index = %d\n", index);
exit(1);
}
if (isFull(list)) {
grow(list);
}
list->count++;
int count = list->count;
int i;
for (i = count - 1; i >= index; i--) {
list->data[i + 1] = list->data[i];
}
list->data[index] = elem;
}
/**
* insert an element at end of the list
*
* @param list list to insert
* @param element to insert
*/
void add(ArrayList *list, int elem) {
if (list == NULL) {
printf("NullPointerException Occurred\n");
exit(1);
}
if (isFull(list)) {
grow(list);
}
insert(list, elem, list->count);
}
/**
* remove data using index.
*
* @param list list to remove
* @param index index to remove
*/
void removeIndex(ArrayList *list, int index) {
if (list == NULL) {
printf("NullPointerException Occurred\n");
exit(1);
}
if (index > list->count) {
printf("ArrayIndexOutOfBoundException Occurred. count = %d, index = %d\n", list->count, index);
exit(1);
}
if (index < 0) {
printf("NegativeArrayIndexException Occurred index = %d\n", index);
exit(1);
}
list->count--;
int count = list->count;
int i;
for (i = index; i <= count; i++) {
list->data[i] = list->data[i + 1];
}
}
/**
* search data using index.
* Returns if the value is valid, otherwise returns NULL
*
* @param list list to search
* @param index index to search
* @return an value located at index that user request
*/
int get(ArrayList *list, int index) {
if (list == NULL) {
printf("NullPointerException Occurred\n");
exit(1);
}
if (index > list->count) {
printf("ArrayIndexOutOfBoundException Occurred. count = %d, index = %d\n", list->count, index);
exit(1);
}
if (index < 0) {
printf("NegativeArrayIndexException Occurred index = %d\n", index);
exit(1);
}
return list->data[index];
}
/**
* print list to console like below
* list = [1, 2, 3]
*
* @param list to print
*/
void printList(ArrayList *list) {
int i;
printf("list = [");
for (i = 0; i < list->count; i++) {
printf("%d", list->data[i]);
if (i != list->count - 1) {
printf(" , ");
}
}
printf("]\n");
}
/**
* free memory all list's attributes
*
* @param list list to free
*/
void freeList(ArrayList *list) {
free(list->data);
list->count = 0;
list->capacity = 0;
free(list);
}
int main() {
ArrayList *list = create();
printf("capacity is %d\n", capacity(list)); // 5
add(list, 1); // [1]
add(list, 2); // [1, 2]
add(list, 3); // [1, 2, 3]
add(list, 4); // [1, 2, 3, 4]
add(list, 5); // [1, 2, 3, 4, 5]
add(list, 6); // [1, 2, 3, 4, 5, 6] => grow
printf("capacity is %d\n", capacity(list)); // 8
add(list, 7); // [1, 2, 3, 4, 5, 6, 7]
add(list, 8); // [1, 2, 3, 4, 5, 6, 7, 8]
add(list, 9); // [1, 2, 3, 4, 5, 6, 7, 8, 9] => grow
printf("capacity is %d\n", capacity(list)); // 13
insert(list, 50, 0); // [50, 1, 2, 3, 4, 5, 6, 7, 8, 9]
insert(list, 52, 2); // [50, 1, 52, 2, 3, 4, 5, 6, 7, 8, 9]
insert(list, 54, 4); // [50, 1, 52, 2, 54, 3, 4, 5, 6, 7, 8, 9]
removeIndex(list, 1); // [50, 52, 2, 54, 3, 4, 5, 6, 7, 8, 9]
removeIndex(list, 2); // [50, 52, 54, 3, 4, 5, 6, 7, 8, 9]
removeIndex(list, 9); // [50, 52, 54, 3, 4, 5, 6, 7, 8]
printf("size is %d\n", size(list)); // size is 9
printf("list[0] is %d\n", get(list, 0)); // list[0] is 50
printf("list[2] is %d\n", get(list, 2)); // list[2] is 54
printf("is list empty ? {0:NO , 1:YES} => %d\n", isEmpty(list));
printList(list); // [50, 52, 54, 3, 4, 5, 6, 7, 8]
freeList(list);
return 0;
}
모든 소스코드는 Github에서 확인할 수 있습니다.
gusdnd852/TIL
Source code collections of my blog 📝. Contribute to gusdnd852/TIL development by creating an account on GitHub.
github.com
'알고리즘' 카테고리의 다른 글
| 스택 (2) - 후위 표기법 계산기 (0) | 2020.04.30 |
|---|---|
| 스택 (1) - 개요 (0) | 2020.04.30 |
| 리스트 (3) - 연결리스트 (Linked List) (0) | 2020.04.28 |
| 리스트 (1) - 개요 (0) | 2020.04.28 |
| 문자열 알고리즘 (5) - 트라이 (Trie) (0) | 2020.03.05 |
| 문자열 알고리즘 (4) - 최장 공통부분 문자열 (Longest Common String) (0) | 2020.03.05 |
| 문자열 알고리즘 (3) - KMP 알고리즘 (5) | 2020.03.04 |