Python으로 구현하는 자료구조 : Array

Array

Python Array 자료형의 특징과 삽입, 삭제, 조회(검색) 하는 방법에 대해

알아보도록 하겠습니다.

---

Python은 Array를 기본 자료형으로 제공하지 않습니다. 따라서 Array을 사용하고 싶다면 NumPy와 같은 패키지를 추가로 설치해야만 합니다. 이 포스팅에서는 NumPy를 따로 설치하여 사용하지 않고 Python의 기본 컨테이너 중 하나인 List를 Array 대신 사용해보도록 하겠습니다. 

 

# Array는 무엇인가요

Array는 여러 원소들이 순차적으로 메모리에 저장(contiguous memory locations)하는 구조입니다. 기본적으로 배열은 모든 원소가 같은 자료형이어야 하며, 배열의 크기를 변경할 수 없습니다.  Array를 담은 변수에는 배열의 첫 원소의 메모리 주소를 담고 있기 때문에 우리는 index를 사용하여 원소에 빠르게 접근할 수 있습니다. 배열의 원소가 모두 같은 자료형이기 때문에, 원소의 자료형이 무엇인지에 따라 다음 index의 원소가 위치한 물리적인 위치로 얼마만큼 이동해야 하는지 알 수 있습니다. 

 

# 배열의 장·단점은요

배열의 장점은, (1) 구현이 쉽고, (2) Index를 활용하면 랜덤으로 원소에 접근(Random access)이 가능하여 검색에서 성능이 좋으며 (3) 순차 탐색에서도 배열은 연속된 메모리 공간에 할당하므로 연결 리스트보다도 빠른 성능을 보이며 (4) 운영체제의 캐시 지역성을 활용할 수 있습니다.

※ 캐시 지역성(cache locality) : 운영체제는 물리적으로 근접한 위치의 데이터가 보통 자주 활용되기 때문에 미리 캐시에 넣어둠으로써 CPU의 성능을 향상시키는데 배열은 물리적으로 연속된 곳에 데이터를 저장하기 때문에 이러한 기능을 보다 잘 활용할 수 있습니다.

배열의 단점은, (1) (원소를 이동해야 하는 연산작업이 필요하므로) 삽입, 삭제시 비효율적이며, (2) 초기에 선언한 크기를 변경할 수 없으며 (즉, 사용안한 만큼의 메모리가 낭비될 수도 있으며) (3) (배열 요소를 삭제했더라도 변수의 선언이 해제되지 않는 이상 점유하고 있는 메모리이므로) 메모리의 재사용이 불가능합니다.

 

 # Python의 List와의 차이는 무엇인가요

우리는 파이썬의 List를 배열처럼 활용할 거지만, 둘의 차이점도 잘 알고 있어야겠습니다. 파이썬의 List 자료형도 Array처럼 index를 사용하여 원소에 접근할 수 있지만, (1) 서로 다른 자료형을 원소로 가질 수도 있으며, (2) 동적 배열(Dynamic Array)로써 Array와는 다르게 자유롭게 크기를 확장 할 수 있습니다. 리스트 안의 원소들은 그 값들은 자유롭게 변경도 가능(Mutable)합니다.  

# 원소 삽입

배열은 물리적인 위치에서 순차적으로 원소를 저장합니다. 따라서 맨 앞이나 중간에 원소를 삽입할 경우에는 배열의 원소들을 순차적으로 저장해야 하므로 다른 원소들을 순서대로 이동해야 하는 번거로움이 있습니다. 

Python에서는 Index가 0인 곳에 삽입하는 작업이 많이 일어날 경우에는 collections.deque를 이용하여 appendleft() 메소드를 활용하는 편이 효율적입니다. Array는 순차적으로 데이터를 삽입하고 조회할 필요가 있을 때 활용하는 것이 좋습니다.

1 2 3 4 5 6 7 8

test1 = ['a', 'b', 'c']     # 맨 뒤에 삽입 test1.append('d') # output : ['a','b','c','d']   # index의 위치에 삽입 (list의 범위를 초과하는 index는 맨 뒤에 삽입) test1.insert(0, 'f')   # output : ['f','a','b','c,','d']

cs

# 원소 삭제

원소의 삭제는 순차적으로 저장되어 있는 데이터들의 위치를 이동시켜야 합니다. 

test1 = ['a', 'b', 'c']
 
 
# del 키워드를 통한 inde의 원소 삭제
del[0]  # output : ['b','c']
 
# 원소를 찾아 삭제 (원소가 없으면 valueError 발생)
test1.remove('b') #output : ['c']
 

# 원소 조회(검색)

조회는 순차적으로 원소를 탐색해야 하며, 최악의 경우에는 모든 원소를 다 뒤져야 한다는 단점이 있습니다. index() 메소드를 사용해서 조회할 수도 있으며, array는 iterable 하기 때문에 find() 함수에서처럼 for문을 사용하여 원소를 비교하여 index를 반환할 수도 있습니다.

test1 = ['a', 'b', 'c']
 
 
# index() 함수를 통한 탐색
test1.index('b') # output : 1
 
def find(arr, ch):
    i = -1
    for c in arr:
        i += 1
        if ch == c:
            return i
    else:
        return -1
 
find(test1. 'b') # 1
find(test1, 'd') # -1