🌚 프로그래밍 언어 - Array

💫 배열 타입

---

동질의(homogeneous) 데이터 원소들의 연속된 데이터 모음

배열의 요소에 대한 접근은 첨자를 이용
첨자에 변수가 있을 경우 실시간 연산이 추가로 요구

대부분의 언어에서 배열이 제공되며, 배열의 모든 요소들은 동일한 타입에 속해야 한다.

@ Python, 동적 배열의 특성을 가진 대상체를 ‘List’라는 이름으로 제공한다.

🫧 설계 고려사항

어떤 타입이 첨자에 대해 적법한가?
첨자 식에 대한 범위가 검사되는가? (C, 검사 안함)
첨자 범위는 언제 바인딩 되는가?
배열 할당은 언제 일어나는가?
배열의 기억 공간이 할당될 때 초기화를 할 수 있는가?
슬라이스 유무와 형태

🫧 배열과 색인

배열의 특정 요소는 배열의 이름과 첨자(subscript) 혹은 색인(index)에 의해 참조
배열이름(첨자/색인 - Subscript/Index) → 특정 원소

원소 참조를 위해 대괄호 []를 사용
첨자는 보통 정수 타입을 사용

첨자의 범위 오류는 프로그램에 자주 나타나는 현상, 범위 검사를 제공하는 것은 언어의 신뢰성을 향상
@ C, 배열 범위 검사를 하지 않음
@ Java, Python : 배열 범위를 넘어서는 경우 실행시간에 오류를 발생

🫧 첨자 바인딩과 배열 유형

• 배열 변수에 대한 첨자 바인딩은 보통 정적이나, 첨자 값 범위는 때때로 동적으로 바인딩
  • 첨자 범위의 하한은 0으로 고정@
• 배열의 종류 (첨자 값 범위에 대한 바인딩, 기억공간 바인딩, 기억공간의 할당 장소에 따른)
  • 정적 배열
  • 고정 스택-동적 배열
  • 스택-동적 배열
  • 고정 힙-동적 배열
  • 힙-동적 배열

동적 : 배열이 특정 상황에 할당됨 (i.e. 선언 포함된 함수가 호출될 때)

1. 정적 배열

int tempA[5] = { 1, 2, 3, 4, 5 };
void main()
{
	static int tempB[5] = { 1, 2, 3, 4, 5 };
}

• 첨자 범위가 정적으로 바인딩 (컴파일 타임에)
• 기억공간 할당이 정적으로 (프로그램이 끝날 때 까지) 이루어진다.
• 동적으로 할당이나 회수가 되지 않으므로 효율이 좋지만, 기억공간이 프로그램의 실행시간 전체에 고정된다.

2. 고정 스택-동적 배열

void main()
{
	int temp[5] = { 1, 2, 3, 4, 5 };
}

첨자 범위가 정적으로 바인딩 되지만, 할당이 실행시간중에 일어난다.
기억공간의 효율성이 좋다.

3. 스택-동적 배열

void main()
{
	int n;
	scanf("%d", &n);

    int temp[n];

    for (int i = 0; i < n; i++)
        temp[i] = i;
}

• 첨자 범위와 기억공간 할당 모두가 실행시간중에 바인딩되는 배열
  • Variable Length Array는 C99, C11에서 지원하나 표준 C에서는 지원하지 않음
• 일단 첨자 범위가 바인딩되고 기억공간이 할당되면 이 바인딩은 변수의 존속 기간에 고정
• 장점: 배열의 크기는 그 배열이 사용되기 전까지 몰라도 되므로 유연성이 좋다
• 단점: 이를 위해 많은 코드를 생성하며, 속도가 느려지고 불안한 코드를 생성할 수 있다.

4. 고정 힙-동적 배열

void main()
{
	int n;
	scanf("%d", &n);
	
	int *temp = NULL;
	
	temp = (int *)malloc(sizeof(int) * n);

	for (int i = 0; i < n; i++)
		temp[i] = i;

	free(temp);
	temp = NULL;
}

public static void main(String[] args)
{
	int[] nums = {0, 1, 2, 3, 4, 5};
	for(int i=0; i < nums.length; i++)
		System.out.println(nums[i]);
}

• 첨자 범위와 기억공간의 바인딩이 기억공간이 할당된 후에 고정됨
• 첨자 범위와 기억공간에 대한 바인딩이 사용자가 요청할 때 발생
• 기억 공간이 스택이 아닌 힙에 할당
• 장점: 유연성
• 단점: 스택보다 느림

5. 힙-동적 배열

nums = [1, 2, 3, 4, 5]

for item in nums:
	print(item)

nums.append(6)
nums.append(7)
nums.append(8)
nums.append(9)
nums.append(10)

for item in nums:
	print(item)

• 첨자 범위와 기억공간의 할당이 동적으로 일어나며 배열의 존속기간에 바뀔수 있음
• 장점: 유연성이 좋음
• 단점: 할당과 회수의 시간이 길다

🫧 배열 초기화

배열이 기억공간에 할당되는 시점에 그 배열을 초기화 할 수 있는 수단을 제공

• 배열의 초기화 허용
  • 가장 좌측 요소의 크기는 생략 가능, 이 경우 컴파일러가 크기를 설정
    • 암묵적 설정이므로 실수로 항목을 빼버릴 수 있음
    • int list[] = {4, 5, 7, 8};
    • char name[] = “freddie”;   // name배열의 크기는?
    • char *names[] = {“Bob”, “Jake”, “Darcie”};

🫧 배열 연산

배열 연산은 배열 단위로 연산을 수행하는 연산
배정, 접합, 비교, 슬라이스 등

• C의 경우 배열 연산을 제공하지 않음 -> 라이브러리를 통해 필요한 기능 사용

• Java, C++, C#은 배열이 객체로 제공되며 메소드로 수행

• Python은 리스트 형태의 요소를 제공하며 이질적인 요소를 포함할 수 있음

  • 배정, 접합(+), 원소 멤버쉽(in), 동일성 비교(is), 동등성 비교(==)

@ APL : 강력한 배열 처리 언어

🫧 배열과 슬라이스

슬라이스는 배열의 어떤 부분 구조(substructure)이다.
Python, Ruby, Perl 등의 언어에서 배열의 슬라이스 연산을 제공

nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

print(nums[0:7])
print(nums[2:])
print(nums[:6])
print(nums[::2])
print(nums[1::2])

🫧 평가

FORTRAN I에서 소개된 후 배열은 거의 모든 언어에 포함 됨
모든 순서 타입을 첨자로 허용하거나, 슬라이스 연산등의 진보가 있었음
특히 최근 연상 배열로 향상된 특징을 제공

💫 연상 배열 - Associative array

---

원소 개수와 동일한 개수의 값(키)들로 인덱싱되는, 순서를 갖지 않는 데이터 원소의 모임
키(key)-값(value) 구조

• 구조와 연상
  • 구현에서 원소들이 해시(hash) 함수로 저장되고 인출됨
• 장점 (vs 배열)
  • 가독성과 작성력을 높인다.
  • (해시 함를 써서) 원소들의 접근 속도가 빠르다.
  • 모든 요소들을 하나씩 처리해야하는 경우 배열이 효율적임
• Python : 기본 데이터, 사전(dictionary)
  • 키(key)는 hashable 해야한다. → immutable한 값이어야 함
  • 키와 값사이는 콜론(:)으로 구분