[기말레포트] 배열의 설계와 구현 - 일차원 배열의 설계, 이차원 배열의 설계

소개글

[기말레포트] 배열의 설계와 구현 - 일차원 배열의 설계, 이차원 배열의 설계에 대한 보고서 자료입니다.

목차

- 들어가며
1. 일차원 배열의 설계
2. 이차원 배열의 설계
3. 소감

본문내용

을 검사하기 때문에 신뢰성이 좋다고 할 수 없다.
⒝. 적응성
배열의 크기가 가변적으로 바꿀 수 있다. 적응성이 매우 높다고 할 수 있다.
⒝. 효율성
배열이 연속된 공간에 있지 않고, 링크로 연결된 상태이므로 Access시 배열을 찾아가는데 시간이 많이 걸려 효율성이 떨어진다.
2. 이차원 배열의 설계
배열의 크기를 정하지 않아도 되는(가변적인) 이차원 배열
이차원 배열의 크기를 런타임시에 정하는 배열을 설계하였습니다.
최대한 적응성을 보장하게 만들려면 어떻게 설계하여야 할까? 생각하면서
구현 해보았습니다.
◈ 가정
⒜. 배열은 heap영역에 저장 된다.
⒝. 배열은 Descriptor를 생성하는데, Descriptor는 컴파일시 메모리에 할당한다.
⒞. A[N][M]일 경우, N만큼의 Descriptor를 heap에 생성한다.
⒟. heap 영역에 배열을 연속적으로 할당하지 않는다.
예4-1)
int X[N][M];
N값과 M값은 런타임시 배정된다.
예4-1)에서 보는 바와 같이 배열의 크기는 런타임시 결정된다.
그림4.1) 배열 X의 Stack에 저장된 Descpirtor
그림4.2) 배열 X[N][M]가 메모리에 할당되는 모습을 보여준다.
그림4.1) 는 컴파일시 배열 X의 전체 descriptor의 모습을 보여준다.
그림4.2) 는 런타임때 배열에서 N과 M이 결정되었을 때, 동적으로 배열이 메모리에 할당되는 것을
볼 수 있다.
배열 X[N][]이라면, N개의 Descriptor가 heap 영역에 할당되는 것을 볼 수 있다.
Descriptor의 Next에 M개의 원소들이 달리는 모습이다.
◈ 평가
⒜. 신뢰성
컴파일 타임에 배열이 stack영역에 할당되는 방법에 비해서,
신뢰성이 낮을 것이다.
⒝. 적응성
배열의 크기가 가변적으로 바꿀 수 있다. 적응성이 매우 높다고 할 수 있다.
하지만 적응성을 높이므로 해서 결국 효율적인 부분에서 성능이 떨어질 수밖에 없다.
⒝. 효율성
배열이 연속된 공간에 있지 않으므로, A[N][M]번째 원소를 찾아가기 위해선, N+M번
링크를 통해서 도달해야 한다.
따라서 실질적인 Random Access가 이루어진다고는 볼 수 없다.
몇 가지 방안으로 효율성을 높일 수는 있지만, 연속되게 데이터를 저장하여 offset으로
원소를 찾아가는 방법을 이 길수는 없다.
원소 사이에 Front Link와 Rear Link를 만들어서 데이터를 처리할 때 왔다 갔다 하게
할 수도 있고, Descriptor에서도 Front Link와 Rear Link를 만들어 앞에서 가까운 원소 인지 뒤에서 가까운 원소인지 계산하여 찾아 간다면 N+M보다는 적은 N+(M/2)번으로
링크를 줄일 수 있다.
배열의 크기를 컴파일시 정하는 이차원 배열
이차원 배열의 크기를 컴파일시 정하는 배열을 설계하였습니다.
효율성을 최대한 높였지만, 대신에 그만큼 적응성이 떨어졌습니다.
◈ 가정
⒜. 배열은 Stack영역에 저장 된다.
⒝. 배열은 Descriptor를 생성하는데, Descriptor는 컴파일시 메모리에 할당한다.
⒞. Stack 영역에 배열을 연속적 할당된다.
⒟. 컴파일시 할당할 수 없는 배열이 있다면 에러를 출력한다.
⒠. 기본적으로 언어는 evaluation rules은 eager evaluation에 따른다.
⒡. 열 우선 배열인지, 행 우선 배열인지는 flag를 통해서 정할 수 있다.
예5-1)
⒞.
char B[10][Sum(a)];
a=input(keyboard);
Sum(int X) { X=X+1; return X; }
⒜.
char A[10][10];
⒝.
char B[10][Sum(a)];
int a=3;
Sum(int X){ X=X+1; return X; }
예5-1) 은 이차원 배열이 크기를 컴파일 타임에 정할 수 있을 때를 설계한 것으로
⒜경우는 이미 배열의 사이즈가 상수로 정해져 있으므로, 쉽게 결정할 수 있다.
하지만, ⒝경우 ⒜경우보다 복잡한 것을 볼 수 있다.
언어는 eager evaluation을 따르고 있으므로, 먼저, Sum(b)의 값을 구하기 위해
b를 매개변수로 하는 Sum(b)를 계산한다.
Sum(b)함수 내에 컴파일타임에서 결과가 계산되면, 배열 B를 메모리에 할당한다.
예5-1) 와 같은 경우 B의 사이즈가 정해져 있지 않으므로, 일단 eager evaluation계산을 한다.
⒝경우는 런타임시 input으로 입력받으므로 배열의 크기를 정할 수 없다.
따라서 배열의 크기를 정할 수 없으므로, Stack영역에 올라가지 못하고,
컴파일러가 에러를 발생시킨다.
그림5.1) 메모리에 예제5-1이 할당된 모습
그림5.1) 는 컴파일시 배열 B가 Stack영역에 할당된 모습을 보여준다.
◈ 평가
⒜. 신뢰성
컴파일 타임에 배열을 stack 영역에 할당하기 위해, 형검사와 에러를 검사 하므로
런타임시에 heap 영역에 배열을 할당하는 것보다 신뢰성이 높다.
⒝. 적응성
배열의 크기가 바뀔 수 없다. 따라서 적응성이 좋지 못하다.
⒝. 효율성
배열이 연속된 공간에 있으므로 Base Address와 Offset을 계산하여 배열에 Random
Access 하게 접근할 수 있다.
효율성은 좋지만, 반대로 신뢰성이 떨어진다.
3. 소감
내가 만일 나만의 언어를 만든다면 어떻게 만들 것인가? 에 대해 많은 생각을
해 볼 수 있는 시간이었습니다.
사실 배열 하나를 디자인 하는데도 효율성과 적응성 두 가지를 모두 잡을 수
없기에 적정한 선을 결정해야 하고, 여러 가지 방법이 있는데, 과연 언어를 모두 설계
해야 한다면 어떤 식으로 해야 할 것인가? 많은 고민을 해보았습니다.
한 학기동안 특정 프로그래밍 언어가 아닌, 프로그래밍 언어의 전반적인 특징과 설계
방법 등을 배웠는데, 어려운 점이 많았습니다.
그럼에도 제가 배웠던 언어에 대입해서, 생각해보고, 다른 언어와의 차이점을 발견하고
어떤 식으로 프로그래밍을 하면 좋을 것인가에 대해 고민을 한 학기동안 했던 거 같습니다.
물론 한 학기동안 힘든 것도 많았지만, 이 모든 것이 제게 도움이 되리라 믿고 있습니다.
수고 많으셨습니다.

키워드

프로그램언어개념,   배열,   배열의 설계,   일차원배열,   이차원배열,   기말프로젝트,   프로그램언어,   배열의 설계와 구현