2-2. 동적 배열

2-1. 배열

동적 배열을 알기 위해서는 배열을 알아야 한다!

 

1. 리스트

 아래 코드를 살펴보자. 이 코드를 실행했을 때 데이터를 계속 추가할 경우 베열의 길이가 고정되어 있다면 오류가 날 텐데 리스트는 오류가 나지 않는다. 그 이유는 바로 데이터가 추가될수록 크기가 일정 단계마다 커지기 때문이다!

import sys								# provides getsizeof function
data = []
for k in range(n):							# NOTE: must fix choice of n
	a = len(data)							# number of elements
    b = sys.getsizeof(data)						# actual size in bytes
    print("Length: {0:3d}; Size in bytes: {1:4d}".format(a, b))
	data.append(None)						# increase length by one

 

2. 동적 배열

 이러한 배열을 동적 배열(Dynamic Array)라고 한다. 동적 배열이란 크기를 지정하지 않는 배열로, 할당된 공간이 다 채워지면 크기가 동적으로 증가하는 배열을 말한다. 동적 배열은 기하급수적(geometric expansion) 증가 방식으로 증가해 기존 크기의 2배로 증가하며, 사용 공간이 줄어들면 자동으로 감소한다.

동적 배열의 증가 방식은 기존 크기의 2배씩

3. 동적 배열 구현

 Python 객체를 참조하는 레퍼런스 배열을 만드려면 C 호환 데이터를 제공하는 외부 함수 라이브러리인 ctypes를 통해low-level로 배열을 생성해야 한다.

array = (c * ctypes.py_object)()

우선 DynamicArray 클래스의 전체 코드를 살펴본 다음, 부분부분을 보도록 하자.

import ctypes									# provides low-level arrays

class DynamicArray:
	"""A dynamic array class akin to a simplified Python List."""
    
    def __init__(self):
    	"""Create an empty List."""
        self._n = 0								# count actual elements
        self._capacity = 1							# default array capacity
        self._A = self._make_array(self._capacity)				# low-level array
   
	def __len__(self):
		"""Return number of elements stored in the array."""
    		return self._n
    
    def __getitem__(self, k):
		"""Return element at index k."""
    	if not 0 <= k < self._n:
        	raise IndexError('invalid index')
        return self._A[k]							# retirieve from array
        
    def _make_array(self, k):							# nonpublic utility
    	"""Return new array with capacity c."""
    	return (c * ctypes.py_object)()						# see ctypes documentation
        
 	def _resize(self, c):							# nonpublic utility
   		"""Resize internal array to capacity c."""
        B = self._make_array(c)							# new (bigger) array
        for k in range(self._n):
        	B[k] = self._A[k]
        self._A = B								# use the bigger array
        self._capacity = c
    
 	def append(self, obj):
    	"""Add object to end of the array."""
        if self._n == self._capacity:						# not enough room
        	self._resize(2 * self._capacity)				# so double capacity
        self._A[self._n] = obj
        self._n += 1
        
	def remove(self, value):
    	"""Remove first occurrence of value(or raise ValueError)."""
        # note: we do not consider shrinking the dynamic array in this version.
        for k in range(self._n):
        	if self._A[k] == value:						# found a match!
            	for j in range(k, self._n - 1):					# shift others to fill gap
                	self._A[j] = self._A[j + 1]
                self._A[self._n - 1] = None					# help garbage collection
                self._n -= 1							# we have one less item
                return
		raise ValueError('value not found')				# only reached if no match
        
	def insert(self, k, value):
    	"""Insert value at index k, shifting subsequent values rightward."""
        # (for simplicity, we assume 0 <= k <= n in this version)
        if self._n == self._capacity:						# not enough room
        	self._resize(2 * self._capacity)				# no double capacity
        for j in range(self._n, k, -1):						# shift rightmost first
        	self._A[j] = self._A[j - 1]
        self._A[k] = value							# store newest element
        self._n += 1

        

 

3. 동적 배열 구현 코드 살펴보기

1) 클래스 선언

import ctypes									# provides low-level arrays

class DynamicArray:
	"""A dynamic array class akin to a simplified Python List."""

2) 초기화

    def __init__(self):
    	"""Create an empty List."""
        self._n = 0								# count actual elements
        self._capacity = 1							# default array capacity
        self._A = self._make_array(self._capacity)				# low-level array

• self._n: 요소 개수
• self._capacity: 배열의 크기
• self._A: 레퍼런스 배열(길이가 1인 비어있는 배열 생성)

3) 길이

	def __len__(self):
		"""Return number of elements stored in the array."""
    		return self._n

 4) 인덱스 k의 데이터 반환

    def __getitem__(self, k):
		"""Return element at index k."""
    	if not 0 <= k < self._n:
        	raise IndexError('invalid index')
        return self._A[k]							# retirieve from array

5) 배열 만들기

    def _make_array(self, k):							# nonpublic utility
    	"""Return new array with capacity c."""
    	return (c * ctypes.py_object)()						# see ctypes documentation

6) 배열 크기 조절(resize)

resize

 	def _resize(self, c):							# nonpublic utility
   		"""Resize internal array to capacity c."""
        B = self._make_array(c)							# new (bigger) array
        for k in range(self._n):
        	B[k] = self._A[k]
        self._A = B								# use the bigger array
        self._capacity = c

6) 데이터 추가(append)

 append는 배열이 다 차있을 때 크기를 2배 늘린 후, n+1번째 항에 새로운 객체를 추가한다.

append

 	def append(self, obj):
    	"""Add object to end of the array."""
        if self._n == self._capacity:						# not enough room
        	self._resize(2 * self._capacity)				# so double capacity
        self._A[self._n] = obj
        self._n += 1

7) 데이터 삭제(remove)

 리스트에서 value 값을 갖는 요소를 찾은 후 요소를 삭제하고 뒤 부분을 한 칸씩 당긴다. 이후 길이를 n-1로 줄인다.

remove

	def remove(self, value):
    	"""Remove first occurrence of value(or raise ValueError)."""
        # note: we do not consider shrinking the dynamic array in this version.
        for k in range(self._n):
        	if self._A[k] == value:						# found a match!
            	for j in range(k, self._n - 1):					# shift others to fill gap
                	self._A[j] = self._A[j + 1]
                self._A[self._n - 1] = None					# help garbage collection
                self._n -= 1							# we have one less item
                return
		raise ValueError('value not found')				# only reached if no match

8) 데이터 삽입(insert)

 insert에서는 배열이 다 찼으면 크기를 두 배 늘린 후, 인덱스를 k번째 요소부터 한 칸씩 뒤로 민다. 결과적으로 인덱스 k번째 요소에 새로운 값이 배정된다.

insert

	def insert(self, k, value):
    	"""Insert value at index k, shifting subsequent values rightward."""
        # (for simplicity, we assume 0 <= k <= n in this version)
        if self._n == self._capacity:						# not enough room
        	self._resize(2 * self._capacity)				# no double capacity
        for j in range(self._n, k, -1):						# shift rightmost first
        	self._A[j] = self._A[j - 1]
        self._A[k] = value							# store newest element
        self._n += 1

다음 게시물에서는 분할 분석과 성능 분석에 대해 다룬다.