데이터 타입(2) - 배열

 

오늘은 이전 포스팅(데이터 타입)에 이어서 배열 타입에 대해 알아볼게요

배열의 구성요소

배열은 배열의 이름과 인덱스로 나뉘어요

array_name(index)   ->   element

어? 왜 괄호로 접근하냐구요? 옛날 컴퓨터 키보드에는 대괄호 []가 없어서 괄호로 접근했다고해요

근데 이게 함수 호출이랑 너무 헷갈리고 키보드에 대괄호가 들어오면서 오늘날의 접근 방식으로 바뀌었다고합니다~

array_name[index]   ->  element

배열의 종류

Static array(고정 크기 및 고정 위치 배열, Fixed size & Fixed location array)

고정된 메모리 위치에 고정된 크기의 배열을 할당하는 방식이에요.

항상 같은 위치에 같은 크기의 배열을 할당한다면 Load time 에 배열을 할당하는게 가능해져서 수행속도가 매우 빨라집니다.

다만 이 방식으로 구현된 언어는 함수 내에서의 배열도 고정 크기, 고정 위치에 할당되기 때문에 재귀호출시 메모리가 겹치는 문제가 생겨요

중요! Fixed size, location 이기 때문에 실행 시간에 allocate, deallocate 하는 행위를 하지 않습니다.

실행과 동시에 해당 메모리는 할당된 상태로 프로그램 끝까지 사용됩니다.

효율적이나 유연성(재귀 호출이 불가능)이 떨어짐

Fixed stack-dynamic array(고정 크기 및 스택 동적 배열, Fixed size & variable location array)

고정 크기라는 말은 기본적으로 배열의 크기를 명시할 때 변수는 사용하지 못하고, 상수만 쓸 수 있다는 말이에요

int a = 10;
int b[10];  ( O )
int c[a];    ( X )

과거 C언어가 Fixed stack-dynamic array 방식이였지만 지금은 아닙니다.

Stack-dynamic 은 함수 호출 시 함수 스택에 배열이 잡힌다는것입니다.

고정 크기 배열은 컴파일 타임에 최적화가 가능하기 때문에 공간적으로 효율적이라고 합니다.

Stack-dynamic array(가변 크기 및 스택 배열, Varaible size & variable location array)

위에서의 dynamic 은 위치적으로 dynamic 하다는 것이고, 여기서의 dynamic 은 사이즈의 dynamic 을 말해요. (헷갈립니다 ㅠ)

배열 크기를 지정할 때 변수를 사용하는 것이 가능한 것을 말합니다.

즉 Runtime 에 배열 크기를 알게되고 동적으로 크기를 결정하여 할당 받게 되는 것입니다.

당연히 컴파일 타임에는 최적화가 불가능합니다.

가변 길이 배열 시 느린 이유

할당 받는 것도 느리지만 a에 대해 참조할때도 항상 다른 스택 주소에 찾아가야 하므로 느릴 수 밖에 없습니다.

Heap-dynamic array(가변 크기 및 힙 배열, Variable size & variable location array)

가변 크기도 지원하지만 Heap 메모리에 배열을 할당하는 것을 말합니다. C의 malloc, free, C++ 의 new, delete 를 말합니다.

char *ptr = malloc(100);   // char ptr[100]; in stack
free(ptr);

C언어 같은 경우에는 explicit heap-dynamic 으로 malloc 같은 함수를 써야지만 힙에 메모리를 할당하는 방식을 쓰는 반면

implicit heap-dynamic 방식을 쓰는 언어들은 모든 배열 선언을 힙에 할당받습니다.

배열의 초기화

int list[] = {4, 5, 6, 7};

위와 같은 방식으로 배열을 초기화 할 수 있지만 모든 요소를 초기화하는 방법은 없고, for 문을 써야만 합니다.

 

변수의 초기화와 마찬가지로 list 라는 변수가 전역변수라면 프로그램 시작 전에 list 를 초기화한다라고 말할 수 있지만

지역 변수일 경우에는 스택에 메모리를 할당하고 각 요소에 값을 할당하는 연산에 불과합니다.

배열 연산

