array & tuple & set

data structure

자료구조란 데이터에 편리하게 접근하고 조작하기 위해 데이터를 저장하거나 조직하는 방법을 의미한다. 어떤 자료구조를 사용할지는 전체 개발 시스템에 큰 영향을 끼칠 수 있으므로, 상황과 문맥에 맞는 적절한 구조를 사용해야 한다.

array

array 의 가장 큰 특징은 순차적으로 데이터를 저장한다는 점이다. 순서가 있다보니 index 를 지정할 수 있다는 장점이 있으나, 반면에 정보가 삭제되거나 추가되는 경우 index 값이 수시로 변경될 수 있으므로 정보가 자주 변경되는 상황에서 사용하기에는 적절하지 않다.

resizing

배열이 생성될 때, 컴퓨터는 배열에 대해 어느 정도의 메모리를 미리 할당해준다. 이를 사전할당(pre-allocation) 이라고 한다. 메모리를 사전 할당 함으로써, 새로 추가되는 요소들도 순차적으로 메모리에 저장될 수 있다. 그러나 처음 할당한 메모리의 이상으로 요소가 증가할 경우, 메모리의 추가 할당이 필요하다. 따라서 array 는 요소의 수가 예측되지 않는 데이터를 다루기에도 적절하지 않다.

list

일전에 기업협업 프로젝트를 위해 JavaScript 를 공부할 때, array method 에 대해 배우면서 python 의 list 와 유사하다고 느낀 바 있다.
일반적인 list 는 인덱스를 가지고 있지 않지만, python 에서의 list 는 인덱스를 사용하여 접근이 가능하다는 점에서 배열과 유사하게 구현되어있다고 볼 수 있겠다. 또, append 나 pop 등의 method 를 이용하여 stack 처럼 활용할수도 있다.

array.array

python 에서도 array 를 지원하기는 한다. import array 를 통해 import 해주면 array 를 사용할 수 있다. 다만 list 와 다른 점은, type code 를 이용하여 저장되는 객체의 형을 제한한다는 점이다. 어떤 객체를 사용할 수 있는지는 python 공식문서에서 확인할 수 있다.

 

ref) https://soshace.com/python-array-explained-and-visualized/

 

간단한 테스트를 통해 array 와 list 가 소요하는 메모리를 알아보자. 순차적으로 시행되기 때문에 따로 test 해주어야 한다.

# list wasted memory test
import resource

startMemory = resource.getrusage(resource.RUSAGE_SELF).ru_maxrss

list = []
for i in range(1, 10000):
    list.append(i)

listMemory = resource.getrusage(resource.RUSAGE_SELF).ru_utime
print('list wasted memory :', listMemory - startMemory)

# list wasted memory : 458752

 

# array wasted memory test
import array
import resource

startMemory = resource.getrusage(resource.RUSAGE_SELF).ru_maxrss

array = array.array('i')
for i in range(1, 10000):
    array.append(i)

arrayMemory = resource.getrusage(resource.RUSAGE_SELF).ru_maxrss
print('array wasted memory :', arrayMemory - startMemory)

# array wasted memory : 40960
# array 가 압도적으로 빠름을 확인할 수 있다.

list 와 array

numpy 는 python 에서 행렬이나 대규모 다차원 배열을 쉽게하기 위해 사용하는 대표적인 라이브러리이다. numpy 의 ndarray 와 list 를 비교해보면, 두 자료구조는 데이터 접근 방법에 차이가 있다.

 

ref) EduAtoZ - Programming / ndarray가 list 보다 빠른이유

 

요소에 바로 접근하는 array 에 비해 list 의 경우 객체가 연속 메모리에 있는것이 아니다. list 는 요소가 들어있는 슬롯(0x502800...) 에 대한 정보를 가지고 있다. 요소에 접근하기 위해서는 먼저 슬롯 안에 있는 item 의 레퍼런스(PyObject_Head)에 접근해야 한다. 그 레퍼런스 안에는 객체가 들어있으며, 그 객체의 주소에(ob_digit) 가야 요소에 접근할 수 있는 것이다. 따라서 array 에 비하여 list 가 느릴 수 밖에 없다.
그럼에도 불구하고 list 를 사용하는 이유는 무한정수 때문이다. ndarray 의 data 에 들어있는 값들에는 크기가 할당되어 있어 정수의 크기가 무한하지 않다. 그러나 list 는 각각의 객체를 갖고 있기 때문에 무한한 정수를 가질 수 있다.

tuple

tuple 은 list 와 마찬가지로 데이터를 순차적으로 저장할 수 있는 자료구조이지만 가변적인 성질을 가진 list 와 달리 불변하는immutable 성질을 가지고 있다. 한번 정의되면 수정할 수 없으나 list 보다 데이터를 더 적게 소모하므로 적은 수의 소규모 데이터를 저장할 때 많이 사용된다.

list 대신 tuple 을 사용하는 경우가 있다면, 그 이유는 메모리 용량 때문이다. list 는 수정이 가능하고 여러 요소들을 저장할 수 있기 때문에 tuple 보다 차지하는 메모리 용량이 훨씬 크다. 그러므로 수정이 필요없는 간단한 형태의 데이터를 표현할 때에는 tuple 을 사용하는것이 훨씬 효과적이다.

개별 변수값을 tuple 로 만드는 것을 packing, tuple 을 =(assignment) 명령어를 통해 개별 변수값으로 지정하는 것을 unpacking 이라 한다.

packing = 1,3,5
print(packing) # (1, 3, 5) 로 packing

num1,num2,num3 = packing # 1, 3, 5 를 unpacking 하여 각각 num1, num2, num3 에 넣는다
print(num1) # 1

num1, _, num2 = packing # 사용되지 않거나 필요없는 변수는 언더스코어로 표시하여 제거해준다
print(num2) # 5

a, b, *c = (1, 2, 3, 4, 5) # 변수 앞에 *표시를 하면 여러개의 값을 갖는 리스트가 된다
print(a) # 1
print(b) # 2
print(c) # [3, 4, 5]

set

set 는 수학에서 이야기하는 집합과 비슷하다.

• 중괄호를 이용한다는 점은 dictionary 와 비슷하지만, key 없이 값만 존재한다.
• list 와 마찬가지로 여러 타입의 요소들을 저장할 수 있으나 list 형은 set 의 요소가 될 수 없다. set 자체는 mutable 하지만, set 의 element 는 immutable 하여 unique 값을 갖기 때문이다. (list 는 mutable 하므로 불가능하다는 의미)

x = {1, 2, 3, 'python', [4, 5, 6], (7, 8, 9)}
print (x)

Traceback (most recent call last):
  File "/Users/sua/algorithm/data-structure/sets.py", line 1, in <module>
    x = {1, 2, 3, 'python', [4, 5, 6], (7, 8, 9)}
TypeError: unhashable type: 'list'
# list 는 unhashable type 이기 때문에 set 의 요소가 될 수 없다고 나온다.

 

• 순서가 없으므로 index 또한 없다.
• set 에서 요소들이 저장될 때에는 저장할 요소 값의 해시값을 구한 후, 해시값에 해당하는 공간에 저장하는 방식을 취한다. 해시값을 기반으로 저장하기 때문에 중복된 요소를 허용하지 않으며(unique), 만일 동일한 값의 요소가 이미 존재하고 있다면 새로운 요소가 이전의 요소를 치환replace 한다.
• look up 이 빠르다는 장점이 있다.