배열의 인덱스·메모리 배치·길이와 용량을 설명하고 삽입·삭제, 복사와 뷰, 다차원 인덱싱, 누적 합·차분·압축을 실행 예제와 경계 검사로 살펴본다.
개요: 인덱스와 저장 위치를 연결하는 구조
배열(array)은 여러 원소를 인덱스로 구분하여 다루는 자료구조다. 기본적인 연속 배열 모델에서는 같은 크기의 슬롯이 차례로 놓이며 시작 위치와 인덱스로 각 슬롯의 위치를 계산할 수 있다. 연결 리스트처럼 앞 원소의 링크를 따라가야만 다음 위치를 알 수 있는 구조와 차이가 있다.
예를 들어 한 주의 일별 판매량 [8,12,7,15,9,11,6]을 저장하면 인덱스 0을 첫날, 6을 마지막 날로 정할 수 있다. 배열 자체가 날짜 의미를 아는 것은 아니므로 인덱스와 업무 의미의 대응을 코드와 데이터 계약에서 정해야 한다.
언어의 Array라는 이름이 모두 같은 메모리 계약을 뜻하지는 않는다. 고정 길이 원소 배열, 참조를 저장하는 가변 목록, 다차원 수치 배열과 희소 속성을 허용하는 객체는 구분해야 한다. 이 문서는 먼저 연속 슬롯 모델을 설명하고 언어별 차이를 덧붙인다.
예제는 별도 패키지 없이 Python 3.9.6에서 실행했다. Python list를 교육용 저장소로 사용하는 코드가 C나 Rust의 원시 배열 메모리를 직접 구현한 것은 아니다. 주소 수식은 모델 계산이며 실제 포인터를 임의로 읽거나 쓰지 않는다.
주소 계산과 상수 시간 접근의 전제
시작 주소를 B, 슬롯 크기를 w바이트라고 하면 0부터 시작하는 인덱스 i의 슬롯 주소는 B+i·w다. 첫 원소는 이동량 0이고 두 번째 원소는 w만큼 떨어져 있다. 필요한 위치를 계산할 때 앞의 모든 원소를 읽을 필요가 없다는 점이 핵심이다.
B=1000, w=4인 교육용 모델에서 인덱스 0,1,2,3의 위치는 1000,1004,1008,1012다. 이 값은 실제 프로세스 주소가 아니며 정렬·객체 헤더·가상 메모리 같은 구현 요소를 생략한 수식 예다.
고정 크기 슬롯 접근을 O(1)로 분석하는 것은 합리적인 기계 연산 모델에서 인덱스 계산과 한 슬롯 접근을 상수 비용으로 세기 때문이다. 캐시 미스, 페이지 폴트, 원격 저장소 같은 실제 지연이 모든 접근에서 동일하다는 뜻은 아니다.
슬롯에 객체 참조를 저장하면 계산되는 것은 참조 슬롯의 위치다. 참조 대상 객체의 전체 데이터가 배열 안에 연속해서 저장된다고 결론 내릴 수 없다. 큰 값의 복사 비용이나 객체 내부 탐색은 슬롯 접근과 별도로 계산한다.
예제 코드
base, width = 1000, 4
print([base + index * width for index in range(4)])
실행 결과
[1000, 1004, 1008, 1012]길이·용량·마지막 인덱스는 서로 다르다
길이 n은 현재 유효한 원소 수이고 0 기반 인덱스의 유효 범위는 0≤i<n이다. 마지막 유효 인덱스는 n−1이며 빈 배열에는 마지막 원소가 없다. 길이를 그대로 인덱스로 사용하면 한 칸 뒤를 읽게 된다.
가변 배열이나 버퍼에는 용량 C가 따로 있을 수 있다. 용량은 확보한 슬롯 수이며 n≤C다. [A,B,C,None,None]에서 유효 길이가 3이면 뒤의 두 칸은 여유 공간이다. None이 정상 값일 수 있으므로 값만 보고 유효 길이를 추측하지 않는다.
읽기·수정 위치는 0부터 n−1까지지만 삽입 위치는 0부터 n까지 허용하는 계약이 흔하다. n에 삽입하는 것은 현재 마지막 뒤에 붙이는 것이고 n번째 원소를 읽는 것과 다르다. API 경계 검사가 혼동되기 쉬운 지점이다.
용량이 가득 찼을 때는 오류, 확장, 오래된 값 덮기 중 어떤 정책인지 정해야 한다. 원시 배열은 스스로 커지지 않는다. 동적 배열은 새 저장소 확보와 복사 같은 정책을 추가한 자료구조다.
예제 코드
storage = ['A', 'B', 'C', None, None]
size = 3
print(size, len(storage), size - 1)
print(storage[:size])
print(list(range(size + 1)))
실행 결과
3 5 2
['A', 'B', 'C']
[0, 1, 2, 3]반열린 구간 [left,right)의 장점
[left,right)는 left를 포함하고 right를 포함하지 않는 구간이다. 0≤left≤right≤n이면 길이는 right−left이고, left=right인 빈 구간도 자연스럽게 표현한다. 전체 배열은 [0,n)이다.
구간을 [left,middle)과 [middle,right)로 나누면 겹치거나 빠지는 원소 없이 원래 구간을 구성한다. 이분 탐색, 정렬, 슬라이스와 누적 합에서 같은 경계 규칙을 쓰면 off-by-one 오류를 줄일 수 있다.
아래 인덱스 [1,4)는 B,C,D이며 길이는 3이다. [2,2)는 빈 결과다. Python 슬라이스는 범위를 넘어가는 값을 조정하는 등 추가 규칙이 있지만 이 문서의 알고리즘 함수들은 명시한 범위 밖 입력을 오류로 처리한다.
닫힌 구간 [left,right]를 쓰는 API와 연결할 때는 마지막 포함 위치를 one-past-end로 바꾸는 과정이 필요하다. 단순히 변수 이름이 right라고 같은 의미로 간주하지 않는다. 외부 데이터의 범위 정의부터 확인한다.
예제 코드
values = list('ABCDE')
left, right = 1, 4
print(values[left:right], right - left)
print(values[2:2])
print(values[:2] + values[2:] == values)
실행 결과
['B', 'C', 'D'] 3
[]
True범위 검사와 음수 인덱스의 언어 차이
Python 시퀀스의 음수 인덱스는 끝에서부터 세는 의미를 갖는다. a[-1]은 마지막 원소지만 빈 목록에서는 실패한다. Java 배열의 음수 인덱스는 같은 의미가 아니며 오류다. C/C++의 유효 범위 밖 접근을 Python처럼 자동 보정해 주는 동작으로 기대해서는 안 된다.
외부 입력이 -1이면 오류여야 하는 함수에서 Python의 기본 인덱싱을 그대로 쓰면 마지막 원소를 읽는 논리 오류가 생길 수 있다. 언어가 허용하는 범위와 업무 계약의 범위를 구분해 먼저 검사한다.
아래 read_at은 0≤index<len(values)만 허용한다. Python 자체의 -1 접근은 30이지만 이 함수는 -1과 길이 3을 모두 거부한다. 경계를 어떻게 정의했는지 함수 이름과 설명에 드러내면 호출자가 잘못 추측할 가능성을 줄인다.
범위 검사는 정확성 문제이면서 저수준 환경에서는 메모리 안전성과도 연결된다. 이 문서는 의도적인 범위 초과 메모리 접근을 실행하지 않고 안전한 예외를 통해 계약 차이를 확인한다.
예제 코드
def read_at(values, index):
if not 0 <= index < len(values):
raise IndexError('index out of range')
return values[index]
values = [10, 20, 30]
print(values[-1], read_at(values, 1))
for index in [-1, 3]:
try:
read_at(values, index)
except IndexError:
print('rejected', index)
실행 결과
30 20
rejected -1
rejected 3고정 용량 버퍼의 삽입과 삭제 구현
순서를 보존하며 중간에 삽입하려면 뒤쪽 원소를 한 칸씩 오른쪽으로 이동해야 한다. 새 값이 들어갈 칸을 마련한 다음 값을 쓰고 길이를 늘린다. 삭제는 뒤 원소를 왼쪽으로 당기고 길이를 줄인다.
오른쪽 이동은 뒤에서 앞으로 해야 아직 복사하지 않은 원본을 덮지 않는다. 왼쪽 이동은 앞에서 뒤로 진행한다. 겹치는 범위를 다룰 때 이동 방향이 중요한 이유다. 실제 언어·라이브러리는 겹치는 복사에 별도 API나 계약을 둘 수 있다.
FixedBuffer는 capacity개 슬롯을 한 번 확보하고 자동 확장은 하지 않는다. 가득 차면 OverflowError, 잘못된 인덱스면 IndexError를 낸다. 제거한 마지막 유효 슬롯은 None으로 지우지만 None도 정상 값으로 저장할 수 있으므로 size로 유효 범위를 판단한다.
이 구현의 기반은 Python list이며 리스트 자체의 메모리 할당 구현을 재현하지 않는다. 고정 용량 내에서 이동 방향, 길이와 유효 구간을 관리하는 알고리즘을 보여 주기 위한 코드다.
예제 코드
class FixedBuffer:
def __init__(self, capacity):
if capacity < 0:
raise ValueError('negative capacity')
self.storage = [None] * capacity
self.size = 0
def insert(self, index, value):
if not 0 <= index <= self.size:
raise IndexError('invalid insertion index')
if self.size == len(self.storage):
raise OverflowError('buffer full')
for position in range(self.size, index, -1):
self.storage[position] = self.storage[position - 1]
self.storage[index] = value
self.size += 1
def remove(self, index):
if not 0 <= index < self.size:
raise IndexError('invalid removal index')
value = self.storage[index]
for position in range(index, self.size - 1):
self.storage[position] = self.storage[position + 1]
self.size -= 1
self.storage[self.size] = None
return value
def values(self):
return self.storage[:self.size]
buffer = FixedBuffer(5)
for value in ['A', 'C', 'D']:
buffer.insert(buffer.size, value)
buffer.insert(1, 'B')
print(buffer.values())
print(buffer.remove(2), buffer.values())
실행 결과
['A', 'B', 'C', 'D']
C ['A', 'B', 'D']덮어쓰기 버그를 작은 예로 추적하기
[A,B,C,빈칸]에 X를 인덱스 1에 넣으면서 앞에서부터 오른쪽으로 이동하면 B를 인덱스 2로 쓴 뒤 그 B를 다시 인덱스 3으로 복사하게 된다. 원래 C가 덮이기 때문에 결과가 A,X,B,B가 된다.
반대로 뒤에서부터 이동하면 C를 먼저 빈칸으로 옮기고 B를 다음 칸으로 옮긴다. 아직 읽지 않은 원본의 위치를 보호하는 순서다. 값이 전부 같으면 버그를 발견하기 어려우므로 서로 다른 값으로 검사한다.
아래 첫 결과는 일부러 잘못된 구현을 실행해 얻은 값이다. 두 번째는 올바른 역방향 이동이다. 예제의 목적은 실행이 성공했다고 정확한 결과가 보장되는 것이 아니라는 점을 보여 주는 것이다.
삭제·압축·버퍼 안에서 겹치는 복사도 같은 문제를 갖는다. “복사 반복문”이라고 묶어 설명하지 않고 원본과 목적지의 상대 위치, 반복 방향과 수정되지 않아야 할 부분을 확인한다.
예제 코드
wrong = ['A', 'B', 'C', None]
for index in range(1, 3):
wrong[index + 1] = wrong[index]
wrong[1] = 'X'
correct = ['A', 'B', 'C', None]
for index in range(3, 1, -1):
correct[index] = correct[index - 1]
correct[1] = 'X'
print(wrong)
print(correct)
실행 결과
['A', 'X', 'B', 'B']
['A', 'X', 'B', 'C']접근·검색·삽입의 시간 복잡도
고정 크기 슬롯의 임의 인덱스 접근은 O(1)이지만 값이 어디 있는지 찾는 검색은 다른 연산이다. 정렬되지 않은 배열에서 특정 값의 존재를 알아내려면 최악에 모든 원소를 검사하므로 O(n)이다. 인덱스를 이미 안다는 가정과 값을 찾는 문제를 혼동하지 않는다.
길이 n에서 인덱스 i에 순서 보존 삽입을 하면 n−i개 원소를 이동한다. 인덱스 i 삭제는 n−i−1개를 이동한다. 뒤 추가·뒤 삭제와 앞 삽입·앞 삭제의 비용은 다르다. 용량 확장은 별도 비용이다.
정렬된 배열에서는 이분 탐색을 사용할 수 있지만 정렬 상태를 만드는 비용과 변경 때 유지하는 비용이 있다. 검색 O(log n)이라는 설명은 정렬된 입력과 임의 접근을 사용할 수 있다는 조건을 포함해야 한다.
배열의 원소가 큰 객체라면 한 원소 이동을 상수 비용으로 보는 모델이 맞는지도 확인한다. 참조 하나를 옮기는 것과 큰 값 객체를 복사하는 것은 다를 수 있다. 복잡도 표기는 표현과 연산 계약을 함께 밝혀야 의미가 있다.
동적 배열은 확장 정책을 더한 구조다
고정 용량이 부족하면 더 큰 저장소를 확보하고 기존 원소를 옮길 수 있다. 이 동작을 사용자에게 숨기고 가변 길이 API를 제공하는 것이 동적 배열의 핵심이다. 논리 길이와 확보한 용량을 분리한다.
매번 정확히 한 칸씩 늘려 전체를 복사하면 연속 n번 추가의 이동 합이 O(n²)이 될 수 있다. 용량을 일정 비율로 늘리는 정책은 연속 추가의 분할 상환 비용을 줄인다. 그러나 특정 한 번의 추가에서는 큰 재할당·복사가 일어날 수 있다.
재할당 이후 이전 저장소를 가리키던 포인터·뷰·반복자의 유효성은 언어와 API 계약에 따른다. 값이 그대로라는 사실과 저장 위치가 그대로라는 사실은 다르다. 외부 함수가 메모리 주소를 보관하는 경우에는 특히 중요하다.
이 문서의 FixedBuffer는 확장하지 않으며, 확장 정책과 자동 축소의 자세한 분석은 동적 배열 문서의 주제다. 배열의 기본 주소 모델과 동적 컨테이너의 수명·용량 정책을 분리해 이해하면 다른 언어의 컬렉션을 비교하기 쉽다.
참조 배열과 값 배열의 차이
슬롯이 실제 숫자 값을 담는지, 다른 객체의 참조를 담는지에 따라 메모리와 복사 의미가 달라진다. 참조 배열에서는 슬롯들을 복사해도 참조 대상 객체는 공유될 수 있다. 바깥 배열이 새 객체라는 사실만으로 내부 값까지 독립적이라고 할 수 없다.
아래 outer[:]는 바깥 Python 목록만 복사한다. copy[0].append(9)는 공유된 안쪽 목록을 바꾸므로 outer에서도 보인다. 반면 copy[1]=['new']는 복사본의 슬롯 참조를 교체하므로 원본의 두 번째 슬롯은 그대로다.
이 차이는 배열을 함수에 전달하거나 캐시에 저장할 때 자주 나타난다. “복사한다”는 표현 대신 바깥 컨테이너 복사, 원소 참조 공유, 값의 깊은 복사 중 어느 수준인지 설명하는 것이 정확하다.
깊은 복사도 모든 자료에 자동으로 적합한 해법은 아니다. 파일·연결·공유 메모리 같은 자원의 복제 의미와 비용을 따로 정해야 한다. 필요한 독립성의 범위를 먼저 결정한다.
예제 코드
outer = [[1], [2]]
copy = outer[:]
copy[0].append(9)
copy[1] = ['new']
print(outer)
print(copy)
print(outer[0] is copy[0], outer[1] is copy[1])
실행 결과
[[1, 9], [2]]
[[1, 9], ['new']]
True False다차원 배열 생성에서 행 공유 실수
Python에서 [[0]*3]*2는 독립된 행 두 개를 만드는 것이 아니라 같은 안쪽 목록 참조를 두 번 반복한다. 한 행의 값을 바꾸면 다른 행에서도 같은 변경이 보인다. 2차원 표를 만들 때 흔한 실수다.
[[0]*3 for _ in range(2)]는 반복마다 새 행 목록을 만들어 두 행을 분리한다. 단, 각 셀에 가변 객체를 반복해서 넣는 경우에는 셀 수준의 공유도 다시 확인해야 한다. 배열의 중첩 단계마다 복제와 공유의 의미를 살핀다.
아래 잘못 만든 표는 첫 행 첫 칸만 수정했는데 두 행 모두 7이 된다. 올바른 표에서는 첫 행만 바뀐다. 출력 모양만 같은 초기 상태에서는 공유 관계가 드러나지 않으므로 변경을 포함한 검사가 필요하다.
Java의 배열의 배열이나 다른 언어의 참조 컨테이너도 각 하위 배열의 수명과 공유를 고려해야 한다. 2차원 인덱싱 문법이 있다는 이유로 하나의 연속된 직사각형 메모리라고 단정하지 않는다.
예제 코드
wrong = [[0] * 3] * 2
right = [[0] * 3 for _ in range(2)]
wrong[0][0] = 7
right[0][0] = 7
print(wrong)
print(right)
print(wrong[0] is wrong[1], right[0] is right[1])
실행 결과
[[7, 0, 0], [7, 0, 0]]
[[7, 0, 0], [0, 0, 0]]
True False행 우선 저장과 평탄화 인덱스
행 수 R, 열 수 C인 직사각형을 행 우선으로 한 배열에 저장하면 (row,column)의 선형 인덱스는 row·C+column이다. 각 행 앞에 row·C개 원소가 있고 그 행 안에서 column칸 이동하기 때문이다.
2행 3열 [A,B,C;D,E,F]를 평탄화하면 [A,B,C,D,E,F]다. (1,2)는 1·3+2=5라서 F다. 반대로 선형 인덱스 i에서 divmod(i,C)로 행과 열을 얻을 수 있다. C가 0인 경우에는 이 역변환을 그대로 적용할 수 없다.
row와 column 각각의 범위를 검사해야 한다. column=C를 허용하면 평탄화 결과가 다음 행의 첫 칸처럼 보여 전체 배열 범위 안에 있어도 잘못된 셀을 읽을 수 있다. 최종 선형 인덱스 하나만 검사하면 놓칠 수 있는 논리 오류다.
열 우선 저장에서는 column·R+row라는 다른 대응이 된다. 외부 파일이나 수치 라이브러리와 연결할 때 형태만 아니라 저장 순서와 stride를 확인해야 한다.
예제 코드
rows, columns = 2, 3
flat = list('ABCDEF')
def at(row, column):
if not 0 <= row < rows or not 0 <= column < columns:
raise IndexError('invalid coordinates')
return flat[row * columns + column]
print(at(1, 2))
print([divmod(index, columns) for index in range(len(flat))])
try:
at(0, 3)
except IndexError:
print('column rejected')
실행 결과
F
[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2)]
column rejectedstride와 전치: 모양을 바꾸는 것과 값을 옮기는 것
stride는 한 축의 인덱스를 한 칸 늘릴 때 저장소에서 얼마나 이동하는지를 나타낸다. 행 우선 2×3 배열에서 원소 단위 stride는 행 방향 3, 열 방향 1이다. 바이트 단위라면 여기에 원소 크기를 곱한다.
같은 저장소를 전치된 3×2 모양으로 보면 새 좌표 (r,c)의 위치는 c·3+r이다. 원본 값 자체를 옮기지 않고 좌표 해석을 바꿀 수 있다. 다만 그 결과가 새 행 방향으로 연속한 데이터라는 뜻은 아니다.
아래 transpose_view 함수는 새 좌표를 원본 인덱스로 변환해 읽는다. 함수 자체는 값을 복사하지 않지만 출력용 중첩 목록을 만드는 부분은 실제 값을 모아 새 목록을 만든다. 뷰라는 개념과 출력 표현을 구분한다.
수치 라이브러리의 reshape가 항상 복사 없는지, 전치 결과를 다른 API에 넘길 수 있는지는 실제 연속성 조건과 계약에 따라 달라진다. NumPy는 기본 슬라이싱과 고급 인덱싱, 복사·뷰의 차이를 문서화하고 있으므로 연산별로 확인한다.
예제 코드
flat = list('ABCDEF')
def transpose_view(row, column):
if not 0 <= row < 3 or not 0 <= column < 2:
raise IndexError('invalid coordinates')
return flat[column * 3 + row]
print([[transpose_view(r, c) for c in range(2)] for r in range(3)])
flat[1] = 'X'
print(transpose_view(1, 0))
실행 결과
[['A', 'D'], ['B', 'E'], ['C', 'F']]
X슬라이스 복사와 버퍼 뷰의 다른 결과
Python list 슬라이스는 새 바깥 목록을 만들지만 memoryview는 버퍼를 공유하는 뷰를 제공할 수 있다. 문법이 구간을 나타낸다고 해서 자료 복사의 유무가 같지는 않다. 무엇을 반환하는지 API 계약으로 확인한다.
아래 bytearray의 [1:4] 슬라이스는 별도 바이트열이며 memoryview(data)[1:4]는 원본 버퍼를 공유한다. 복사본의 첫 바이트를 X로 바꾸어도 원본은 그대로지만 뷰의 첫 바이트를 Y로 바꾸면 원본 두 번째 바이트가 바뀐다.
뷰는 큰 복사를 피할 수 있지만 원본 수명과 변경 가능성을 함께 갖는다. 작은 부분만 보유해도 큰 원본 버퍼가 계속 살아 있을 수 있다. 원본을 늘리거나 재할당하는 연산도 활성 뷰 때문에 제한될 수 있다.
아래에서는 뷰를 release한 뒤 종료한다. 모든 언어의 뷰가 같은 방식으로 관리되는 것은 아니며 소유권·읽기 전용·길이 변경·연속성 조건을 확인해야 한다. 복사 없는 접근이 항상 더 적은 전체 메모리를 보장하는 것도 아니다.
예제 코드
data = bytearray(b'abcde')
copy = data[1:4]
view = memoryview(data)[1:4]
copy[0] = ord('X')
print(data.decode(), copy.decode())
view[0] = ord('Y')
print(data.decode(), bytes(view).decode())
view.release()
실행 결과
abcde Xcd
aYcde Ycd타입이 정해진 수치 배열과 바이트 표현
Python array 모듈은 typecode로 원소 표현을 정해 수치 값을 조밀하게 보관하는 배열을 제공한다. list처럼 임의 객체를 섞는 목적과 다르다. 사용할 수 있는 값 범위와 원소 크기는 선택한 타입 및 플랫폼 계약에 따른다.
아래 array('B')는 부호 없는 바이트 값 0부터 255를 저장한다. 값 256은 범위를 넘으므로 OverflowError가 발생한다. 이 예제는 크기가 명확한 바이트 타입을 사용한다. 다른 정수 코드의 크기를 모든 플랫폼에서 같은 값으로 단정하지 않는다.
바이트열과 정수 배열은 해석 계층이 다르다. 여러 바이트로 된 정수를 파일·네트워크에 기록할 때는 바이트 순서, 부호, 폭을 명시해야 한다. 플랫폼의 내부 표현을 그대로 직렬화하면 다른 시스템에서 다르게 읽을 수 있다.
압축된 숫자 배열을 사용한다고 모든 계산이 자동으로 벡터화되는 것은 아니다. 저장 형식, 연산 구현과 하드웨어 이용은 별개다. 이 예제는 값 범위와 저장 단위를 확인하는 것으로 한정한다.
예제 코드
from array import array
values = array('B', [0, 127, 255])
print(values.tolist(), values.itemsize, len(values.tobytes()))
try:
values.append(256)
except OverflowError:
print('out of byte range')
print(int.from_bytes(bytes([1, 2]), 'big'))
print(int.from_bytes(bytes([1, 2]), 'little'))
실행 결과
[0, 127, 255] 1 3
out of byte range
258
513누적 합으로 구간 질의에 답하기
배열의 여러 구간 합을 반복 계산한다면 매번 구간을 순회하는 대신 앞부분의 합을 미리 저장할 수 있다. prefix[0]=0, prefix[i+1]=prefix[i]+values[i]로 두면 prefix[k]는 [0,k)의 합이다.
[left,right)의 합은 prefix[right]−prefix[left]다. 두 앞부분 합에서 공통 구간 [0,left)를 빼면 필요한 부분만 남는다. 길이가 n인 입력에 n+1개 누적 값이 필요한 이유와 빈 구간 결과 0도 이 정의에서 나온다.
전처리는 O(n), 구간 질의는 합·뺄셈을 상수 비용으로 보는 모델에서 O(1)이다. 누적 배열은 O(n) 공간이다. 입력이 바뀌면 뒤쪽 누적 값들을 갱신해야 하므로 변경이 잦은 문제에서는 다른 구조가 필요할 수 있다.
Python 정수는 큰 값을 표현할 수 있지만 비트 수가 매우 커지면 산술 비용도 커진다. 고정 폭 정수 언어에서는 누적 합의 오버플로 범위를 따로 확인한다. 수식이 맞아도 표현 범위가 부족하면 결과가 틀릴 수 있다.
예제 코드
def prefix_sums(values):
result = [0]
for value in values:
result.append(result[-1] + value)
return result
def range_sum(prefix, left, right):
if not 0 <= left <= right < len(prefix):
raise IndexError('invalid half-open interval')
return prefix[right] - prefix[left]
values = [3, -1, 4, 2]
prefix = prefix_sums(values)
print(prefix)
print(range_sum(prefix, 1, 4))
print(range_sum(prefix, 2, 2))
실행 결과
[0, 3, 2, 6, 8]
5
0차분 배열로 여러 구간 덧셈 모으기
길이 n의 0 배열에서 여러 [left,right) 구간에 값을 더한 뒤 최종 결과만 필요하다면 차분 배열을 쓸 수 있다. difference[left]에 value를 더하고 difference[right]에서 value를 뺀 뒤 누적하면 해당 구간에서만 증가분이 유지된다.
right=n인 갱신을 같은 규칙으로 처리하기 위해 길이 n+1의 차분 저장소를 둔다. 결과에는 앞의 n개 누적 값만 사용한다. 빈 구간 left=right는 같은 칸에 더하고 빼므로 변화가 없다.
아래 길이 5에서 [1,4)에 3을 더하고 [2,5)에 −1을 더하면 [0,3,2,2,−1]이다. 각 갱신이 O(1), 마지막 복원이 O(n)이므로 q개 갱신을 O(n+q)로 모을 수 있다. 매 갱신 직후 임의 위치의 최신 값을 바로 질의하는 요구에는 이 구현이 그대로 맞지 않는다.
입력 배열이 0이 아닌 경우에는 기존 값의 차분을 만들거나 최종 증가분을 원본에 더하는 방식이 필요하다. 이 함수의 계약은 0에서 시작하는 배치 구간 덧셈으로 명시한다.
예제 코드
def apply_additions(length, updates):
if length < 0:
raise ValueError('negative length')
difference = [0] * (length + 1)
for left, right, value in updates:
if not 0 <= left <= right <= length:
raise IndexError('invalid update')
difference[left] += value
difference[right] -= value
current = 0
result = []
for index in range(length):
current += difference[index]
result.append(current)
return result
print(apply_additions(5, [(1, 4, 3), (2, 5, -1)]))
print(apply_additions(3, [(1, 1, 9)]))
print(apply_additions(0, []))
실행 결과
[0, 3, 2, 2, -1]
[0, 0, 0]
[]두 인덱스로 안정적으로 압축하기
음수 원소를 제거하면서 남는 원소의 순서를 유지한다고 하자. 읽기 인덱스 read는 모든 원소를 보고 쓰기 인덱스 write는 다음 보존 위치를 가리킨다. 남길 값을 만나면 values[write]에 쓰고 write를 늘린다.
write≤read이므로 아직 읽지 않은 오른쪽 원소를 덮지 않는다. [0,write)에는 지금까지 읽은 값 중 남길 원소가 원래 순서대로 있다. 이 불변식이 압축의 정확성과 안정성을 설명한다.
반복 종료 후 뒤쪽 남은 슬롯을 잘라 논리 길이를 맞춘다. 시간은 O(n)이고 알고리즘의 인덱스 상태는 O(1)이다. 런타임의 내부 리스트 축소·메모리 관리까지 특정 임시 할당량으로 보장하는 설명은 아니다.
반복 중에 remove를 호출하며 같은 배열을 앞으로 순회하면 인덱스가 당겨져 일부 원소를 건너뛸 수 있다. 또 값마다 중간 삭제를 반복하면 이동 비용이 누적될 수 있다. 한 번의 압축은 이런 반복 이동을 피한다.
예제 코드
def keep_nonnegative(values):
write = 0
for read in range(len(values)):
if values[read] >= 0:
values[write] = values[read]
write += 1
del values[write:]
return write
values = [3, -1, -2, 0, 5, -4]
print(keep_nonnegative(values), values)
values = [-1, -2]
print(keep_nonnegative(values), values)
실행 결과
3 [3, 0, 5]
0 []순서가 필요 없다면 마지막 원소로 메우기
중간 원소를 삭제하되 순서를 유지할 필요가 없으면 마지막 원소를 삭제 위치로 옮기고 마지막을 제거할 수 있다. 전체 뒤쪽 원소를 이동하지 않아 고정 개수의 슬롯 수정으로 처리할 수 있다.
[A,B,C,D]의 인덱스 1을 삭제하면 [A,D,C]가 된다. B는 사라지지만 원래 C,D의 상대 순서가 바뀐다. 순서 보존 삭제와 같은 연산이라고 부르면 안 되며 UI 목록이나 정렬된 데이터에는 적합하지 않을 수 있다.
객체 식별자에서 인덱스로 가는 외부 매핑이 있다면 이동한 D의 새 위치도 갱신해야 한다. 배열 내부 변경은 맞아도 외부 인덱스가 낡으면 이후 조회가 잘못될 수 있다. 여러 구조의 일관성을 함께 유지해야 한다.
아래 함수는 빈 목록이나 범위 밖 인덱스를 거부하고 삭제한 값을 반환한다. 마지막 원소를 지울 때도 같은 슬롯에 자기 값을 쓴 뒤 pop하므로 같은 규칙으로 처리된다.
예제 코드
def remove_unordered(values, index):
if not 0 <= index < len(values):
raise IndexError('invalid index')
removed = values[index]
values[index] = values[-1]
values.pop()
return removed
values = list('ABCD')
print(remove_unordered(values, 1), values)
print(remove_unordered(values, 2), values)
실행 결과
B ['A', 'D', 'C']
C ['A', 'D']밀집 배열과 희소 데이터
가능한 인덱스 범위가 매우 크지만 실제 값이 있는 위치가 적다면 모든 슬롯을 확보하는 밀집 배열은 낭비가 클 수 있다. 예를 들어 0부터 10억까지의 사용자 식별자 중 몇 개만 활성 상태라면 식별자를 그대로 배열 인덱스로 쓸지 다시 검토한다.
사전은 존재하는 키만 보관할 수 있지만 순회 순서·메모리 오버헤드·조회 비용 모델이 배열과 다르다. 희소 행렬은 행·열 좌표와 값, 행 시작 위치 같은 별도 표현을 사용한다. 기본값이 0인지, 빠진 값인지, 알 수 없는 값인지도 구별해야 한다.
JavaScript Array는 속성과 length의 의미를 가지며 빈 슬롯을 허용할 수 있다. 그 이름만 보고 동일 타입 값이 항상 조밀한 연속 메모리에 저장된다고 언어 수준에서 단정하지 않는다. 숫자 버퍼 요구에는 TypedArray 같은 다른 계약을 검토한다.
자료 표현을 바꾸면 없는 원소 처리와 반복 범위도 달라진다. 성능 최적화 전에 의미가 동일한지 확인해야 한다. 빈 슬롯, undefined, null, 0을 같은 상태로 합치면 응용 프로그램의 결과가 바뀔 수 있다.
캐시 지역성과 순회 순서
연속 저장은 이웃 원소를 가까운 메모리에서 읽을 수 있게 한다. 행 우선 행렬을 행마다 순회하면 인접 원소를 차례로 사용하지만 열마다 순회하면 큰 간격으로 이동할 수 있다. 이 차이가 실제 메모리 접근 성능에 영향을 줄 수 있다.
그렇다고 행 우선 순회가 모든 환경에서 항상 빠르다고 단정하지 않는다. 데이터 크기, 캐시, 컴파일러 최적화, 인터프리터 오버헤드, 실제 stride와 연산량이 함께 작용한다. 작은 Python 중첩 목록 측정을 수치 라이브러리의 연속 행렬 전체로 일반화할 수 없다.
벡터화와 SIMD도 저장 형식만으로 자동 결정되지 않는다. 연산 의존성, 정렬, 분기, 타입과 실행 라이브러리가 중요하다. 연속 배열은 유리한 조건을 줄 수 있지만 “배열이면 병렬 계산”이라는 의미는 아니다.
벤치마크를 설계한다면 입력 생성·변환·할당과 핵심 계산을 구분하고 같은 결과를 계산하는지 확인한다. 이 문서는 성능 수치를 만들어 제시하지 않고 위치 계산과 실제 예제 결과로 구조의 원리를 설명한다.
언어별 배열 계약을 구분해서 읽기
Java 배열 객체는 생성 후 길이가 고정되며 원소 타입과 범위 검사가 있다. 배열의 배열은 하위 배열 참조를 저장하므로 행마다 길이가 다를 수 있다. 참조 타입 배열의 공변성과 런타임 저장 검사도 일반적인 임의 객체 목록과 다른 규칙이다.
Rust의 [T;N]은 길이 N이 타입에 포함되는 고정 길이 배열이다. 빌린 연속 구간을 나타내는 slice와 가변 소유 버퍼 Vec는 다른 역할이다. 길이가 고정이라는 말이 곧 원소가 불변이라는 뜻은 아니며 변경 가능성은 빌림과 바인딩 조건을 따른다.
C++의 내장 배열은 원소가 연속 배치되는 계약을 갖지만 이를 함수에 넘길 때의 타입 변환, 크기 정보와 수명은 별도 주의가 필요하다. 표준 라이브러리의 array, vector, span은 각각 고정 소유·가변 소유·비소유 뷰 같은 다른 계약을 제공한다.
Python list, array.array, memoryview와 NumPy ndarray 역시 같은 것이 아니다. 이름이나 대괄호 문법보다 길이 변경, 원소 타입, 소유권, 복사·뷰, 다차원 형태와 범위 처리 규칙을 비교하는 것이 정확하다. 이 문서에서 실제 실행한 코드는 Python 표준 라이브러리 예제다.
고정 버퍼의 연산열 검증
다음 검사는 FixedBuffer를 일반 Python 목록과 비교한다. 용량 0,1,4,8 각각에서 1,000회 작업을 수행하여 앞·뒤·중간 삽입과 삭제를 섞는다. 빈 상태 제거와 가득 찬 삽입은 지정한 예외를 내야 한다.
매 단계 유효 원소 순서, size와 여유 공간이 일치하는지 확인한다. 값으로 None도 사용하므로 유효 범위를 슬롯의 None 여부로 정하면 틀린다는 점까지 검사한다. 여유 공간만 None이어야 한다.
고정 시드를 쓰므로 같은 실행 환경에서 연산열을 재현할 수 있다. 4,000단계 검사는 모든 정수와 모든 연산열의 증명은 아니지만 이동 방향과 경계 처리 구현을 확인하는 데 유용하다.
실패한 연산이 상태를 바꾸지 않는지도 기준 목록과의 비교에서 드러난다. 메모리 부족이나 다른 스레드의 변경은 이 검사의 범위가 아니며 실제 고정 크기 원시 버퍼 구현을 검사한 것도 아니다.
예제 코드
from random import Random
rng = Random(73)
checks = 0
for capacity in [0, 1, 4, 8]:
actual, expected = FixedBuffer(capacity), []
for _ in range(1000):
if rng.randrange(2):
index = rng.randrange(len(expected) + 1)
value = rng.choice([None, -1, 0, 8])
if len(expected) == capacity:
try:
actual.insert(index, value)
except OverflowError:
pass
else:
raise AssertionError('overflow accepted')
else:
actual.insert(index, value)
expected.insert(index, value)
elif expected:
index = rng.randrange(len(expected))
assert actual.remove(index) == expected.pop(index)
else:
try:
actual.remove(0)
except IndexError:
pass
else:
raise AssertionError('empty removal accepted')
assert actual.values() == expected
assert actual.size == len(expected)
assert all(x is None for x in actual.storage[actual.size:])
checks += 1
print(checks)
실행 결과
4000구간 합·압축·차분의 완전 열거 대조
구간 합은 값 −1,0,1로 만들 수 있는 길이 0부터 6까지의 모든 배열과 모든 유효한 [left,right)를 검사한다. 기준 결과는 슬라이스를 직접 합한 값이다. 빈 배열·빈 구간·전체 구간과 음수 값이 포함된다.
같은 1,093개 배열에서 압축 결과를 조건 필터와 비교한다. 순서까지 동일한지 확인하므로 원소 개수만 맞고 순서가 바뀐 구현을 구분할 수 있다. 함수가 반환한 새 길이도 검사한다.
차분 배열은 길이 4의 모든 반열린 구간과 증가량 −1,2의 조합을 만들고 두 갱신의 모든 쌍을 검사한다. 총 900쌍이며 겹친 구간·분리된 구간·빈 구간·음수 증가량이 포함된다. 기준은 각 구간의 모든 원소에 직접 더하는 구현이다.
작은 범위의 독립 구현과 대조하는 검사는 공식만 보고 지나칠 수 있는 끝 경계 오류를 찾는 데 도움이 된다. 복잡도는 별도의 연산 수 분석으로 설명했으며 테스트 횟수를 성능 보장의 근거로 사용하지 않는다.
예제 코드
from itertools import product
range_checks = compact_checks = 0
for length in range(7):
for values in product([-1, 0, 1], repeat=length):
prefix = prefix_sums(values)
for left in range(length + 1):
for right in range(left, length + 1):
assert range_sum(prefix, left, right) == sum(values[left:right])
range_checks += 1
actual = list(values)
expected = [x for x in values if x >= 0]
assert keep_nonnegative(actual) == len(expected)
assert actual == expected
compact_checks += 1
updates = [(left, right, value) for left in range(5)
for right in range(left, 5) for value in [-1, 2]]
difference_checks = 0
for pair in product(updates, repeat=2):
expected = [0] * 4
for left, right, value in pair:
for index in range(left, right):
expected[index] += value
assert apply_additions(4, pair) == expected
difference_checks += 1
print(range_checks, compact_checks, difference_checks)
실행 결과
27064 1093 900배열을 사용할 때 확인할 계약
먼저 인덱스의 의미와 유효 범위를 정한다. 인덱스가 날짜인지 식별자인지, 음수를 허용하는지, 빈 배열과 빈 구간을 어떻게 처리하는지 명확해야 한다. 수학적인 인덱스 범위와 언어가 실제로 허용하는 문법이 다를 수 있다.
다음으로 순서 유지, 길이 변경과 메모리 소유권을 살핀다. 중간 삭제에서 순서가 필요 없으면 다른 구현이 가능하지만 요구사항이 바뀐 것이다. 뷰가 원본을 공유하는지와 재할당 후 참조가 유효한지도 계약의 일부다.
배열을 기반으로 하는 알고리즘은 유효 구간과 불변식을 함께 설명하면 이해하기 쉽다. 삽입의 미복사 원본 보호, 압축의 write≤read, 누적 합의 [0,k) 정의처럼 작은 규칙이 코드 전체의 정확성을 지탱한다.
이후 동적 배열의 성장 정책, 이분 탐색의 경계, 누적 합·차분 배열과 슬라이딩 윈도를 이어서 학습할 수 있다. 같은 배열 저장소 위에서도 요구하는 연산과 상태 정의에 따라 전혀 다른 알고리즘이 만들어진다.