배열 데이터 유형
Array data type컴퓨터 과학에서 배열 유형은 요소(값 또는 변수)의 집합을 나타내는 데이터 유형으로, 프로그램 실행 중 런타임에 계산할 수 있는 하나 이상의 지수(키 식별)에 의해 각각 선택된다.이러한 컬렉션을 보통 배열 변수, 배열 값 또는 간단히 배열이라고 한다.[1]수학 개념 벡터 및 행렬과 유추하여 지수 1개와 2개의 배열을 각각 벡터형과 매트릭스형이라고 하는 경우가 많다.보다 일반적으로 다차원 배열 유형을 텐서형이라고 할 수 있다.[2]
어레이 유형에 대한 언어 지원에는 특정 내장 어레이 데이터 유형, 프로그래머가 이러한 유형을 정의하고 어레이 변수를 선언하는 데 사용할 수 있는 일부 구문 구조(어레이 유형 생성자) 및 어레이 요소 인덱싱을 위한 특수 표기법이 포함될 수 있다.[1]예를 들어, 파스칼 프로그래밍 언어에서 선언문은type MyTable = array [1..4,1..2] of integer,라는 새 배열 데이터 유형을 정의함MyTable. 선언문var A: MyTable그런 다음 변수를 정의한다.A8개 요소의 집합인 이 유형의 각 요소는 두 개의 지수로 식별되는 정수 변수다.Pascal 프로그램에서는 이러한 요소들을 가리킨다.A[1,1],A[1,2],A[2,1], …,A[4,2]특수 배열 유형은 언어의 표준 라이브러리에 의해 정의되는 경우가 많다.[3]
또한 동적 목록은 동적 배열보다 더 일반적이고 구현하기 쉽다.배열 형식은 주로 Pascal 할당에서와 같이 요소 지수를 런타임에 계산할 수 있기 때문에 레코드 형식과 구별된다. A[I,J] := A[N-I,2*J]. 무엇보다도, 이 기능은 단일 반복문을 통해 배열 변수의 많은 요소들을 임의로 처리할 수 있다.
보다 이론적인 맥락에서, 특히 유형 이론과 추상 알고리즘의 설명에서, "어레이"와 "어레이 유형"이라는 용어는 때때로 추상 배열이라고도 불리는 추상적 데이터 유형(ADT)을 가리키거나 대부분의 언어에서 전형적인 어레이 유형의 기본 연산 및 동작을 가진 수학 모델인 연관 배열을 가리킬 수 있다.s — 기본적으로 런타임에 계산된 지수에 의해 선택되는 요소의 모음입니다.
언어에 따라 배열 유형은 목록과 문자열과 같은 값의 집계를 설명하는 다른 데이터 유형과 중복(또는 식별)될 수 있다.어레이 유형은 어레이 데이터 구조에 의해 구현되는 경우가 많지만, 해시 테이블, 링크된 목록 또는 검색 트리와 같은 다른 수단에 의해 구현되는 경우도 있다.
역사
하인츠 루티샤우저의 프로그래밍 언어 슈퍼플랜(1949~1951)에는 다차원 배열이 포함되어 있었다.그러나 루티샤이저는 자신의 언어를 위한 컴파일러가 어떻게 만들어져야 하는지에 대해 기술했지만, 그것을 실행하지는 않았다.
조립 언어와[4] BCPL과 같은 낮은 수준의 언어는 일반적으로 어레이에 대한 통사적 지원이 없다.
효율적인 연산을 위한 배열구조의 중요성 때문에, FORTRAN(1957), COBOL(1960), 알골 60(1960) 등 초기의 고차원 프로그래밍 언어가 다차원 배열을 지원했다.
추상 배열
배열 데이터 구조는 두 개의 연산을 갖는 추상 데이터 구조(추상 배열)로 수학적으로 모델링할 수 있다.
- get(A, I): 인덱스가 정수 튜플 I인 배열 A의 요소에 저장된 데이터.
- 설정(A, I, V): 해당 요소의 값을 V로 설정하여 결과를 산출하는 어레이.
- get(A, I, V, I) = V
- get(A, I, V, J) = get(A, J)일 경우 get(A, J)
모든 어레이 상태 A, 모든 값 V 및 연산이 정의된 튜플 I, J에 대해.
첫 번째 공리는 각 원소가 변수처럼 작용한다는 것을 의미한다.두 번째 공리는 뚜렷한 지수를 가진 원소가 불연속 변수로 작용하여 한 원소에 값을 저장하는 것이 다른 원소의 값에 영향을 미치지 않는다는 것을 의미한다.
이러한 공리는 유효한 인덱스 튜플 I 집합에 어떤 제약조건도 두지 않으므로 이 추상 모델은 삼각 행렬과 기타 이상한 모양의 배열 등에 사용할 수 있다.
구현
 |