• 할당(assignment) = 복사(copy)
• 이어붙이기(concatenate)
• 비교(== , equality)
• 덧셈(+, 배열 간 덧셈)
• 행렬곱, 전치, 내적

int a[10];
int *b;

// &b[0] = b
a = &b[0];    // 불가능. 배열의 이름은 lvalue 가 아니다.

배열 참조

a[3]; 과 같이 배열의 요소에 참조하는 연산이 필요한데 이를 어떻게 구현하는지에 대한 논의가 필요합니다.

int a[10];

즉 컴파일러가 위 구문을 만났을 때 심볼 테이블을 어떻게 관리할 것인가?

어셈블러로 어떻게 변환할 것인가? 에 대해 알아보겠습니다.

따라서 배열의 몇 번째 접근하는 것보다는 배열의 포인터를 유지하며 *p++ 하면서 반복문을 돌리는게 더 효율적임을 알 수 있습니다.

 

한 가지 흥미로운 점은 어셈블리 표현을 통해 배열의 인덱스가 왜 0부터 시작하는지 이 부분에서 알 수 있다는 것입니다.

만약 인덱스가 1부터 시작한다면 배열의 요소에 접근할 때

a의 배열 주소 + (k - 1) * 4

와 같이 어셈블리가 변할 것이고, 뺄셈 명령어가 하나 추가되게 됩니다.

명령어 5개에서 6개로 증가했으니 성능이 20% 감소한 것입니다.

 

C언어의 주요한 특성 중 하나인데 배열의 인덱스 유효성 검사를 하지 않는다는 것입니다.

만약 a의 크기가 10인데 k 에 1000이라는 값을 넣는다면 어떻게 될까요?

운영체제(언어 X)가 잘못된 메모리에 접근함을 눈치채고 프로그램을 종료시킬것입니다. 이것이 Segmentation Fault 입니다.

하지만 파스칼 같은 언어에서는 a의 크기가 10이라면 k 가 0과 9 사이의 값인지 검증하는 어셈블리가 추가되고,

여기에 걸리면 언어 자체적인 오류 메세지를 출력합니다. (Segmentation fault X)

그렇게되면 배열 자체에 길이를 표현하는 header로 인해 추가적인 메모리가 사용되고 검증 어셈블리 코드가 추가되니 속도도 느려지지만 안전한 프로그래밍이 가능합니다.

 

■ 요약

인덱스 유효성 검사 할 경우

장점 : 안전하다.

단점 : 메모리 추가사용 + 느림

 

인덱스 유효성 검사 안 할 경우 (C언어 방식)

장점 : 빠르다.

단점 : 안전하지 못하다.

 

다차원 배열의 경우 배열 인덱스 참조가 조금 더 복잡합니다.

int a[10][5];
a[i][j]   // &a[0][0] + i * (5 * 4) + j * 4

3차원, 4차원이 되면 더더욱 복잡해질것입니다.

Compile time Descriptor

심볼테이블의 다른 이름으로

• 타입(array)
• 요소 타입(element type)
• 인덱스 타입(int)
• 시작 인덱스(index lower bound)
• 끝 인덱스(index upper bound)
• 주소(address)

와 같은 정보들을 저장할 수 있습니다. 이는 언어에 따라 다르며 C언어를 기준으로 한 것이 아닙니다.

Runtime Descriptor

 

결론

언어에 따라 배열이 생성되는 크기와 장소가 달라짐

• Static array
• Fixed stack-dynamic
• stack-dynamic
• heap-dynamic

배열 참조에 대한 컴파일러의 동작 방식

어셈블리어로 표현되는 방식에 대해 알게되면서 a[1] 보다는 a++ 이 더 빠름

배열 인덱스가 0부터 시작하는 이유

 

인덱스 유효성 검사 할 경우

장점 : 안전하다.

단점 : 메모리 추가사용 + 느림

 

인덱스 유효성 검사 안 할 경우 (C언어 방식)

장점 : 빠르다.

단점 : 안전하지 못하다.

컴파일러의 배열 표현 방식

• Compile time descriptor (Symbol table)
• Runtime descriptor