배열 구조와 같은 유형의 변수를 효과적으로 구현하기 위해(포인터 산술에 의해 수행된 인덱싱으로), 많은 언어는 인덱스를 정수 데이터 유형(또는 바이트 및 열거 유형과 같은 정수로 해석될 수 있는 다른 유형)으로 제한하고 모든 요소가 동일한 데이터 유형과 저장 크기를 갖도록 요구한다.또한 대부분의 언어들은 배열 변수의 수명 동안 고정된 정수의 유한한 구간으로 각 지수를 제한한다.일부 컴파일된 언어의 경우, 실제로 인덱스 범위는 컴파일 시간에 알려야 할 수 있다.
반면에 일부 프로그래밍 언어는 부동 소수점 숫자, 문자열, 객체, 참조 등과 같은 임의의 값에 의한 인덱싱을 허용하는 보다 자유로운 배열 유형을 제공한다.그러한 지수 값은 고정 구간은커녕 구간으로 제한될 수 없다.그래서 이러한 언어들은 대개 임의의 새로운 요소들이 언제든지 생성될 수 있도록 한다.이러한 선택은 배열 데이터 구조로서 배열 유형의 구현을 배제한다.즉, 이러한 언어는 보다 일반적인 연관 배열 의미론을 구현하기 위해 배열과 같은 구문을 사용하므로 해시 테이블이나 다른 검색 데이터 구조에 의해 구현되어야 한다.
언어 지원
|
다차원 배열
요소를 지정하는 데 필요한 지수 수를 배열 유형의 치수, 치수 또는 순위라고 한다.(이 명명법은 원소의 수인 선형대수학에서 차원 개념과 충돌한다.[6]따라서 5행과 4열로 이루어진 숫자 배열, 즉 20개의 원소는 계산 컨텍스트에서는 차원 2를 가지고 있다고 하지만 수학에서는 차원 4x5 또는 20을 가진 행렬을 나타낸다.또, 「순위」의 컴퓨터 과학의 의미는 텐서 대수에서의 의미와 유사하지만, 행렬의 순위의 선형 대수 개념과는 다르다.
많은 언어가 1차원 배열만 지원한다.이러한 언어에서, 다차원 배열은 일반적으로 일리프 벡터로 표현되는데, 일리프 벡터는 한 차원 적은 배열의 배열에 대한 1차원 배열이다.특히 2차원 배열은 행에 대한 포인터 벡터로 구현될 것이다.따라서 배열 A의 i행과 j행의 요소는 이중 인덱싱(일반 표기법에서는 A[i][j])을 통해 접근할 수 있다.다차원 배열을 에뮬레이션하는 이 방법은 각 행의 크기가 다를 수 있는 들쭉날쭉한 배열 또는 일반적으로 각 지수의 유효 범위가 선행 지수의 값에 따라 달라지는 들쭉날쭉한 배열의 생성을 가능하게 한다.
다차원 배열의 이러한 표현은 C와 C++ 소프트웨어에서 상당히 보편적이다.단, C와 C++는 컴파일 시간 상수 크기로 선언되는 다차원 배열(예: 다음과 같은 경우)에 선형 인덱싱 공식을 사용한다.int A[10][20]또는int A[m][n], 전통적인 대신에.int **A.[7]
인덱싱 표기법
어레이를 지원하는 대부분의 프로그래밍 언어는 저장 및 선택 작업을 지원하며 인덱싱에 특별한 구문을 가지고 있다.초기 언어에서는 괄호를 사용하였다(예:A(i,j), FORTRAN에서와 같이; 다른 이들은 대괄호(예: 대괄호)를 선택한다.A[i,j]또는A[i][j], Algol 60 및 Pascal에서와 같이 (기능 호출에 괄호를 사용하는 것과 구별하기 위해서)
인덱스 유형
배열 데이터 유형은 대개 배열 구조로 구현된다. 즉, 색인은 정수(또는 전체 순서) 값으로 제한되고, 인덱스 범위는 배열 생성 시간에 고정되며, 다중선 요소 주소 지정이 그것이다.대부분의 "제3세대" 언어에서 그랬으며, 여전히 에이다, C, C++와 같은 대부분의 시스템 프로그래밍 언어의 경우다.그러나 일부 언어에서 배열 데이터 유형은 임의 유형 및 동적 요소 생성의 지수와 함께 연관 배열의 의미론을 갖는다.Awk 및 Lua와 같은 일부 스크립팅 언어와 표준 C++ 라이브러리에서 제공하는 일부 어레이 유형의 경우가 이에 해당한다.
경계 검사
Pascal 및 Modula와 같은 일부 언어에서는 모든 액세스에 대해 경계 검사를 수행하여 인덱스가 유효한 범위를 벗어나면 예외를 발생시키거나 프로그램을 중단한다.컴파일러는 속도를 위해 안전을 위해 이러한 점검을 해제할 수 있다.FORTRAN과 C와 같은 다른 언어들은 프로그래머를 신뢰하고 수표를 수행하지 않는다.좋은 컴파일러는 또한 지표가 가질 수 있는 값의 범위를 결정하기 위해 프로그램을 분석할 수 있으며, 이 분석은 경계 검사 제거로 이어질 수 있다.
인덱스 원점
C와 같은 일부 언어는 0 기반 배열 유형만 제공하며, 이 유형의 최소 유효 값은 0이다.이 선택은 배열 구현과 어드레스 계산에 편리하다.C와 같은 언어를 사용하면 어떤 배열의 내부에 대한 포인터를 정의하여 음의 지수를 수용하는 사이비 배열로 상징적으로 작용할 수 있다.이는 C가 사용할 때 지수를 경계와 대조하여 점검하지 않기 때문에만 작동한다.
다른 언어들은 오직 한 가지 기반 배열 유형만을 제공하며, 여기서 각 색인은 1에서 시작한다; 이것은 수학에서 행렬과 수학 시퀀스에 대한 전통적인 관습이다.Pascal과 Lua와 같은 몇몇 언어는 프로그래머가 최소 법적 지수를 선택하는 n 기반 배열 유형을 지원한다.각 선택의 상대적 장점이 열띤 논쟁의 대상이 되어 왔다.특히0-based for(i=0, i<, 이렇게 5i+=1)(5-0으로 꺾으면서)번, 동등한 것을1-based 반 범위했던 반면에 for(i=1, i<, 6, i+=1)6는 자체 잠재적인 그러한 오류, 일반적으로 length()+1 필요하고1-based 포괄적인 범위(5-1)+1번 for(i=1, i<, =5, i+=1)예제 반복하 보강하려면 색인 또는fencepostoff-by-one errors,[8]을 피할 수 있다..
최고지수
배열 선언에 나타나는 숫자와 배열의 마지막 요소의 색인 사이의 관계도 언어에 따라 다르다.많은 언어(예: C)에서는 배열에 포함된 요소의 수를 지정해야 하는 반면, 다른 언어(예: Pascal 및 Visual Basic)에서는 배열에 포함된 요소의 수를 지정해야 한다.NET) 마지막 요소의 인덱스에 대한 숫자 값을 지정해야 한다.말할 필요도 없이, 이 구분은 루아처럼 지수가 1에서 시작하는 언어에서는 중요하지 않다.
배열 대수
일부 프로그래밍 언어는 특정 데이터 유형에 대해 정의된 연산 및 함수가 해당 유형의 요소 배열로 암시적으로 확장되는 어레이 프로그래밍을 지원한다.따라서 A+B를 작성하여 두 배열 A와 B의 해당 요소를 추가할 수 있다.보통 이들 언어는 요소별 곱셈과 선형대수의 표준 행렬 산출물을 모두 제공하며, 이 중 어느 것이 언어에 따라 다른가 * 연산자로 표현되는가.
어레이 프로그래밍 기능을 제공하는 언어는 이 APL 영역의 혁신 이후 급증했다.이것들은 GAUSS, IDL, Mathematica와 같은 도메인별 언어의 핵심 능력이다.그들은 줄리아와 최근 버전의 포트란과 같은 새로운 언어의 핵심 시설이다.이러한 기능은 다른 범용 프로그래밍 언어(예: Python용 NumPy 라이브러리)를 위한 표준 확장 라이브러리를 통해서도 제공된다.
문자열 유형 및 배열
많은 언어가 내장 문자열 데이터 유형을 제공하며, 해당 유형의 값을 빌드하기 위한 특수 표기법(" 문자열 리터럴")을 사용한다.일부 언어(예: C)에서 문자열은 문자의 배열일 뿐이거나 거의 같은 방식으로 처리된다.Pascal과 같은 다른 언어들은 문자열과 배열을 위해 매우 다른 작업을 제공할 수 있다.
배열 인덱스 범위 쿼리
일부 프로그래밍 언어는 벡터의 크기(요소 수) 또는 보다 일반적으로 배열의 각 인덱스의 범위를 반환하는 연산 기능을 제공한다.C와 C++ 어레이에서는 크기 기능을 지원하지 않기 때문에 프로그래머는 크기를 보유하기 위해 별도의 변수를 선언해야 하는 경우가 많으며, 이를 별도의 파라미터로 절차에 전달해야 한다.
새로 생성된 배열의 요소는 정의되지 않은 값(C와 동일)을 가질 수도 있고, 0과 같은 특정 "기본" 값이나 (Java와 동일) null 포인터 값을 가지도록 정의할 수도 있다.
C++에서 std::vector 객체는 위에서 설명한 성능 특성으로 저장, 선택 및 추가 작업을 지원한다.벡터는 크기에 따라 쿼리할 수 있으며 크기를 조정할 수 있다.중간에 요소를 삽입하는 것과 같은 느린 작업도 지원된다.
슬라이싱
배열 슬라이싱 연산은 배열 형식 도면요소(값 또는 변수)의 요소 중 일부를 취한 다음 다른 배열 형식 도면요소(아마도 다른 지표와 함께)로 조립한다.배열형식을 배열구조로 구현하면 구조물의 도프벡터를 조작하여 유용한 슬라이싱 작업(하위배열 선택, 지수 스와핑, 지수 방향 반전 등)을 매우 효율적으로 수행할 수 있다.가능한 슬라이싱은 구현 세부사항에 따라 달라지는데, 예를 들어, FORTRAN은 행렬 변수 한 컬럼을 자르지만 행은 자르지 않고 벡터로 취급하는 반면, C는 행렬에서 행을 자르지만 열은 자르지 않는다.
한편, 배열 타입을 다른 방법으로 구현할 경우 다른 슬라이싱 작업이 가능하다.
크기 조정
일부 언어는 동적 배열(크기 조정, 확장 또는 확장 가능)을 허용한다. 이러한 배열 변수는 현재 요소의 값을 변경하지 않고 생성 후 언제든지 인덱스 범위가 확장될 수 있다.
1차원 배열의 경우, 이 설비는 운영으로 제공될 수 있다.append(A,x)"는 배열 A의 크기를 1씩 증가시킨 다음 마지막 요소의 값을 x로 설정하는 것이다.다른 배열 유형(Pascal 문자열 등)은 연결 연산자를 제공하며, 이 연산자는 슬라이싱과 함께 사용할 수 있어 그 효과 등을 얻을 수 있다.일부 언어에서, 어레이의 요소에 값을 할당하면 필요한 경우 어레이를 자동으로 확장하여 해당 요소를 포함시킨다.다른 어레이 유형에서는 "A[5:5] = [10,20,30]"에서와 같이 슬라이스를 "A[5]" 요소 앞에 3개의 새로운 요소(10,20,30]를 삽입하는 파이썬의 목록 할당에서와 같이 그에 따라 후속 요소들의 번호가 변경되는" 배열로 대체할 수 있다.크기 조정 가능한 배열은 개념적으로 목록과 유사하며, 두 개념은 일부 언어에서 동의어다.
확장 가능한 어레이는 실제 사용 중인 요소의 수를 기록하는 카운터를 사용하여 고정 크기 어레이로 구현될 수 있다.그append연산: 전체 어레이가 사용될 때까지 카운터를 증가시킬 뿐,append작동이 실패하도록 정의될 수 있다.이는 다음과 같이 고정된 용량을 가진 동적 어레이의 구현이다.string파스칼의 일종또는,append운영은 기본 배열을 더 큰 크기로 다시 배열하고 이전 요소를 새 영역에 복사할 수 있다.
참고 항목
참조
- ^ a b 로버트 W. 세베스타(2001) 프로그래밍 언어의 개념.애디슨 웨슬리제4판 (재), 제5판 (2001) ISBN9780201385960
- ^ "Introduction to Tensors TensorFlow Core". TensorFlow.
- ^ K. Jensen과 Niklaus Wirth, PASCAL 사용 설명서 및 보고서.스프링거.페이퍼백 에디션(2007) 184쪽, ISBN 978-3540069508
- ^ 존 미첼, 프로그래밍 언어의 개념.케임브리지 대학 출판부.
- ^ 루캄, 스즈키(1979) 「파스칼에서의 배열·기록·포인터 운용의 검증」.프로그래밍 언어 및 시스템 1(2), 226–244에 대한 ACM 트랜잭션
- ^ 행렬의 정의를 보다.
- ^ 브라이언 W. 케르니건과 데니스 M.Ritchie(1988), The C 프로그래밍 언어.프렌티스 홀, 81쪽
- ^ 에드거 디크스트라 "번호 매기는 왜 0부터 시작해야 하는가"
외부 링크
 | Wikibooks에는 다음과 같은 주제로 한 책이 있다: 데이터 구조/아람 |
 | 무료 사전인 Wiktionary에서 배열을 찾아보십시오. |
